Chapter 3: Methods of Proof¶
How mathematicians show that something must be true
Learning outcomes
After this chapter you should be able to:
- use precise definitions (even, odd, divides, rational, prime) as the starting point of a proof;
- write direct proofs, proofs by contraposition and proofs by contradiction, and choose between them;
- prove statements by cases, prove biconditionals, and prove that several statements are equivalent;
- give constructive and non-constructive existence proofs and uniqueness proofs;
- disprove a universal statement with a counterexample;
- recognise common errors in proofs and write proofs that a reader can check line by line.
3.1 What a proof is¶
A proof is an argument that establishes, beyond any doubt, that a statement is true. It starts from things already accepted (definitions, axioms, and results proved earlier) and reaches the statement by steps each of which follows from what came before by the rules of logic of Chapters 1 and 2. A statement that has been proved is a theorem. A small theorem used to prove a larger one is a lemma, and a result that follows easily from a theorem is a corollary. A statement believed but not yet proved is a conjecture.
Proofs in books are not written as numbered lists of formulas with a rule on each line, as in Chapter 1. They are written in sentences, and they leave out steps that any reader can supply, such as applications of the commutative law. But every proof written in sentences must be one that could, in principle, be expanded into a formal proof. That is the test of whether it is correct.
Definitions are where proofs begin¶
You cannot prove anything about even numbers until you know exactly what "even" means. The definitions used in this chapter are these.
Definitions
- An integer \(n\) is even if there is an integer \(k\) with \(n = 2k\), and odd if there is an integer \(k\) with \(n = 2k + 1\). Every integer is either even or odd, and not both.
- For integers \(a\) and \(b\) with \(a \ne 0\), \(a\) divides \(b\), written \(a \mid b\), if there is an integer \(k\) with \(b = ak\).
- An integer \(p > 1\) is prime if its only positive divisors are \(1\) and \(p\). An integer greater than 1 that is not prime is composite.
- A real number \(r\) is rational if there are integers \(p\) and \(q\) with \(q \ne 0\) and \(r = p/q\). A real number that is not rational is irrational.
Key idea
When a proof is stuck, write down what the definitions say. "Let \(n\) be odd" becomes "let \(n = 2k + 1\) for some integer \(k\)", and now there is something to calculate with.
Most theorems have the form \(\forall x\, (P(x) \to Q(x))\), usually with the "for all" left unsaid: "If \(n\) is odd, then \(n^2\) is odd" means "for every integer \(n\), if \(n\) is odd then \(n^2\) is odd". By universal generalisation (Section 2.6) it is enough to take an arbitrary \(n\) and prove \(P(n) \to Q(n)\). The rest of the chapter is about ways of doing that.
3.2 Direct proof¶
A direct proof of \(p \to q\) assumes \(p\) and, by a chain of steps, reaches \(q\). Because \(p \to q\) is automatically true when \(p\) is false, the case where \(p\) is true is the only one that needs work.
Example 3.1: The square of an odd number
Theorem. If \(n\) is an odd integer, then \(n^2\) is odd.
Proof. Let \(n\) be an odd integer. Then \(n = 2k + 1\) for some integer \(k\). So
Since \(2k^2 + 2k\) is an integer, \(n^2\) has the form \(2m + 1\) with \(m\) an integer, so \(n^2\) is odd. \(\blacksquare\)
Notice the shape: state what is assumed, unpack the definitions, calculate, and repackage the result to match the definition of what is to be proved.
Example 3.2: Divisibility is transitive
Theorem. For integers \(a, b, c\) with \(a \ne 0\) and \(b \ne 0\): if \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
Proof. Suppose \(a \mid b\) and \(b \mid c\). By definition there are integers \(k\) and \(\ell\) with \(b = ak\) and \(c = b\ell\). Substituting, \(c = (ak)\ell = a(k\ell)\). Since \(k\ell\) is an integer, \(a \mid c\). \(\blacksquare\)
Example 3.3: The sum of two rational numbers
Theorem. The sum of two rational numbers is rational.
Proof. Let \(r\) and \(s\) be rational. Then \(r = a/b\) and \(s = c/d\) for integers \(a, b, c, d\) with \(b \ne 0\) and \(d \ne 0\). So
Here \(ad + bc\) and \(bd\) are integers and \(bd \ne 0\) (a product of non-zero integers is non-zero). So \(r + s\) is rational. \(\blacksquare\)
3.3 Proof by contraposition¶
Sometimes the hypothesis \(p\) gives nothing useful to work with. Then try the contrapositive. Since \(p \to q \equiv \neg q \to \neg p\) (Section 1.3), a direct proof of \(\neg q \to \neg p\) is a proof of \(p \to q\). This is proof by contraposition.
Example 3.4: When the square is even
Theorem. For every integer \(n\), if \(n^2\) is even, then \(n\) is even.
Proof. We prove the contrapositive: if \(n\) is not even, then \(n^2\) is not even; that is, if \(n\) is odd, then \(n^2\) is odd. This is exactly Example 3.1. \(\blacksquare\)
A direct proof would start from "\(n^2 = 2k\)" and need to take a square root, which leads nowhere. The contrapositive turns the problem into one we have already solved.
Example 3.5: A product and its factors
Theorem. If \(a\) and \(b\) are positive integers with \(ab = n\), then \(a \le \sqrt{n}\) or \(b \le \sqrt{n}\).
Proof. We prove the contrapositive: if \(a > \sqrt{n}\) and \(b > \sqrt{n}\), then \(ab \ne n\). (Note De Morgan's law: the negation of "\(a \le \sqrt{n}\) or \(b \le \sqrt{n}\)" is "\(a > \sqrt{n}\) and \(b > \sqrt{n}\)".) Multiplying the two inequalities between positive numbers gives \(ab > \sqrt{n}\cdot\sqrt{n} = n\), so \(ab \ne n\). \(\blacksquare\)
This theorem has a practical use: to test whether \(n\) is prime, it is enough to try divisors up to \(\sqrt{n}\), because any factorisation \(n = ab\) has a factor no larger than \(\sqrt{n}\).
When to use contraposition
Try contraposition when the conclusion \(q\) is a negative statement ("is not ...", "is irrational", "\(\ne\)") or when its negation \(\neg q\) gives you an equation to work with but \(p\) does not.
3.4 Proof by contradiction¶
To prove a statement \(s\) by contradiction, assume \(\neg s\) and derive a contradiction: some statement \(r\) together with \(\neg r\). Since \(\neg s \to (r \wedge \neg r)\) can be true only if \(\neg s\) is false, \(s\) must be true. To prove a conditional \(p \to q\) this way, assume \(p\) and \(\neg q\) and derive a contradiction.
The most famous proof by contradiction is over two thousand years old.
Example 3.6: The square root of 2 is irrational
Theorem. \(\sqrt{2}\) is irrational.
Proof. Suppose, for a contradiction, that \(\sqrt{2}\) is rational. Then \(\sqrt{2} = a/b\) for integers \(a\) and \(b\) with \(b \ne 0\), and we may take the fraction in lowest terms, so that \(a\) and \(b\) have no common factor greater than 1. Squaring, \(2 = a^2/b^2\), so \(a^2 = 2b^2\). Thus \(a^2\) is even, and by Example 3.4, \(a\) is even: \(a = 2c\) for some integer \(c\). Then \(4c^2 = 2b^2\), so \(b^2 = 2c^2\), and \(b^2\) is even; by Example 3.4 again, \(b\) is even. Now \(a\) and \(b\) are both even, so 2 is a common factor, which contradicts the choice of \(a/b\) in lowest terms. Hence \(\sqrt{2}\) is irrational. \(\blacksquare\)
Example 3.7: There are infinitely many primes
Theorem. There are infinitely many prime numbers.
Proof. Suppose, for a contradiction, that there are only finitely many primes, \(p_1, p_2, \dots, p_n\). Let
Then \(N > 1\), so \(N\) has at least one prime divisor \(p\). (Every integer greater than 1 has a prime divisor; we prove this in Chapter 6.) Since \(p_1, \dots, p_n\) are all the primes, \(p\) is one of them, so \(p\) divides the product \(p_1 p_2 \cdots p_n\). Then \(p\) divides \(N - p_1 p_2 \cdots p_n = 1\). But no prime divides 1. This contradiction shows there are infinitely many primes. \(\blacksquare\)
A common misreading
The proof does not say that \(p_1 p_2 \cdots p_n + 1\) is prime. For the first six primes, \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509\), which is composite. The argument only says that its prime factors are new.
Contradiction and contraposition are related. A proof by contraposition of \(p \to q\) assumes \(\neg q\) and reaches \(\neg p\); that is also a contradiction with the assumption \(p\). When a proof by contradiction of \(p \to q\) ends by contradicting \(p\) itself, it is usually clearer to rewrite it as a proof by contraposition.
3.5 Proof by cases¶
When the hypothesis splits naturally into possibilities, prove the conclusion in each. This is proof by cases, and it rests on the tautology
The cases must cover every possibility, but they may overlap.
Example 3.8: A product of consecutive integers
Theorem. For every integer \(n\), the number \(n(n+1)\) is even.
Proof. Every integer is even or odd.
Case 1: \(n\) is even. Then \(n = 2k\), so \(n(n+1) = 2k(n+1)\), which is even.
Case 2: \(n\) is odd. Then \(n + 1 = 2k + 2 = 2(k+1)\) is even, so \(n(n+1) = 2n(k+1)\) is even.
In both cases \(n(n+1)\) is even. \(\blacksquare\)
Example 3.9: The triangle inequality for absolute value
Theorem. For all real numbers \(x\) and \(y\), \(\lvert x + y \rvert \le \lvert x \rvert + \lvert y \rvert\).
Proof. Recall that \(\lvert a \rvert = a\) if \(a \ge 0\) and \(\lvert a \rvert = -a\) if \(a < 0\); in every case \(a \le \lvert a \rvert\) and \(-a \le \lvert a \rvert\).
Case 1: \(x + y \ge 0\). Then \(\lvert x + y \rvert = x + y \le \lvert x \rvert + \lvert y \rvert\).
Case 2: \(x + y < 0\). Then \(\lvert x + y \rvert = -x - y = (-x) + (-y) \le \lvert x \rvert + \lvert y \rvert\). \(\blacksquare\)
Without loss of generality¶
When the cases are alike, a proof often handles one and says the others are the same "by symmetry". The phrase without loss of generality (often shortened to WLOG) announces this. In a proof about two integers \(x\) and \(y\) where the roles of \(x\) and \(y\) can be exchanged, we may say "without loss of generality, \(x \le y\)". Use it only when the omitted cases really are identical after renaming.
Example 3.10: Parity of a product
Theorem. If \(x\) and \(y\) are integers and \(xy\) is odd, then both \(x\) and \(y\) are odd.
Proof. By contraposition: suppose \(x\) and \(y\) are not both odd. Then at least one is even, and without loss of generality \(x\) is even (the case where \(y\) is even is the same with the letters exchanged). So \(x = 2k\), and \(xy = 2(ky)\) is even. \(\blacksquare\)
3.6 Biconditionals and equivalences¶
To prove \(p \leftrightarrow q\), prove both \(p \to q\) and \(q \to p\). The two directions are often called "only if" (\(p \to q\)) and "if" (\(q \to p\)).
Example 3.11: An if-and-only-if
Theorem. An integer \(n\) is odd if and only if \(n^2\) is odd.
Proof. (\(\Rightarrow\)) If \(n\) is odd, then \(n^2\) is odd, by Example 3.1. (\(\Leftarrow\)) If \(n^2\) is odd, then \(n\) is odd: by contraposition, if \(n\) is even, \(n = 2k\), then \(n^2 = 2(2k^2)\) is even. \(\blacksquare\)
To show that several statements \(p_1, p_2, \dots, p_n\) are all equivalent, it is enough to prove a cycle of implications \(p_1 \to p_2 \to \dots \to p_n \to p_1\), since from a cycle any statement implies any other by hypothetical syllogism. For three statements that is three proofs instead of six.
Example 3.12: Three equivalent statements
Theorem. For an integer \(n\), the following are equivalent: (i) \(n\) is even; (ii) \(n - 1\) is odd; (iii) \(n^2\) is even.
Proof. (i) \(\Rightarrow\) (ii): if \(n = 2k\), then \(n - 1 = 2(k - 1) + 1\) is odd. (ii) \(\Rightarrow\) (iii): if \(n - 1 = 2k + 1\), then \(n = 2k + 2 = 2(k+1)\) and \(n^2 = 2 \cdot 2(k+1)^2\) is even. (iii) \(\Rightarrow\) (i): Example 3.4. \(\blacksquare\)
3.7 Existence and uniqueness¶
A statement \(\exists x\, P(x)\) is proved by an existence proof. A constructive proof exhibits a particular \(x\) and checks that \(P(x)\) holds. A non-constructive proof shows that some \(x\) must exist without saying which.
Example 3.13: A constructive existence proof
Theorem. There is a positive integer that can be written as the sum of two cubes of positive integers in two different ways.
Proof. \(1729 = 1^3 + 12^3 = 9^3 + 10^3\). Check: \(1 + 1728 = 1729\) and \(729 + 1000 = 1729\). \(\blacksquare\)
Example 3.14: A non-constructive existence proof
Theorem. There are irrational numbers \(x\) and \(y\) such that \(x^y\) is rational.
Proof. Consider \(\sqrt{2}^{\sqrt{2}}\). It is either rational or irrational.
Case 1: it is rational. Take \(x = y = \sqrt{2}\), which are irrational by Example 3.6.
Case 2: it is irrational. Take \(x = \sqrt{2}^{\sqrt{2}}\) and \(y = \sqrt{2}\). Then \(x^y = \sqrt{2}^{\sqrt{2}\cdot\sqrt{2}} = \sqrt{2}^{2} = 2\), which is rational.
Either way such \(x\) and \(y\) exist. \(\blacksquare\)
The proof does not tell us which case holds. (In fact \(\sqrt{2}^{\sqrt{2}}\) is known to be irrational, but proving that needs much deeper mathematics.)
A uniqueness proof shows that there is exactly one \(x\) with \(P(x)\). It has two parts. Existence: show that some \(x\) has the property. Uniqueness: suppose \(x\) and \(y\) both have it, and show \(x = y\).
Example 3.15: Existence and uniqueness
Theorem. If \(a\) and \(b\) are real numbers with \(a \ne 0\), there is a unique real number \(r\) with \(ar + b = 0\).
Proof. Existence: \(r = -b/a\) works, since \(a(-b/a) + b = -b + b = 0\). Uniqueness: suppose \(ar + b = 0\) and \(as + b = 0\). Subtracting, \(a(r - s) = 0\), and since \(a \ne 0\), \(r - s = 0\), so \(r = s\). \(\blacksquare\)
3.8 Counterexamples and mistakes¶
To show that a universal statement \(\forall x\, P(x)\) is false, one counterexample suffices, because \(\neg\forall x\, P(x) \equiv \exists x\, \neg P(x)\).
Example 3.16: A pattern that breaks
Problem. Is \(n^2 + n + 41\) prime for every natural number \(n\)?
Solution. For \(n = 0, 1, 2, \dots, 39\) the values \(41, 43, 47, 53, \dots\) are all prime, which is a remarkable run. But for \(n = 40\), \(40^2 + 40 + 41 = 40 \cdot 41 + 41 = 41 \cdot 41\), which is composite. So the statement is false. Checking many cases is never a proof of a universal statement.
Common errors¶
Five ways a proof goes wrong
- Proving the converse. To prove \(p \to q\), you must assume \(p\) and reach \(q\), not assume \(q\) and reach \(p\).
- Assuming what is to be proved (circular reasoning). A "proof" that \(n^2\) even implies \(n\) even which begins "since \(n\) is even ..." proves nothing.
- Arguing from examples. Checking \(n = 1, 2, 3\) does not prove a statement about all \(n\). (It can, however, disprove one.)
- Reusing a variable. "Let \(m = 2k\) and \(n = 2k\) be even" forces \(m = n\). Two arbitrary even numbers need two different letters: \(m = 2k\), \(n = 2\ell\).
- Dividing by zero, or by something that might be zero. A classic false "proof" that \(1 = 2\) starts from \(a = b\), reaches \((a + b)(a - b) = b(a - b)\), and divides both sides by \(a - b\), which is zero.
3.9 Writing proofs that others can read¶
A proof is written for a reader. These habits make proofs easier to check.
- Say what you are proving and how. Begin with "We prove the contrapositive" or "Suppose, for a contradiction, that ...".
- Introduce every variable with its type: "Let \(n\) be an integer", "there is an integer \(k\) such that ...".
- Write in sentences. Symbols such as \(\Rightarrow\) and \(\therefore\) are not substitutes for words like "so" and "because". Display long calculations, but connect them with words.
- Give the reason for each step that is not routine: "by the definition of odd", "by Example 3.4".
- Say when you have finished, with a closing sentence and the mark \(\blacksquare\).
Table 3.1 collects the strategies of this chapter.
| To prove | Strategy | You assume | You show |
|---|---|---|---|
| \(p \to q\) | direct | \(p\) | \(q\) |
| \(p \to q\) | contraposition | \(\neg q\) | \(\neg p\) |
| \(p \to q\) | contradiction | \(p\) and \(\neg q\) | a contradiction |
| \(s\) | contradiction | \(\neg s\) | a contradiction |
| \((p_1 \vee p_2) \to q\) | cases | \(p_1\), then \(p_2\) | \(q\) in each case |
| \(p \leftrightarrow q\) | two directions | \(p\), then \(q\) | \(q\), then \(p\) |
| \(\exists x\, P(x)\) | construction | a specific \(c\) with \(P(c)\) | |
| \(\neg \forall x\, P(x)\) | counterexample | a specific \(c\) with \(\neg P(c)\) |
Table 3.1. Proof strategies at a glance.
The flowchart in Figure 3.1 is a rough guide to choosing among them. It is not a rule: with experience, you will see the right method from the shape of the statement.
flowchart TD
A[Statement: if p then q] --> B{Does p give an equation or object to work with?}
B -- yes --> C[Try a direct proof]
B -- no --> D{Does not-q give something to work with?}
D -- yes --> E[Try contraposition]
D -- no --> F[Try contradiction: assume p and not-q]
C --> G{Does p split into natural cases?}
G -- yes --> H[Prove each case]
3.10 Summary¶
Summary
- A proof starts from definitions, axioms and earlier theorems, and each step follows logically from earlier ones. Begin every proof by unpacking the definitions.
- Direct proof of \(p \to q\): assume \(p\), derive \(q\).
- Contraposition: prove \(\neg q \to \neg p\) instead. Useful when the conclusion is negative.
- Contradiction: assume the statement is false and derive a contradiction. Used for \(\sqrt{2}\) irrational and for the infinity of primes.
- Cases must cover every possibility; WLOG lets you skip cases that are identical after renaming.
- A biconditional needs two directions; a list of equivalent statements needs a cycle of implications.
- Existence proofs are constructive or non-constructive; uniqueness proofs show that any two solutions are equal.
- One counterexample disproves a universal statement; no number of examples proves one.
3.11 Exercises¶
Exercise 1
Prove that the sum of two odd integers is even.
Answer
Let \(m = 2k + 1\) and \(n = 2\ell + 1\) be odd. Then \(m + n = 2k + 2\ell + 2 = 2(k + \ell + 1)\), which is even since \(k + \ell + 1\) is an integer. \(\blacksquare\)
Exercise 2
Prove that if \(a \mid b\) and \(a \mid c\), then \(a \mid (b + c)\) and \(a \mid (bx + cy)\) for all integers \(x, y\).
Answer
Write \(b = ak\) and \(c = a\ell\). Then \(bx + cy = akx + a\ell y = a(kx + \ell y)\), so \(a \mid (bx + cy)\). Taking \(x = y = 1\) gives \(a \mid (b + c)\). \(\blacksquare\)
Exercise 3
Prove by contraposition: if \(3n + 2\) is odd, then \(n\) is odd.
Answer
Contrapositive: if \(n\) is even, then \(3n + 2\) is even. If \(n = 2k\), then \(3n + 2 = 6k + 2 = 2(3k + 1)\), which is even. \(\blacksquare\)
Exercise 4
Prove that \(\sqrt{3}\) is irrational. You may use the fact that if \(3 \mid a^2\) then \(3 \mid a\).
Answer
Suppose \(\sqrt{3} = a/b\) in lowest terms. Then \(a^2 = 3b^2\), so \(3 \mid a^2\) and hence \(3 \mid a\); write \(a = 3c\). Then \(9c^2 = 3b^2\), so \(b^2 = 3c^2\), so \(3 \mid b^2\) and \(3 \mid b\). Then 3 divides both \(a\) and \(b\), contradicting lowest terms. \(\blacksquare\)
Exercise 5
Prove that the sum of a rational number and an irrational number is irrational.
Answer
Let \(r\) be rational and \(x\) irrational, and suppose, for a contradiction, that \(r + x = s\) is rational. Then \(x = s - r\). The difference of two rationals is rational (as in Example 3.3, \(a/b - c/d = (ad - bc)/(bd)\)), so \(x\) is rational, a contradiction. \(\blacksquare\)
Exercise 6
Prove that for every integer \(n\), \(n^2 \bmod 4\) is \(0\) or \(1\); that is, \(n^2\) leaves remainder 0 or 1 on division by 4. Deduce that no integer of the form \(4m + 3\) is a sum of two squares.
Answer
Cases. If \(n = 2k\), \(n^2 = 4k^2\), remainder 0. If \(n = 2k + 1\), \(n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1\), remainder 1. A sum of two squares therefore has remainder \(0 + 0\), \(0 + 1\) or \(1 + 1\), that is, 0, 1 or 2 on division by 4, never 3. \(\blacksquare\)
Exercise 7
Disprove: "For every positive integer \(n\), \(2^n + 1\) is prime."
Answer
\(n = 3\): \(2^3 + 1 = 9 = 3 \cdot 3\). (The cases \(n = 1, 2, 4\) give the primes 3, 5, 17, which is why the claim is tempting.)
Exercise 8
Prove that there is no largest even integer.
Answer
Suppose, for a contradiction, that \(N\) is the largest even integer. Then \(N + 2\) is even (if \(N = 2k\) then \(N + 2 = 2(k+1)\)) and \(N + 2 > N\), a contradiction. \(\blacksquare\)
Exercise 9
Find the error: "Claim: every integer greater than 1 is even. Proof: Let \(n > 1\). Then \(n = 2k\) for some integer \(k\), so \(n\) is even."
Answer
The proof assumes what it is meant to prove: writing \(n = 2k\) is the definition of \(n\) being even, so the argument is circular. The claim is false (\(n = 3\)).
Exercise 10
Prove that among any three integers, two have an even sum.
Answer
Each integer is even or odd, so among three integers two have the same parity (if not, there would be at most one even and at most one odd, only two numbers). Two even numbers have an even sum, and so do two odd numbers (Exercise 1). \(\blacksquare\) This is a first use of the pigeonhole principle of Chapter 7.
3.12 Quiz¶
Check your understanding of proof methods
Exercise 1
To prove "if n squared is even then n is even" the easiest method is
- direct proof
- proof by contraposition
- a counterexample
- checking small cases
Answer
proof by contraposition
Exercise 2
In a proof by contradiction of "p implies q" you assume
- p
- not q
- p and not q
- q and not p
Answer
p and not q
Exercise 3
Give a counterexample to "n squared plus n plus 41 is prime for all natural numbers n". Type the smallest such n.
Answer
40
Exercise 4
Example 3.14 shows that irrational x and y with x to the power y rational exist, without saying which. Such a proof is called
- constructive
- non-constructive
- circular
- by cases only
Answer
non-constructive
Exercise 5
To prove that four statements are equivalent, the smallest number of implications you need to prove is
- 3
- 4
- 6
- 12
Answer
4
A cycle of four implications suffices.
Exercise 6
Checking a statement about all integers for n = 1 to 1000 is
- a proof
- a proof by cases
- not a proof
- a proof by induction
Answer
not a proof