Section 3.2 Proof by Contradiction
Guiding Questions.
In this section, we’ll seek to answer the questions:
What is a proof by contradiction?
Why is a proof by contradiction valid?
What are some examples of proof by contradiction, and why might we want to use this technique?
Another proof technique relies on the assumption that a statement \(Q\) cannot be both true and false. The technique we describe in this section is an example of indirect proof known as proof by contradiction.
Proof by Contradiction.
To prove the statement
\(P\Rightarrow Q\) by contradiction, we assume
\(P\) and
\(\neg Q\) (which places us in row 2 of
Table 1.2.14), and thus that
\(P\Rightarrow Q\) is false. We proceed deductively until we contradict some assumption or known fact. Thus, our original assumption of
\(\neg Q\) is false, which means
\(Q\) and thus
\(P\Rightarrow Q\) are both true.
We’ll begin with an example.
If ten ducks are paddling in four ponds, then some pond must contain at least three paddling ducks.
Proof.
Suppose ten ducks are paddling in four ponds, but no pond contains at least three paddling ducks. This means that each of the four ponds contains at most two ducks.
That is, the first pond contains at most two ducks, the second pond contains at most two ducks, the third pond contains at most two ducks, and the fourth pond contains at most two ducks, for a total of (at most!)
\(2+2+2+2 = 8\) ducks. This contradicts the given assumption that ten ducks are paddling in four ponds. Thus, there must be a pond with at least three ducks.
Let’s consider a different example now, where a direct proof would be extremely difficult (or impossible).
Theorem 3.2.2, which was known to the
Pythagoreans, states that
\(\sqrt{2}\) is irrational, i.e., that there are no integers
\(p\) and
\(q\ne 0\) such that
\(\sqrt{2} = \frac{p}{q}\text{.}\)
Theorem 3.2.2.
The real number \(\sqrt{2}\) is irrational.
Proof.
Suppose that \(\sqrt{2}\) is rational, i.e., there exist integers \(p, q\) with \(q\ne 0\) such that \(p,q\) have no common factors (i.e,. \(p/q\) is in “lowest terms”) and \(\sqrt{2} = p/q\text{.}\)
Begin by squaring both sides to obtain
\(2 = \frac{p^2}{q^2}\text{,}\) which we may rewrite as
\(2q^2 = p^2\text{.}\) Since
\(q^2\) is an integer, this means that
\(p^2\) is even. We may conclude (with a nod to
Theorem 3.1.3 and
Theorem 3.1.5) that
\(p\) is even, and write
\(p = 2k\) for some
\(k\in\Z\text{.}\) We thus obtain
\begin{equation*}
2q^2 = (2k)^2 = 4k^2,
\end{equation*}
and canceling a 2 from each side yields \(q^2 = 2k^2\text{.}\) By an argument similar to the above, \(q\) is even. But here arises a contradiction, as we assumed \(p\) and \(q\) have no common factors, yet we have proved they are both divisible by 2.
Therefore, no such \(p/q\) exists, and \(\sqrt{2}\) is irrational.
Establish the following theorems via a proof by contradiction.
Theorem 3.2.3.
Suppose \(m,n\in\Z\) such that \(m\cdot n\) is odd. Then both \(m\) and \(n\) are odd.
Theorem 3.2.4 (Dirichlet). The Pigeonhole Principle.
Suppose \(n+1\) pieces of mail are delivered to \(n\) mailboxes. Then there is a mailbox that contains at least two pieces of mail.
Theorem 3.2.5.
There is no rational number \(r\) such that \(r^2 = 3\text{.}\)
Proofs by contradiction are fun! But sometimes they can get a bit ... silly.
Theorem 3.2.6.
Let \(m\) be an even integer. Then \(m^2\) is even.
Proof.
Suppose
\(m\) is even but, for a contradiction, that
\(m^2\) is odd. Then there exist integers
\(j,k\) such that
\(m = 2j\) and
\(m^2 = 2k+1\text{.}\) We observe that
\(m^2 = m\cdot m = (2j) \cdot (2j) = 2(2j^2) = 2k+1\text{.}\) Thus,
\(m^2\) is both even and odd, in clear violation of
Axiom 3.1.9. We therefore find that
\(m^2\) cannot be odd, and must be even.
Activity 3.2.7.
Proofs by contradition are useful when showing that something cannot exist: you assume that it does, and reach a contradiction.
Theorem 3.2.8 (Ted Sundstrom).
There do not exist integers \(a,b\) such that \(b^2 = 4a + 2\text{.}\)
Definition 3.2.9.
The degree sequence of a graph is a sequence of the degrees of the vertices in the graph, including any repetitions, and listed in decreasing order.
For example, the degree sequence of the graph in
Figure 2.1.2 is
\((2,2,1,1)\text{,}\) while the degree sequence of the graph in
Figure 2.1.3 is
\((2,2,2,0)\text{.}\)
Theorem 3.2.10.
There is no graph with the degree sequence \((5,5,5,4,4,3,3)\text{.}\)
Theorem 3.2.11.
There is no graph with the degree sequence \((7,6,5,4,3,2,1)\text{.}\)
Theorem 3.2.12.
There is no graph with the degree sequence \((6,5,4,3,2,2,0)\text{.}\)
