Discrete Math › Section B · Logic and proofs › Topic B.4
Direct proof, contrapositive, and contradiction
A proof is an argument that leaves no case unchecked. Three logical skeletons, the direct, contrapositive and contradiction methods, carry most proofs you will write, and each starts from definitions written in exact form.
What a proof is
A proof shows that a statement is true by a chain of valid steps from definitions, accepted facts and earlier results. Examples are not proofs, however many there are. The expression \(n^2 + n + 41\) gives a prime for every n from 0 to 39, yet at \(n = 40\) it gives \(1681 = 41^2\). Goldbach's conjecture, that every even number greater than 2 is a sum of two primes, has been checked by computer for enormous numbers but is still unproved. A proof has two layers: a logical skeleton, chosen from the forms below, and mathematical content, supplied by definitions.
Definitions in usable form
Proofs about integers turn words into equations. An integer n is even if \(n = 2k\) for some integer k, and odd if \(n = 2k + 1\) for some integer k; every integer is one or the other. An integer a divides b, written \(a \mid b\), if \(b = ak\) for some integer k, so \(3 \mid 12\) because \(12 = 3 \cdot 4\). Most theorems are universal, \(\forall n\,(P(n) \to Q(n))\), so a proof begins "let n be an arbitrary integer": it assumes nothing about n except what the hypothesis says, so its reasoning applies to every n.
Direct proof
To prove \(P \to Q\) directly, assume P, unpack it with definitions, and reason step by step until you reach Q. The skeleton is: assume P; explain; therefore Q. Claim: the sum of two odd integers is even. Proof. Let a and b be odd integers, so \(a = 2k + 1\) and \(b = 2m + 1\) for some integers k and m. Then
Since \(k + m + 1\) is an integer, \(a + b\) is even. ■ Notice the two different letters k and m: using k for both would wrongly force \(a = b\).
Worked example: a direct proof about divisibility
Prove: for all integers a, b and c, if \(a \mid b\) and \(a \mid c\), then \(a \mid (b + c)\). 1. Set up: let a, b, c be arbitrary integers, and assume \(a \mid b\) and \(a \mid c\). 2. Unpack the definition: \(b = aj\) and \(c = ak\) for some integers j and k. 3. Aim: write \(b + c\) as a times an integer. 4. Compute: \(b + c = aj + ak = a(j + k)\). 5. Since \(j + k\) is an integer, \(a \mid (b + c)\). ■ 6. Check with numbers: \(3 \mid 12\) and \(3 \mid 21\), and indeed \(3 \mid 33\).
Proof by contrapositive
Since \(P \to Q\) is logically equivalent to \(\neg Q \to \neg P\), a direct proof of the contrapositive proves the original. The skeleton is: assume not Q; explain; therefore not P. Choose this method when the hypothesis is hard to unpack but the negated conclusion is easy. Knowing that \(n^2\) is even tells you little directly about n, but knowing that n is odd gives \(n = 2k + 1\) at once. That is how to prove "if \(n^2\) is even, then n is even": if n is odd, then
which is odd.
Worked example: proof by contrapositive
Prove: for every integer n, if \(3n + 5\) is even, then n is odd. 1. A direct start, \(3n + 5 = 2m\), does not easily isolate n, so use the contrapositive. 2. Contrapositive: if n is not odd, then \(3n + 5\) is not even; that is, if n is even, then \(3n + 5\) is odd. 3. Assume n is even, so \(n = 2k\) for some integer k. 4. Then \(3n + 5 = 6k + 5 = 2(3k + 2) + 1\). 5. Since \(3k + 2\) is an integer, \(3n + 5\) is odd. ■ 6. Check: \(n = 3\) gives 14, even, and 3 is odd, as claimed.
Proof by contradiction
To prove a statement S by contradiction, assume S is false and reason validly until you reach something impossible, a statement of the form \(R \wedge \neg R\). A valid argument from a lone assumption cannot reach a falsehood unless the assumption is false, so S must be true. For an implication, the assumption \(\neg(P \to Q)\) is \(P \wedge \neg Q\), so you may use both P and not Q. Compare the starts: a direct proof assumes P and ends with Q; a contrapositive proof assumes not Q and ends with not P; a proof by contradiction assumes both and ends with an impossibility.
Worked example: the square root of 2 is irrational
1. Suppose, for contradiction, that \(\sqrt{2}\) is rational: \(\sqrt{2} = \frac{a}{b}\) for integers a and b with \(b \ne 0\), the fraction in lowest terms. 2. Squaring, \(2 = \frac{a^2}{b^2}\), so \(a^2 = 2b^2\) and \(a^2\) is even. 3. By the contrapositive proof above, a is even: \(a = 2c\) for some integer c. 4. Substituting, \(4c^2 = 2b^2\), so \(b^2 = 2c^2\), and b is even too. 5. Then 2 divides both a and b, so the fraction was not in lowest terms: a contradiction. 6. Therefore \(\sqrt{2}\) is irrational. ■
Cases, existence and counterexamples
A proof by cases splits the hypothesis into cases that cover every possibility. Claim: \(n^2 + 3n = n(n + 3)\) is even for every integer n. If n is even, the factor n is even. If n is odd, then \(n + 3\) is even. Either way the product is even. ■ To prove that something exists, construct it: "some prime is even" is proved by 2. Uniqueness: assume two objects have the property, then show they are equal. To disprove a universal claim, one counterexample suffices: "every odd number is prime" fails at 9. Euclid proved there are infinitely many primes: multiply any finite list of primes and add 1; the result leaves remainder 1 on division by each listed prime, so its prime factors are new. It need not itself be prime:
Writing proofs well
A proof is written for a reader. State what you are proving and which method you are using. Introduce every variable before using it and say what kind of object it is. Justify each step, naming the definition or earlier result it uses. Write in full sentences, with equations as part of them. Mark the end with a box ■ or QED. Then reread it as a sceptic: is any case missing, or any step assumed?
Common mistakes to avoid
First, offering examples as a proof of a universal claim. Second, assuming what you are trying to prove, such as starting a direct proof from the conclusion. Third, reusing one letter for two numbers, as in \(a = 2k\) and \(b = 2k\). Fourth, proving the converse by mistake. Fifth, starting a contrapositive proof but negating the statement wrongly; the negation of "a or b is odd" is "a and b are both even". Sixth, choosing cases that miss some integers, such as positive and negative, which leaves out 0.
Key takeaways
A proof covers every case; examples never do. Write definitions as equations: even \(n = 2k\), odd \(n = 2k + 1\), \(a \mid b\) when \(b = ak\). Direct proof: assume P, deduce Q. Contrapositive: assume not Q, deduce not P. Contradiction: assume the statement false, for an implication P and not Q, and reach an impossibility. Cases must cover every possibility, existence can be shown by an example, and one counterexample disproves a universal claim.
Flashcards
Flashcard
A chain of valid steps showing a statement holds in every case
Test your understanding
Question 1 of 5
To prove "if P, then Q" by contrapositive, how does the proof begin and end?
Question 2 of 5
Which observation shows that "n² + n + 41 is prime for every natural number n" is false?
Question 3 of 5
Which is the correct start of a direct proof that the sum of two even integers is even?
Question 4 of 5
The proof that √2 is irrational is a proof by contradiction. What does it assume first?
Question 5 of 5
A proof by cases shows that n² + 3n is even for every integer n. Which pair of cases covers every integer?
