101 Interesting Things, part thirty-two: Proof by Contradiction

Contradictions do not exist. Paradoxes exist, usually expressed in clever-sounding phrases such as, "If you want peace, then prepare for war," or, "The tree of liberty must be refreshed from time to time with the blood of patriots and tyrants." These are mere conceits of what we call "common sense," though, and all they show is that reality doesn't always conform to our expectations of "what makes sense." But a bona fide contradiction is of the form, "X both is the case and is not the case, at exactly the same time and in exactly the same respect," and such statements are categorically false. We can establish this with good old fashioned deductive logic - specifically, with implication.

A statement of implication is a conditional, an "if-then" statement, and may be phrased as, "A implies C," or "If A, then C," where A is the Antecedent and C is the Consequent. These in their turn are propositional clauses, statements which may be taken on their own and determined to be either true or false (but not both - at least not at the same time and in the same respect). The whole implication may be taken itself as a proposition, and itself has truth value. To illustrate this point, let us consider the implication, "If I encounter a pile of babies, then I will wish for a fork and knife," because I've got A Modest Proposal on the brain.

"If I encounter a pile of babies, then I will wish for a fork and knife," may be written several different ways; in addition to the foregoing, we may also write, "D encountering a pile of babies implies that D will wish for a fork and knife," or "A implies C, where A is 'D encounters a pile of babies' and C is 'D wishes for a fork and knife'." I'll spare the symbolic logic, because if you know what that stuff means then you don't need me to tell you all of this. At any rate, our A and C may each be true or false independently, and the implication as a whole may be true or false as follows:

• If I do in fact encounter a pile of babies, then A is true.
• If I do in fact then wish for a fork and knife, then C is also true and the implication is true as a whole.
• If I do not in fact then wish for a fork and knife, then C is not true and the implication is false as a whole. This is the only way for an implication to be false as a whole proposition (if A is true and C is false).
• If I do not in fact encounter a pile of babies, then A is false.
• If A is false, then it does not matter whether C is true or false, because I never actually do the antecedent thing; the implication is thus true as a whole.

This is one of the weirdest consequences of logical implication: a false antecedent validly implies any consequent. This is also why David Lewis likes modal realism, because it justifies the weirdness of implication in his mind. I just want to punch him in the face. Moving on! A professor was once asked to show how "2=1" implies that he is the pope, and according to legend, he responded as follows: "2=1, and there are the two entities 'myself' and 'the pope'; since 2=1, we two entities are in fact one and the same entity, and thus I am the pope." As I have illustrated before, this makes first premises very dangerous, because a false premise validly implies absolutely anything. As it happens, only a false premise implies absolutely anything, so if you wind up implying anything and everything, then you know you've got a false premise somewhere (common-sense version: a statement that could mean anything, in fact means nothing). But I'm getting ahead of myself here.

I'm really writing this to get at the proof that the square root of two is an irrational number, which is to my mind one of the greatest-ever marriages of mathematics and logic (aside from, oh, the entire field of geometry). We start by assuming that the square root of two is rational and seeing where things go from there. If the square root of two is rational, then it can be written as the proportion of two integers a and b (such that ^a/_b is an irreducible fraction). This implication is true, because any rational number may be so described. So we start with:

√2=^a/_b

Since we have an equivalence, we can square both sides:

2=(^a/_b)²=^a2/_b²

Now cut out that middle part and multiply both sides by b²:

2b²=a²

Interesting! Because b² can be doubled to make a², we know that a² is a multiple of two; and since a is an integer, and even integers have even squares while odd integers have odd squares, we also know that a itself must be a multiple of two. So let's say that a=2x, where x is an integer, because of all of the foregoing and the fact that even integers may be halved to create yet more integers. Going back to the start, this gives us:

√2=^2x/_b

Lather, rinse, and repeat as before:

2=(^2x/_b)²=^4x2/_b²

Multiply both sides by b² as before:

2b²=4x², and divide by 2 for b²=2x²

Wait, what?! This means that b is also an even number! Which means that a and b can both be divided by two! Which means that ^a/_b is not an irreducible fraction, and we have thus reached a contradiction. Because our initial implication is true, the antecedent (viz. "the square root of 2 is a rational number") must perforce be false for the contradiction to be resolved. Quod erat demonstrandum, motherfucker!

You can also do a little mutatis mutandis to prove that the square root of 3, if written as the fraction ^a/_b, can never be made irreducible because a and b will always both be divisible by 3 (which is impossible, thus the contradiction, thus the square root of 3 is irrational). This also works for five, and seven, and every prime number, and every non-square integer. We may even generalize this proof for any prime number p as follows, with but one quick detour:

√p=^a/_b

p=(^a/_b)²=^a2/_b²

Since p is an integer, ^a2/_b² is also an integer because it is p. No non-integer may be multiplied unto itself to create an integer (try it, I dare you!), thus ^a/_b must also be an integer. But if ^a/_b is an integer, and can be multiplied unto itself to make p, then p must not be prime after all and so we contradict ourselves: if the square root of a number p is rational, then p is not prime. Since we stipulated at the start that p is in fact prime, we have thus shown that every prime number has an irrational square root. Hey, presto!

OK, math class is over, now go outside and play!