Skip to main content

Section 1.11 Proof by Contradiction

Suppose we have a statement \(\phi\) that we suspect is false. How can we prove that? One approach is to leverage a statement \(\psi\) that we know is false, and try to prove that \(\phi \implies \psi\text{.}\) Remember, the statement \(\quine{\phi \implies \psi}\) is the same thing as \(\quine{\neg{\phi} \vee \psi}\text{,}\) so if we know that \(\psi\) is false, then the only alternative is that \(\phi\) is false. This is called Proof by Contradiction.

We begin with the forward direction; that is, we shall show first that if \(\neg(\phi \vee \psi)\text{,}\) then \((\neg{\phi}) \wedge (\neg{\psi})\text{.}\) So let us assume \(\neg(\phi \vee \psi)\text{.}\) We aim to prove that both \(\neg{\phi}\) and \(\neg{\psi}\text{.}\)

In other words, we need to show that \(\phi\) is false. So we want to prove that \(\phi\) implies something we know to be false. In our case, we are assuming that \(\neg(\phi \vee \psi)\text{,}\) so we know \(\quine{\phi \vee \psi}\) to be false. This is great news: if \(\phi\) is true, then certainly \(\quine{\phi \vee \psi}\) is true. That is, \(\phi \implies (\phi \vee \psi)\text{.}\) Since we know that \(\quine{\phi \vee \psi}\) is false, that implies that \(\phi\) is false as well. Thus \(\quine{\neg{\phi}}\) holds. Similarly, \(\psi \implies (\phi \vee \psi)\text{,}\) but that contradicts our assumption that \(\quine{\neg(\phi \vee \psi)}\) is true. Thus \(\quine{\neg{\psi}}\) holds.

Now let's reverse directions; that is, let's show that if \((\neg{\phi}) \wedge (\neg{\psi})\text{,}\) then \(\neg(\phi \vee \psi)\text{.}\) So let us assume that both \(\neg{\phi}\) and \(\neg{\psi}\text{.}\) We aim to prove that \(\neg(\phi \vee \psi)\text{.}\)

In other words, we need to show that \(\quine{\phi \vee \psi}\) is false. If \(\phi \vee \psi\text{,}\) there are two options:

  • One possibility is that \(\phi\) is true. But this would contradict our assumption that \(\quine{\neg{\phi}}\) is true.

  • So that leaves the other possibility, which is that \(\psi\) is true. But that contradicts our other assumption, that \(\quine{\neg{\psi}}\) is true.

Either way, we arrive at a contradiction, and so \(\quine{\phi\vee \psi}\) is indeed false.

As a quick corollary of this, we deduce that

\begin{equation*} \neg(\phi \wedge \psi) \iff \neg((\neg\neg\phi) \wedge (\neg\neg\psi)) \iff \neg\neg((\neg{\phi}) \vee (\neg{\psi})) \iff ((\neg{\phi}) \vee (\neg{\psi}))\text{.} \end{equation*}

Here's another example of proof by contradiction.

Let's say we want to prove that \(\sqrt{3}\lt 1+\sqrt{2}\text{.}\) For the moment, let's not worry about how to prove that these numbers really exist; we'll get to that. All we're going to use about \(\sqrt{2}\) and \(\sqrt{3}\) is that they are positive numbers \(a \) and \(b \) (respectively) such that \(a^2=2\) and \(b^2=3\text{.}\)

Solution.

Let's prove this by contradiction: we assume instead that \(\sqrt{3}\geq 1+\sqrt{2}\text{,}\) and we aim to deduce something we know to be false. If we square both sides of the inequality we assumed, we obtain

\begin{equation*} 3\geq (1+\sqrt{2})^2=1+2\sqrt{2}+2=3+\sqrt{2}>3\text{,} \end{equation*}

which is definitely false. We have thus shown by contradiction that \(\sqrt{3}\lt 1+\sqrt{2}\text{.}\)

Why didn't we do the same computations but with the original inequality? If we assumed \(\sqrt{3}\lt 1+\sqrt{2}\text{,}\) then squaring both sides gives

\begin{equation*} 3\lt (1+\sqrt{2})^2=1+2\sqrt{2}+2=3+\sqrt{2} \end{equation*}

which is certainly true, but this doesn't help us. We started by assuming the thing we wanted to prove and then deducing something we know to be true. if \(\phi\) is the statement “\(\sqrt{3}\lt 1+\sqrt{2}\)” and \(\psi\) is the statement “\(3\lt 3+\sqrt{2}\text{,}\)” then what we just showed was \(\phi\implies \psi\text{,}\) but that can't help us conclude that \(\phi\) is true. In our proof of \(\phi\) by contradiction, we assumed first that \(\phi\) is false, and then we deduce the statement \(\chi\text{:}\) “\(3>3\text{,}\)” which we know perfectly well is false. Since \(\chi\) is false, the implication \(\neg{\phi} \implies \chi\) ensures that \(\neg{\phi}\) has to be false as well; in other words, \(\phi\) is true.