Proof Technique: Contradiction

As discussed in the previous section, when trying to prove a statement like $p \to q$, we can take an indirect approach by proving some other statement, logically equivalent to $p \to q$, is true. There, the indirect method we used was the contrapositive. In this section, we use the Rule of Contradiction to arrive at another indirect proof method.

The Underlying Argument

Consider some arbitrary statement $p$. Since the implication $(\neg p \to F_0) \to p$ is always true (as we saw in the section on Rules of Inference), we can write $(\neg p \to F_0) \Longrightarrow p$ — meaning it’s a valid rule of inference, representing the valid argument

Now suppose we’re trying to prove $\forall x\ [p(x) \to q(x)]$ for every element of some universe $\mathcal{U}$. Pick an arbitrarily chosen element $x_0 \in \mathcal{U}$. What happens if we assume $p(x_0) = 1$ and $q(x_0) = 0$ (meaning $\neg q(x_0) = 1$)? The implication $p(x_0) \to q(x_0)$ would be false. Let’s look at what happens in an argument where we assume both $p(x_0)$ and $\neg q(x_0)$ as premises: a truth table confirms that

which means the argument

is logically equivalent to the argument

Thus, in order to show $\forall x\ [p(x) \to q(x)]$, we could instead show $[p(x_0) \land \neg q(x_0)] \Longrightarrow F_0$ for our arbitrarily chosen $x_0$. This is the idea behind proof by contradiction: assume the negation of the desired conclusion as an additional premise, then show that doing so yields a contradiction.

Revisiting a Previous Theorem

Let’s once again revisit Theorem 2.13.11: “If $n^2$ is odd, then $n$ is odd.” To prove this by contradiction, we first identify our premises. $n^2$ being odd is one; but in a proof by contradiction, we also have the negation of the conclusion as a premise. Since the conclusion is “$n$ is odd,” its negation is “$n$ is not odd” — that is, “$n$ is even.” So our premises are:

Using the definitions of even and odd as usual: there’s an integer $a$ such that $n = 2a$. Squaring $n$:

Since $n^2$ is double whatever integer $b$ happens to be, $n^2$ is even. But this directly contradicts our premise that $n^2$ is odd! Thus, assuming $n$ is even yields a contradiction whenever we assume $n^2$ is odd — so $n$ can’t be even, and must be odd, as desired.

Over the past three sections, we’ve proven “if $n^2$ is odd, then $n$ is odd” in three different ways — directly, indirectly via the contrapositive, and indirectly via a contradiction. This is the versatility of mathematical logic: if we’re ever stuck trying to prove a theorem one way, we can try another tactic.

Some theorems are established in so many ways it’s hard to keep track of how many proofs exist — there are entire books dedicated to proofs of the Pythagorean Theorem alone. But not every theorem is so easily established in a variety of ways. Perhaps most infamous is Fermat’s Last Theorem: for over 350 years, mathematicians tried to either establish or disprove the statement that when $n > 2$, there are no integers $a$, $b$, $c$ (with $abc \neq 0$) satisfying $a^n + b^n = c^n$. A proof was eventually given by Andrew Wiles in the mid-1990s, requiring such abstract and sophisticated methods that there are entire graduate courses dedicated to studying it.

As you study more mathematics, you’ll collect ever more tools for proving theorems, or providing counter-examples. For now, let’s show some more results using the method of contradiction.

Numbers Can’t Be Both Even and Odd

Notice that in some of our previous proofs, we used the fact that if $n$ isn’t even, it must be odd. For example, the contrapositive proof that $n^2$ odd implies $n$ odd required us to assume that $n$ not being odd meant $n$ was even. We haven’t actually proven this — are there numbers that are both even and odd? Most readers already know none exist, and now we can prove it.

A few things worth pointing out about this proof. First, notice we used the letter $a$ when assuming $n$ was even, and $b$ when assuming $n$ was odd — not the same letter for both, since $n$ can’t simultaneously equal $2a$ and $2a + 1$ for the same value of $a$ (that would mean two consecutive integers are equal, which is absurd).

Second, when we reached the contradiction, we asserted it was the assumption of $n$ being odd that was the problem, not the assumption of $n$ being even. Remember, the hypothesis of the theorem is that $n$ is even — we’re only considering even integers, and testing what happens if $n$ was also assumed odd. Once we reach a contradiction, either the “even” assumption or the “odd” assumption must be faulty — but since $n$ being even is the hypothesis we’re given, it must be the “odd” assumption that’s at fault.

Finally, notice the contradiction we arrived at had nothing to do with $n$ being even or odd at all — it was about the number $1$. When using the contradiction method, the contradiction we arrive at may be about the hypothesis of the proposition being examined, or it might be some piece of previous knowledge that happens to show up. In some sense, every piece of knowledge we have can be used as a premise, it’s just that we don’t necessarily need — or want — to explicitly lay out every premise, or the statements of our theorems would become unwieldy.

Another Example