Proof by Contradiction

This document presents some examples of proofs by contradiction. The first is a generic demonstration of the technique:

Proof. We will prove by contradiction that for all integers \(n\), if \(n \equiv 1 \pmod {2}\) then \(n \not \equiv 2 \pmod {4}\). We assume for the sake of contradiction that \(n\) is an integer such that \(n \equiv 1 \pmod {2}\) and \(n \equiv 2 \pmod {4}\). Since \(n \equiv 1 \pmod {2}\), there is some integer \(a\) such that

\begin{align} n - 1 &= 2a \nonumber \\ n &= 2a + 1 \end{align}

Similarly, since \(n \equiv 2 \pmod {4}\), there is some other integer \(b\) such that

\begin{align} n &= 4b + 2 \nonumber \\ &= 2(2b+1) \end{align}

From equation (1), we see that \(n\) is odd, and from equation (2) that \(n\) is even. Since a number can’t be both odd and even, this is a contradiction. Since the assumption that \(n \equiv 1 \pmod {2}\) and \(n \equiv 2 \pmod {4}\) leads to a contradiction, we have proven by contradiction that for all integers \(n\), if \(n \equiv 1 \pmod {2}\) then \(n \not \equiv 2 \pmod {4}\). □

The next example is based on a classic proof by contradiction, namely a proof that \(\sqrt {2}\) is irrational. Our example adapts the ideas from that proof to proving that \(\sqrt {6}\) is also irrational:

Proof. We assume that \(x\) is a real number and \(x^2 = 6\), and will prove by contradiction that \(x\) is irrational. So assume for the sake of contradiction that not only is \(x\) a real number and \(x^2 = 6\), but that \(x\) is rational. Since \(x\) is rational, it can be written as

\begin{equation} x = \frac {m}{n} \end{equation}

where \(m\) and \(n\) are integers, \(n \ne 0\), and \(m\) and \(n\) have no common factors besides \(1\).

Squaring both sides of (3) gives

\begin{align} 6 &= \frac {m^2}{n^2} \nonumber \\ 6n^2 &= m^2 \end{align}

\begin{equation*} m^2 = 2(3n^2) \end{equation*}

which means that \(m\) must be even. In other words \(m = 2p\) for some integer \(p\).

Plugging \(2p\) into equation (4) in place of \(m\) gives

\begin{align*} 6n^2 &= (2p)^2 \\ &= 4p^2 \end{align*}

\begin{equation*} 3n^2 = 2p^2 \end{equation*}

meaning that \(3n^2\) is even. Now, if \(n^2\) were odd, \(3n^2\) would also be odd, so \(n^2\) must be even.

We now arrive at a contradiction, because if \(m\) and \(n\) are both even, they have a common factor of \(2\), but we defined them to have no such common factor. Since we have showed that the assumption that \(x\) is rational leads to a contradiction, any square root of \(6\) must in fact be irrational. □