Proof Techniques: Direct, Contrapositive & Contradiction

Discrete Mathematics Fundamentals

Chapter 7 · Proof Techniques: Direct, Contrapositive & Contradiction

Every chapter so far has justified its claims informally. This chapter makes the reasoning itself the subject — the standard techniques for proving a claim is actually, unconditionally true, not just true in every case anyone happened to check.

What a Proof Actually Is — and Why Testing Isn't One

A proof is a logically valid chain of steps from accepted facts (definitions, already-proven results) to the claim being made, with no gaps — every step follows necessarily from what came before.

Passing every test case is evidence, not proof

Running a function against a thousand test cases and seeing it pass every time is real, useful evidence — but it's not the same claim as "this function is correct for all possible inputs." A single untested input could still break it. This is exactly why Chapter 8's mathematical induction matters: it's the one technique in this course that can genuinely prove a property holds for every case in an infinite family, not just the finitely many cases anyone got around to checking.

Direct Proof

To prove "if P then Q," assume P is true, and show through a valid chain of reasoning that Q must then also be true.

Claim: If n is even, then n² is even

Proof. Assume n is even. By definition, n = 2k for some integer k. Then n² = (2k)² = 4k² = 2(2k²). Since 2k² is an integer, n² is 2 times an integer — which is exactly the definition of even. ∎

Proof by Contrapositive

Chapter 2 established that p → q ≡ ¬q → ¬p — the contrapositive is logically equivalent to the original implication, so proving one genuinely proves the other. This matters because the contrapositive direction is sometimes much easier to work with directly.

Claim: If n² is odd, then n is odd

Proving this directly is awkward. Its contrapositive, though, is "if n is not odd (i.e., even), then n² is not odd (i.e., even)" — which is exactly the direct proof already given above. Since the contrapositive is proven, and it's logically equivalent to the original claim, the original claim is proven too, with no additional work. ∎

Proof by Contradiction

Assume the claim is false, then show this assumption leads to something logically impossible. Since a false starting assumption can't lead to a genuine contradiction unless the assumption itself was the problem, the original claim must actually be true.

Claim: √2 is irrational (cannot be written as a ratio of integers)

Proof. Assume, for contradiction, that √2 is rational. Then √2 = a/b for some integers a, b with no common factor (in lowest terms). Squaring both sides: 2 = a²/b², so a² = 2b² — meaning a² is even.

By this chapter's own contrapositive result above, if a² is even, then a is even. So a = 2k for some integer k. Substituting: (2k)² = 2b², so 4k² = 2b², so b² = 2k² — meaning b² is even too, and by the same result, b is even.

But if both a and b are even, they share a common factor of 2 — directly contradicting the assumption that a/b was already in lowest terms. This is a genuine contradiction. The only assumption that could be wrong is the starting one — so √2 is not rational. ∎

This proof reuses the chapter's own earlier result

The "a² even → a even" step above is exactly the contrapositive result proven earlier in this same chapter — proofs build on each other constantly, the same way functions call other functions rather than reimplementing everything from scratch each time.

Choosing a Technique

Use this when...	Technique
The forward reasoning from P to Q is already straightforward	Direct
Reasoning from ¬Q backward is cleaner than reasoning from P forward	Contrapositive
Proving "there is no X" or an impossibility claim directly seems hard	Contradiction

The debugging parallel

"Assume the bug isn't in this function, trace through what that would mean, and find it leads somewhere impossible" is genuinely the same underlying logic as proof by contradiction — assuming the opposite of what you suspect, and using the resulting absurdity as evidence for where the real problem actually is.

Hands-On Exercises

Exercise 1

Give a direct proof that if n is odd, then n² is odd.

📄 View solution

Exercise 2

Prove "if n² is even, then n is even" using proof by contrapositive. (Hint: what does the contrapositive of this specific statement look like, and does Exercise 1's own result already prove it?)

📄 View solution

Exercise 3

Use proof by contradiction to show that there is no smallest positive rational number.

📄 View solution

Chapter 7 Quick Reference

A proof is a gapless logical chain from accepted facts to a conclusion — testing many cases is evidence, not proof
Direct: assume P, show Q follows
Contrapositive: prove ¬Q → ¬P instead — logically equivalent to P → Q, per Chapter 2
Contradiction: assume the claim is false, derive an impossibility, conclude the claim must be true
√2's irrationality proof reused this chapter's own earlier "a² even → a even" result directly — proofs build on each other
Next chapter: Mathematical induction — the one technique that can prove a property for infinitely many cases at once