Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 1.4.4 Proof by contradiction

Let \(s\) and \(r\) be propositions. Recall that \(r\land\lnot r\) is a contradiction. In particular, \(r\land\lnot r\) is always false. If we can prove that \(\lnot s\implies (r\land\lnot r)\) is true, then \(\lnot s\) must be false. In this case, \(s\) must be true.
🔗
Unwinding that, we get a technique known as proof by contradiction . Namely, we can prove \(s\) is true by producing a direct proof of \(\lnot s \implies (r\land\lnot r)\text{.}\) That is, to prove \(s\) is true, we start by assuming \(\lnot s\) is true and try to reach a contradiction.
🔗
For the next example we need the following definition.
🔗

Definition 1.4.4.2.

A number \(r\) is rational if there exists integers \(p\) and \(q\) with \(q \neq 0\) such that \(r = \frac{p}{q}\text{.}\)
🔗
We say that a rational number \(\frac{p}{q}\) is written in lowest terms when there exists no integer \(d\) with \(d>1\text{,}\) \(d\ne p\text{,}\) and \(d\ne q\) and no integers \(k\) and \(l\) such that \(p=d\cdot k\) and \(q=d\cdot l\text{.}\)
🔗
A number that is not rational is called irrational.
🔗
🔗

Example 1.4.4.3. The square root of two is irrational.

Prove that \(\sqrt{2}\) is irrational.
🔗
Answer.
We proceed by contradiction. Suppose \(\sqrt{2}\) is rational. Then there exists integers \(p\) and \(q\) , with \(q \neq 0\) such that \(\sqrt{2} = \frac{p}{q}\text{.}\) Note that we can arrange that the fraction is in lowest terms by canceling common factors, so without loss of generality assume that \(p\) and \(q\) have no common factors.
🔗
Squaring both sides of \(\sqrt{2} = \frac{p}{q}\) yields \(2 = \frac{p^2}{q^2}\text{.}\)
🔗
Multiplying both sides by \(q^2\) we get \(2q^2 = p^2\text{.}\) Because \(q^2\) is an integer this means that \(p^2\) is even. It follows with Example 1.4.3.2 that \(p\) is even. So there exists an integer \(k\) such that \(p =2k\text{.}\)
🔗
With \(p=2k\) we get \(2q^2 = (2k)^2 = 4k^2\text{.}\) Dividing by \(2\text{,}\) we obtain \(q^2 =2k^2\) which implies that \(q^2\) is even. Again, it follows with Example 1.4.3.2 that \(q\) is even.
🔗
From our assumption that \(\sqrt{2}\) is a rational number we have deduced that \(p\) and \(q\) must be even. This contradicts our assumption that \(p\) and \(q\) have no common factor.
🔗
Thus \(\sqrt{2}\) cannot be a rational number, which means that \(\sqrt{2}\) is irrational.
🔗
🔗
🔗

Example 1.4.4.4. No rational number.

Use a proof by contradiction to show that there is no rational number \(r\) for which \(r^3 + r + 1 = 0\text{.}\)
🔗
Answer.
Suppose there is a rational number \(r = \frac{a}{b}\) such that \(r^3 + r + 1 = 0\) , where we write \(\frac{a}{b}\) is lowest terms so that \(a\) and \(b\) have no common factors. Then
\begin{equation*} \left(\frac{a}{b}\right)^3 + \frac{a}{b} + 1 = 0. \end{equation*}
Multiplying both sides by \(b^3\) , we get
\begin{equation*} a^3 + ab^2 + b^3 = 0. \end{equation*}
There are four cases to consider, depending on the parity (even/odd) of \(a\) and \(b\text{.}\)
\(a\) and \(b\) both even
🔗
This case contradicts that \(\frac{a}{b}\) is in lowest terms, because they have the common factor \(2\text{.}\)
🔗
\(a\) and \(b\) both odd
🔗
Then \(a^3\text{,}\) \(ab^2\text{,}\) and \(b^3\) are all odd. The sum of three odd numbers is odd and thus cannot be equal to \(0\) which is even.
🔗
\(a\) is even \(b\) is odd
🔗
Then \(a^3\) and \(ab^2\) are even, and \(b^3\) is odd. The sum of two even integers and an odd integer is odd thus cannot be equal to \(0\) which is even.
🔗
\(a\) is odd \(b\) is even
🔗
Then \(a^3\) is odd, and \(ab^2\) and \(b^3\) are even. The sum of an odd integer and two even integers is odd thus cannot be equal to \(0\) which is even.
🔗
Since all four cases yield a contradiction, there is not rational number \(r\) such that \(r^3 + r + 1 = 0\text{.}\)
🔗
🔗
🔗
We give an alternative proof of the result from Example 1.4.0.18.
🔗

Example 1.4.4.5. If \(x^2+2x+1\) is odd then \(x\) is even by contradiction.

Prove by contradiction that if for an integer \(x\) we have \(x^2+2x+1\) is odd then \(x\) is even.
🔗
Answer.
We assume that \(x^2+2x+1\) is even then \(x\) is even and show that this leads to a contradiction.
🔗
As \(x\) is even by Definition 1.4.1.1 there exists an integer \(k\) such that \(x=2k\text{.}\) Then
\begin{equation*} x^2+2x+1=(2k)^2+2(2k)+1=4k^2+4k+1=2(2k^2+2k)+1. \end{equation*}
Because \(2k^2+2k\) is the sum of products of integers it is an integer. Thus by Definition 1.4.1.5 we have that \(x^2+2x+1\) is odd. This contradicts our assumption that \(x^2+2x+1\) is even. So \(x^2+2x+1\) must be odd which concludes our proof.
🔗
🔗
🔗
Figure 1.4.4.6. Principle of Explosion by Randal Munroe (https://xkcd.com/704/). You want me to pick up waffle cones? Oh, right, for the wine. One sec, let me just derive your son’s credit card number and I’ll be on my way.
🔗
🔗
PrevTopNext