Proof by Contradiction

The proof method that we will talk about here is quite different than many others. In his famous book A Mathematician’s Apology, the great mathematician G.H. Hardy made an analogy between this proof style, which we call a proof by contradiction, to a gambit in chess. So before I try to analyze what this proof method is all about, I’ll first take a moment to explain the analogy.

There is not really a need to go all the way into the rules of chess in order to explain the idea of a gambit, because the same idea applies to other games. In chess, there are various pieces, and some of the pieces are more valuable than others. So, if a sequence of moves in chess causes you to ‘lose value,’ you want to avoid that. However, there are exceptions, and the exceptions are what we mean by a gambit. Gambits in chess are strategies that involve purposefully losing valuable pieces in order to gain position that will help win the game. Think of this as taking one step back and two steps forwards. The beginning of the plan looks really bad, but things turn out for the better.

Now, how might we apply this ‘one step backwards, two steps forwards’ idea to mathematics? Since the overall goal of mathematics is to understand what is and is not true about numbers, shapes, etc, with the goal of identifying as much truth as possible, taking one step backwards is assuming that something false is actually true – which is a mathematical failure. This amounts to beginning a math problem with a statement like “since we know 1+1=3…” I think most of us will feel a sense of unease at a claim like “1+1=3,” since it is clearly wrong. In mathematics, wrong is bad, right is good.

However, there is a principle of logic that I have discussed before that enables us to make use of false ideas. This is the principle of non-contradiction. This is absolutely essential. The principle tells us that there are no contradictions – no sentence can be at once both true and false. I think everyone knows this intuitively, and in fact if you spend some time thinking about it, it is actually impossible to deny the principle of non-contradiction (if you want a brain-teaser, try to imagine an argument about whether this principle is true). This principle can be taken as foundational to all thought, and in particular the way we think about mathematics.

Here is where the style of proof by contradiction arises. Suppose that there is a statement P and that we want to know whether P is true or false. Suppose we temporarily assume that P is false, and we later discover that assuming P is false leads us to affirm some kind of contradiction. Since the principle of non-contradiction tells us that there can never be any contradictions, our temporary guess that P is false led us into a problematic situation. We can’t continue believing that P is false any more because that is contradictory, and since there are only two choices available to us, P must be true.

This strategy is what we mean by proof by contradiction. Since all claims (in the context of mathematics at least) are either true or false, anything that cannot be false must be true. I will now show how this works with one of the most famous examples of this method, the proof that “the square root of 2 is irrational.” To be clear briefly on what this means, the rational numbers are all the fractions, and an irrational number is just any number that is not a fraction. It isn’t actually clear immediately that there is any such thing as an irrational number, and the proof by contradiction is the primary mechanism by which we begin to understand that there are such things as irrational numbers and what they are like. To begin this proof, all I claim to know about “the square root of 2,” which is normally written \sqrt{2}, is that (\sqrt{2})^2 = 2.

From here, we can now prove that \sqrt{2} is irrational.

Theorem: The square root of 2 is not equal to any rational number.

Proof: Suppose that the claim is false, that is, that \sqrt{2} actually is a fraction. Then we can write down that fraction using whole numbers a and b such that

\sqrt{2} = \dfrac{a}{b}.

Since fractions can always be reduced to lowest terms, we can take for granted that a/b is in lowest terms already (which means the whole numbers a and b share no common factor). Now, we want to see what we can learn about a and b. First, we can square both sides of our first equation to obtain the new equation

2 = \dfrac{a^2}{b^2}.

Multiply both sides of this by b2 to obtain the equation 2b2 = a2. Now, 2b2 is even, since it is a multiple of 2, so a2 is also even. Multiplying a number by itself does not change its evenness/oddness, and therefore a must also be even. That means (definition of even numbers) that we can pick a new whole number c so that c is half of a, that is, 2c = a. Then a2= 4c2 must be true by squaring both a and 2c, and the equation from the beginning of the paragraph then shows is that b2 = 2c2. For the same reason as we have just used on a, the whole number b must be even as well. Since we have reasoned that a is also even, this means a and b share the common factor of 2, and so a/b is not in lowest terms. Therefore, the fraction a/b both is in lowest terms and is not in lowest terms. This is a contradictory statement, and so it must be the case that our initial starting point of \sqrt{2} = \dfrac{a}{b} is actually false. Therefore, there is no fraction equal to the square root of 2. So, our proof is now completed.

This way of thinking takes a lot of getting used to. To see more examples (and examples that are not directly math-related) the Latin term reductio ad absurdum refers to any logical process that uses this same structure – whether related to mathematics or not. Though very strange, this proof method is extremely useful, because sometimes (as is the case with the problem I have just solved) a claim that ‘there is no such-and -such’ is difficult to work with directly, whereas a claim that ‘there is a such-and-such’ gives you more information – in this case, we gained access to the numbers a and b and an equation which supposedly related them to one another, which helped us greatly.

As one learns more mathematics over time, it is very important to develop an intuition for what kinds of situations this method will work well for, as very often it makes problems enormously easier to solve.

2 thoughts on “Proof by Contradiction

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: