Contrapositive and Contradiction
Proving a statement by way of its negation
Adapted from Kameron Decker Harris’s Fall 2026 lecture notes “Contrapositive Proof” and “Proof by Contradiction”, which are typed transcriptions of Scott Wehrwein’s Spring 2025 handwritten lecture notes. These come from those notes:
- the definition of congruence modulo \(n\), and the point that it is not the mod operator;
- the human and mammal illustration of a contrapositive;
- the example of a product not divisible by \(5\);
- the truth table showing why a proof by contradiction works;
- the outlines of a proof by contrapositive, a proof by contradiction, and a proof of a conditional by contradiction;
- the definition and examples of a prime number, and the fact that every integer above one has a prime divisor;
- the statement that \(\sqrt{2}\) is irrational (the proof here is different);
- Euclid’s proof that there are infinitely many primes.
The exercises are new.
The definitions of the contrapositive, proof by contrapositive, proof by contradiction, and rational and irrational numbers, their examples of a proof by contradiction and of rational and irrational numbers, and the theorem that a conditional is equivalent to its contrapositive, are included from the mathematics prerequisites notes, so they read the same in both places.
1 Congruence modulo \(n\)
2 Proof by contrapositive
Proof. By the definition of implies, \(P \Rightarrow Q\) is false exactly when \(P\) is true and \(Q\) is false. By the same definition, \(\neg Q \Rightarrow \neg P\) is false exactly when \(\neg Q\) is true and \(\neg P\) is false, that is, exactly when \(Q\) is false and \(P\) is true. So the two propositions are false in the same row of a truth table and true in the other three, which is Definition: Logically equivalent.
3 Proof by contradiction
Proof. \(C \land \neg C\) is false in every row (Definition: And, Definition: Not), so it is a contradiction (Definition: Contradiction). So, by Definition: Implies, \(\neg P \Rightarrow (C \land \neg C)\) is true exactly in the rows where \(\neg P\) is false, which are the rows where \(P\) is true:
| \(P\) | \(C\) | \(\neg P\) | \(C \land \neg C\) | \(\neg P \Rightarrow (C \land \neg C)\) |
|---|---|---|---|---|
| T | T | F | F | T |
| T | F | F | F | T |
| F | T | T | F | F |
| F | F | T | F | F |
The first and last columns match in every row (Definition: Logical equivalence).
4 Irrational numbers
Proof. Suppose, for contradiction, that \(\sqrt{2}\) is rational (Definition 5). Then \(\sqrt{2} = \frac{a}{b}\) for some integers \(a\) and \(b\) with \(b \ne 0\). Since \(\sqrt{2} > 0\), we can take \(a\) and \(b\) positive (if \(b < 0\), replace \(a\) and \(b\) with \(-a\) and \(-b\)). So the set of positive integers \(b\) for which \(\sqrt{2}\, b\) is an integer has an element, and by Remark 5 it has a smallest element. Let \(b\) be that smallest element, and let \(a = \sqrt{2}\, b\), a positive integer.
By Solution 6, \(b < a < 2b\), so \(b' = a - b\) is an integer with \(0 < b' < b\). Let \(a' = 2b - a\), also an integer. Then
\[ \begin{aligned} \sqrt{2}\, b' &= \sqrt{2}\, (a - b) && \text{(definition of } b' \text{)} \\&= \sqrt{2}\, a - \sqrt{2}\, b && \text{(distributive law)} \\&= \sqrt{2}\, \sqrt{2}\, b - a && \text{(substitute } a = \sqrt{2}\, b \text{ in the first term, and } \sqrt{2}\, b = a \text{ in the second)} \\&= 2b - a && \text{(} \sqrt{2}\, \sqrt{2} = 2 \text{)} \\&= a'. && \text{(definition of } a' \text{)} \end{aligned} \]
So \(b'\) is a positive integer for which \(\sqrt{2}\, b'\) is an integer, and \(b' < b\). That contradicts the choice of \(b\) as the smallest such integer. So \(\sqrt{2}\) is not rational.
5 Infinitely many primes
Proof. Suppose, for contradiction, that there are only finitely many primes, and list them all as \(p_1, p_2, \ldots, p_k\). The list is not empty, because \(2\) is prime. Let
\[ N = p_1 p_2 \cdots p_k + 1. \]
Each \(p_i \ge 2\), so \(N \ge 3\), and by Remark 6 some prime \(p\) divides \(N\): \(N = p s\) for some integer \(s\). The list holds every prime, so \(p\) is one of \(p_1, \ldots, p_k\), and so \(p\) also divides their product: \(p_1 p_2 \cdots p_k = p t\) for some integer \(t\). Then
\[ \begin{aligned} 1 &= N - p_1 p_2 \cdots p_k && \text{(definition of } N \text{)} \\&= p s - p t && \text{(substitute both products)} \\&= p (s - t). && \text{(distributive law, read from right to left)} \end{aligned} \]
Since \(s - t\) is an integer (Remark: Facts about integers used without proof), \(p \mid 1\). But \(p \ge 2\), and \(p \cdot 0 = 0 < 1 < p = p \cdot 1\), so no integer \(c\) has \(p c = 1\), and \(p \nmid 1\). That is a contradiction, so there are infinitely many primes.