9.2: Types of proof

There are a number of accepted “styles" of doing proofs. Here are some important ones:

Direct proof

The examples we’ve used up to now have been direct proofs. This is where you start from what’s known and proceed directly by positive steps towards your conclusion.

Direct proofs remind me of a game called “word ladders," invented by Lewis Carroll, that you might have played as a child:

WARM
||||
????
||||
COLD

You start with one word (like WARM) and you have to come up with a sequence of words, each of which differs from the previous by only one letter, such that you eventually reach the ending word (like COLD). It’s sort of like feeling around in the dark:

WARM
WAR
WAT
WLT
WIL
||||
....

This attempt seemed promising at first, but now it looks like it’s going nowhere. (“WOLD?" “CILD?" Hmm....) After starting over and playing around with it for a while, you might stumble upon:

WARM
WRM
WOR
ORD
COD

This turned out to be a pretty direct path: for each step, the letter we changed was exactly what we needed it to be for the target word COLD. Sometimes, though, you have to meander away from the target a little bit to find a solution, like going from BLACK to WHITE:

BLACK
LACK
CACK
RACK
TRCK
TRIC
TRIE
RITE
WITE

Here, we had to temporarily change our first letter three different times — two of which seemingly brought us no nearer to WHITE — in order to successfully forge a path through the tangled forest.

Knowing which direction to set out on is a matter of intuition plus trial and error. Given the axioms of any system (whether algebra, predicate logic, sets, etc.) there are an unfathomable number of different ways to proceed. The vast majority of them are bound to lead to dead ends. This is why a valid proof, when it is finished, is often an elegant and beautiful thing. It’s a thin braid of jewels glistening in the midst of a whole lot of mud.

Indirect proof

Also known as a proof by contradiction or reductio ad absurdum, the indirect proof starts in a completely opposite way. It says, “okay, I’m trying to prove X. Well, suppose for the sake of argument I assume that the opposite — not X — is true. Where would that lead me?" If you follow all the rules and it leads you to a contradiction, this tells you that the original assumption of \(\neg\)X must have been false. And this in turn proves that X must be true.

We do this all the time in our thinking. Say you’re driving down the highway. How do you know that the alternator in your car engine is working? A direct proof would require that you open the hood and examine the part, testing to ensure it works properly. An indirect proof simply says, “well, suppose it weren’t working properly. Then, my car engine wouldn’t operate. But here I am, driving down the road, and the engine obviously does operate, so that tells me that the alternator must be working properly."

One of the most famous indirect proofs dates from Euclid’s Elements in 300 B.C. It proves that the square root of 2 is an irrational number, a great surprise to mathematicians at the time (most of whom doubted the very existence of irrational numbers). Remember that an irrational number is one that cannot be expressed as the ratio of two integers, no matter what the integers are.

Proving this directly seems pretty hard, since how do you prove that there aren’t any two integers whose ratio is \(\sqrt{2}\), no matter how hard you looked? I mean, 534,927 and 378,250 are pretty dang close: \[\Bigg(\frac{534,927}{378,250}\Bigg)^2 = 2.000005.\] How could we possibly prove that no matter how hard we look, we can never find a pair that will give it to us exactly?

One way is to assume that \(\sqrt{2}\) is a rational number, and then prove that down that path lies madness. It goes like this. Suppose \(\sqrt{2}\) is rational, after all. That means that there must be two integers, call them \(a\) and \(b\), whose ratio is exactly equal to \(\sqrt{2}\): \[\frac{a}{b} = \sqrt{2}.\] This, then, is the starting point for our indirect proof. We’re going to proceed under this assumption and see where it leads us.

By the way, it’s clear that we could always reduce this fraction to lowest terms in case it’s not already. For instance, if \(a=6\) and \(b=4\), then our fraction would be \(\frac{6}{4}\), which is the same as \(\frac{3}{2}\), so we could just say \(a=3\) and \(b=2\) and start over. Bottom line: if \(\sqrt{2}\) is rational, then we can find two integers \(a\) and \(b\) that have no common factor (if they do have a common factor, we’ll just divide it out of both of them and go with the new numbers) whose ratio is \(\sqrt{2}\).

Okay then. But now look what happens. Suppose we square both sides of the equation (a perfectly legal thing to do): \[\begin{aligned} \frac{a}{b} &= \sqrt{2} \\ \Bigg(\frac{a}{b}\Bigg)^2 &= (\sqrt{2})^2 \\ \frac{a^2}{b^2} &= 2 \\ a^2 &= 2{b^2}. \\\end{aligned}\] Now if \(a^2\) equals 2 times something, then \(a^2\) is an even number. But \(a^2\) can’t be even unless \(a\) itself is even. (Think hard about that one.) This proves, then, that \(a\) is even. Very well. It must be equal to twice some other integer. Let’s call that \(c\). We know that \(a=2c\), where \(c\) is another integer. Substitute that into the last equation and we get: \[\begin{aligned} (2c)^2 &= 2{b^2} \\ 4c^2 &= 2{b^2} \\ 2c^2 &= b^2. \\\end{aligned}\] So it looks like \(b^2\) must be an even number as well (since it’s equal to 2 times something), and therefore \(b\) is also even. But wait a minute. We started by saying that \(a\) and \(b\) had no common factor. And now we’ve determined that they’re both even numbers! This means they both have a factor of 2, which contradicts what we started with. The only thing we introduced that was questionable was the notion that there are two integers \(a\) and \(b\) whose ratio was equal to \(\sqrt{2}\) to begin with. That must be the part that’s faulty then. Therefore, \(\sqrt{2}\) is not an irrational number. Q.E.D.