Skip to main content

Section 5.3 Proof by Contradiction

Subsection 5.3.1 Proof by Contradiction

Proof by contradiction is an indirect proof technique. It involves assuming the negation of the desired result, then doing some mathematical reasoning, and the concluding a contradiction. To prove a statement \(P\) by contradiction, the process is as follows:

  1. By contradiction, suppose \(P\) is false (that is, \(\neg P\) is true).

  2. Use a chain of implication, to imply a contradiction \(C\text{,}\) a statement that is always false

  3. Then, by the chain of implications, the implication \(\neg P \rightarrow C\) is true.

  4. Then, since \(C\) is false (it is a contradiction), this implies that \(\neg (\neg P) = P\) is true.

In latin, this method is called “reductio ad absurdum” meaning “reduction to absurdity”. Typically, we start a proof by contraction by “by contradiction”, “by way of contradiction” or simply “BWOC”. Then, by supposing or assuming a statement.

In the case where \(P\) is a conditional \(A \longrightarrow B\text{,}\) the negation of this is \(\neq (A \longrightarrow B) = A \land \neq B\text{.}\) Then, to start the proof, assume that \(A \land \neg B\) is true. That is, the hypothesis is true, but the conclusion is false.

Subsection 5.3.2 Basic Proofs by Contradiction

By contradiction, suppose \(n\) is the largest integer/real number. Then, \(n + 1\) is also an integer/real number and \(n + 1 > n\text{,}\) which contradicts our assumption that \(n\) is the largest integer/real number.

By contradiction, suppose \(p\) is the smallest positive rational number. Then, there exists \(a, b \in \mathbb{Z}, b \neq 0\text{,}\) such that \(p = \frac{a}{b}\text{.}\) Then, since \(0 \lt \frac{1}{2} \lt 1\text{,}\) by multiplying all three sides by \(p\text{,}\) we have,

\begin{align*} 0 \amp \lt \frac{p}{2} \lt p\\ 0 \amp \lt \frac{a}{2b} \lt p \end{align*}

Since \(a, 2b \in \mathbb{Z}\text{,}\) and \(b \neq 0\) so \(2b \neq 0\text{,}\) \(\frac{p}{2}\) is rational and is smaller than \(p\text{,}\) which contradicts our assumption that \(p\) is the smallest rational number.

By contradiction, suppose \(p\) is the smallest real number. Then,

\begin{equation*} 0 \lt \frac{p}{2} \lt p \end{equation*}

Since \(\frac{p}{2} > 0\) and \(\frac{p}{2} \lt p\text{,}\) so \(\frac{p}{2}\) is positive and smaller than \(p\text{,}\) which contradicts our assumption that \(p\) is the smallest real number.

By contradiction, suppose \(r + x\) is rational, \(r + x \in \mathbb{Q}\text{.}\) Then, there exists \(a, b, c, d \in \mathbb{Z}, b, d \neq 0\) such tha t\(r = \frac{c}{d}\) and \(r + x = \frac{a}{b}\text{.}\) Then,

\begin{align*} x \amp = (r + x) - r\\ \amp = \frac{a}{b} - \frac{c}{d}\\ x \amp = \frac{ad - bc}{bd} \end{align*}

Since \(ad - bc, bd \in \mathbb{Z}, bd \neq 0\text{,}\) this implies that \(x \in \mathbb{Q}\text{,}\) which contradicts the assumption that \(x\) is irrational.

Alternatively, using the property that the sum/difference of two rational numbers is rational, we have that \(x = (r + x) - r\) is rational, contradicting our assumption that \(x\) is irrational.

By contradiction, suppose \(rx\) is rational, \(rx \in \mathbb{Q}\text{.}\) Then, there exists \(a, b, c, d \in \mathbb{Z}, b, d \neq 0\text{,}\) such that \(r = \frac{a}{b}, rx = \frac{c}{d}\text{.}\) Then,

\begin{equation*} x = \frac{rx}{r} = \frac{\frac{c}{d}}{\frac{a}{b}} = \frac{bc}{ad} \end{equation*}

Since \(bc, ad \in \mathbb{Z}\) and \(ad \neq 0\text{,}\) this implies that \(x \in \mathbb{Q}\text{,}\) which contradicts the assumption that \(x\) was irrational.

By contradiction, suppose that \(x \in \mathbb{Q}\) but \(\frac{1}{x} \in \mathbb{R} \setminus \mathbb{Q}\text{.}\) Then, there exists \(a, b \in \mathbb{Z}, b \neq 0\text{,}\) such that \(x = \frac{a}{b}\text{.}\) Then,

\begin{equation*} \frac{1}{x} = \frac{1}{\frac{a}{b}} = \frac{b}{a} \in \mathbb{Q} \end{equation*}
which contradicts our assumption that \(\frac{1}{x} \in \mathbb{R} \setminus \mathbb{Q}\text{.}\)

Subsection 5.3.3 Tips for Proof by Contradiction

Clearly state the fact, theorem, or property that is being contradicted at the end, rather than just ending with “, a contradiction.”

Subsection 5.3.4 Bad Proofs by Contradiction

Proof my contradiction can be overused. In general, if a direct proof is available, it is considered poor mathematics to use a proof by contradiction.

Suppose we want to prove a statement \(P\) is true. By contradiction, we suppose \(P\) is false. Then, we show that \(P\) is true. This leads to a contradiction, as \(P\) cannot be both true and false. Thus, \(P\) is true.

This is a poor proof because the the assumption that \(P\) is false adds nothing to the proof. Instead, we could have just shown that \(P\) is true, using a direct proof.

Subsection 5.3.5 Square Root of 2 (\(\sqrt{2}\)) is Irrational (Hippasus Death)

Here, we will prove that the real number \(\sqrt{2}\) is irrational, possibly one of the most well known proofs by contradiction. In ancient Greece (in 5th century BC), the Pythagoreans believed that all numbers were rational. To them, the term “number” meant rational number. However, Hippasus, a member of the Pythagoreans, was the first to publicly reveal that the square root of 2, was irrational. Here, the square root of 2 represented the length of the hypotenuse of a right triangle with side lengths 1. The Pythagoreans did not accept \(\sqrt{2}\) as a number, and supposedly, he was thrown off a boat and drowned. However, whether this actually happened is controversial.

By contradiction, suppose \(\sqrt{2}\) is rational, so there exists \(a, b \in \mathbb{Z}, b \neq 0\text{,}\) such that \(\sqrt{2} = \frac{a}{b}\text{.}\) Further, \(a, b\) can be chosen to have no common factors, so that \(\frac{a}{b}\) is in lowest terms. Then, we will square both sides to convert the equation to an equation between integers,

\begin{align*} 2 \amp = \frac{a^2}{b^2}\\ 2b^2 \amp = a^2 \end{align*}

Then, since \(b^2 \in \mathbb{Z}\text{,}\) \(a^2\) is even, and this implies that \(a\) is even. Thus, there exists \(k \in \mathbb{Z}\) such tha \(a = 2k\text{.}\) Then,

\begin{align*} 2b^2 \amp = (2k)^2\\ 2b^2 \amp = 4k^2\\ b^2 \amp = 2k^2 \end{align*}

Then, since \(k^2 \in \mathbb{Z}\text{,}\) \(b^2\) is even, and so \(b\) is even. However, \(a\) and \(b\) cannot both be even, as otherwise then they share a common factor of 2, contradicting the assumption that \(a\) and \(b\) share no common factors.

Note why the assumption that \(a\) and \(b\) have no common factors works here. Say we write \(a = 2c\text{,}\) \(b = 2d\text{,}\) for some \(c, d \in \mathbb{Z}, d \neq 0\text{.}\) Then, we have,

\begin{equation*} \sqrt{2} = \frac{a}{b} = \frac{2c}{2d} = \frac{c}{d} \end{equation*}

Then, we can continue a similar process and find that both \(c\) and \(d\) must be even. This process can be repeated indefinitely. Thus, if \(\sqrt{2}\) is rational, then its it could always be written as a rational number with smaller and smaller integers. However, this is impossible, since integers cannot be divided indefinitely, and so this is a contradiction. This method of reasoning is called proof by infinite descent.

Alternatively, the above reasoning proves that if \(\sqrt{2}\) is rational, then it does not have a representation in lowest terms. However, is it a fact that all rational numbers have a (unique) representation \(\frac{a}{b}\) in lowest terms.

Subsection 5.3.6 Square Roots of Other Numbers are Irrational

The reasoning for proving that \(\sqrt{2}\) is irrational can be used to prove that other radicals are irrational.

By contradiction, suppose \(\sqrt{3}\) is rational, so there exists \(a, b \in \mathbb{Z}, b \neq 0\text{,}\) such that \(\sqrt{3} = \frac{a}{b}\text{,}\) where \(a\) and \(b\) have no common factors. Then,

\begin{align*} 3 \amp = \frac{a^2}{b^2}\\ 3b^2 \amp = a^2 \end{align*}

Then, \(3 \mid a^2\text{.}\) Then, this implies that \(3 \mid a\) (this is by Euclid's lemma). Then, \(a = 3k\) for some \(k \in \mathbb{Z}\text{.}\) Then,

\begin{align*} 3b^2 \amp = (3k)^2\\ 3b^2 \amp = 9k^2\\ b^2 \amp = 3k^2 \end{align*}

Then, \(3 \mid b^2\text{,}\) so again, this implies that \(3 \mid b\text{.}\) Then, \(a\) and \(b\) share a common factor of 3, contradicting the assumption that they share no common factors.

Notice the similar themes between the proofs for \(\sqrt{2}\) and \(\sqrt{3}\text{.}\) Use proof by contradiction, square both sides, and so on.

The key element of this proof is Euclid's lemma, which says that if a prime number \(p\) divides a product \(ab\text{,}\) then \(p\) divides \(a\) or \(p\) divides \(b\text{.}\) Then, for \(a = b\text{,}\) this says that if \(p\) divides \(a^2\text{,}\) then \(p\) divides \(a\text{.}\)

Notice that this property does not hold if \(p = 4\) as it is not prime. In this case, if \(\sqrt{4} = \frac{a}{b}\text{,}\) then we have,

\begin{align*} 4 \amp = \frac{a^2}{b^2}\\ 4b^2 \amp = a^2 \end{align*}

This implies that \(4 \mid a^2\text{,}\) however, this does not imply that \(4 \mid a\text{.}\) For example, \(4 \mid 36\text{,}\) but \(4 \nmid 6\text{.}\)

By contradiction, suppose \(\sqrt{p}\) is rational, so there exists \(a, b \in \mathbb{Z}, b \neq 0\) such that \(\sqrt{p} = \frac{a}{b}\text{,}\) where \(a\) and \(b\) share no common factors. Then, \(p b^2 = a^2\text{,}\) so by Euclid's lemma, \(p \mid a\text{,}\) so \(a = kp\) for some \(k \in \mathbb{Z}\text{.}\) Then,

\begin{align*} pb^2 \amp = (kp)^2\\ pb^2 \amp = k^2 p^2\\ b^2 \amp = k^2 p \end{align*}

Then, \(p \mid b^2\text{,}\) so by Euclid's lemma, \(p \mid b\text{.}\) Thus, \(a\) and \(b\) share a common factor of \(p\text{,}\) contradicting the assumption that they share no common factors.

First, \(\sqrt{12} = 2 \sqrt{3}\text{.}\) Then, \(2\) is rational and \(\sqrt{3}\) is irrational, and the product of a rational and irrational is irrational, so \(\sqrt{12}\) is irrational.

By contradiction, suppose \(\sqrt{12}\) is rational, so that there exists \(a, b \in \mathbb{Z}, b \neq 0\text{,}\) such that \(\sqrt{12} = \frac{a}{b}\text{,}\) and \(a\) and \(b\) share no common factors. Then, \(a^2 = 12b^2 = 2(6b^2)\text{,}\) and so \(a^2\) is even, and so \(a\) is even. Then, there exists \(k \in \mathbb{Z}\) such that \(a = 2k\) and so,

\begin{align*} 12b^2 \amp = (2k)^2\\ 12b^2 \amp = 4k^2\\ 3b^2 \amp = k^2 \end{align*}

Since \(a\) and \(b\) share no common factors, \(b\) must be odd (otherwise, \(a\) and \(b\) would share the common factor of 2). Then, \(3b^2\) is the product of 3 odd numbers, and so is odd. This implies that \(k^2\) is also odd, and so \(k\) is odd. Then, there exists \(m, n \in \mathbb{Z}\) such that \(b = 2m + 1\) and \(k = 2n + 1\text{.}\) Then,

\begin{align*} 3(2m + 1)^2 \amp = (2n + 1)^2\\ 12m^2 + 12m + 3 \amp = 4n^2 + 4n + 1\\ 4(n^2 + n - 3m^2 - 3m) \amp = 2 \end{align*}

Then, this is a contradiction, because \(4(n^2 + n - 3m^2 - 3m)\) is a multiple of 4, which cannot be equal to 2.

Exercise.

Subsection 5.3.7 Some Logarithms are Irrational

Recall that \(\log_b{x}\) is defined to be the number \(y\) such that \(b^y = x\text{.}\)

By contradiction, suppose \(\log_{2}{3}\) is rational, so \(\log_{2}{3} = \frac{a}{b}\) for some \(a, b \in \mathbb{Z}, b \neq 0\text{.}\) Then,

\begin{align*} \log_{2}{3} \amp = \frac{a}{b}\\ 3 \amp = 2^{a/b} \amp\amp \text{definition of logarithm}\\ 3^b \amp = 2^a \end{align*}

Then, \(3^b\) is an integer power of 3, a product of odd numbers, and so is odd. Similarly, \(2^a\) is an integer power of 2, a product of even integers, and so is even. This contradicts the fact that an even integer cannot be equal to an odd integer.

Subsection 5.3.8 An Integer Cannot Divide Two Consecutive Numbers

By contradiction, suppose that \(a \mid b\) and \(a \mid (b + 1)\text{.}\) Then, there exists \(m, n \in \mathbb{Z}\) such that \(b = ma\) and \(b + 1 = na\text{.}\) Then, consider the difference of these two equations,

\begin{align*} na - ma \amp = (b + 1) - b\\ a(n - m) \amp = 1 \end{align*}

Then, since \(a, n-m \in \mathbb{Z}\text{,}\) the product \(a(n - m)\) is the product of two integers. If the product of two integers is equal to 1, then each integer must be either 1 or \(-1\text{.}\) Thus, \(a = \pm 1\text{,}\) contradicting the assumption that \(a \geq 2\text{.}\)