Methods of Proof: Direct Contradiction Induction

Want to prove P → Q? You have three main options.

Direct proof: Assume P, derive Q. Contrapositive: Assume ¬Q, derive ¬P. Contradiction: Assume P and ¬Q, derive a contradiction.

All three prove the same thing. But some are easier than others depending on the specific statement. The choice of technique can make the difference between a straightforward proof and an impossible struggle.

Skilled mathematicians choose their proof technique before they start writing.

Direct Proof

The most straightforward approach: assume the hypothesis, derive the conclusion.

To prove: If n is even, then n² is even.

Proof: Assume n is even. Then n = 2k for some integer k. So n² = (2k)² = 4k² = 2(2k²). Since 2k² is an integer, n² is even. ∎

You start with P (n is even) and work forward until you reach Q (n² is even).

Proof by Contrapositive

The contrapositive of P → Q is ¬Q → ¬P. They're logically equivalent.

Sometimes ¬Q → ¬P is easier to prove.

To prove: If n² is even, then n is even.

Direct approach would start with "n² is even" — but it's hard to work forward from there.

Contrapositive proof: We prove: If n is odd, then n² is odd.

Assume n is odd. Then n = 2k + 1 for some integer k. So n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1. Since 2k² + 2k is an integer, n² is odd. ∎

We proved ¬Q → ¬P, which is equivalent to P → Q.

When to Use Contrapositive

Use contrapositive when:

• The hypothesis P is hard to work with
• The negation ¬Q gives you something concrete to start from
• You have more information about what things are NOT than what they ARE

The even/odd example is classic: "n² is even" is awkward to start from, but "n is odd" gives you a clean formula (2k + 1).

Proof by Contradiction

Assume the statement is false. Derive something impossible.

To prove: √2 is irrational.

Proof: Assume √2 is rational. Then √2 = a/b for some integers a, b with no common factors. Squaring: 2 = a²/b², so a² = 2b². Thus a² is even, so a is even (by contrapositive proved above). Let a = 2k. Then (2k)² = 2b², so 4k² = 2b², so b² = 2k². Thus b² is even, so b is even. But then both a and b are even — contradicting "no common factors." The assumption was false. √2 is irrational. ∎

The Contradiction Pattern

To prove P by contradiction:

1. Assume ¬P
2. Derive a statement of the form Q ∧ ¬Q
3. Since contradictions are impossible, ¬P must be false
4. Therefore P

The power: you can use both the original assumptions AND the negation of what you're trying to prove. More ammunition often means an easier proof.

Proof by Contradiction for Implications

To prove P → Q by contradiction:

1. Assume P and ¬Q
2. Derive a contradiction
3. Therefore P → Q

This is similar to contrapositive but slightly different: you're assuming P is true AND Q is false, then showing that's impossible.

Example — If n² is even, then n is even:

Assume n² is even and n is odd. Then n = 2k + 1, so n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1. This means n² is odd. But we assumed n² is even. Contradiction. Therefore, if n² is even, n is even. ∎

Proof by Cases

When a statement breaks into distinct cases, prove each separately.

To prove: For any integer n, n² + n is even.

Case 1: n is even. Let n = 2k. Then n² + n = 4k² + 2k = 2(2k² + k), which is even.

Case 2: n is odd. Let n = 2k + 1. Then n² + n = (4k² + 4k + 1) + (2k + 1) = 4k² + 6k + 2 = 2(2k² + 3k + 1), which is even.

In both cases, n² + n is even. ∎

Constructive vs. Non-Constructive

Constructive proof: Shows something exists by exhibiting it.

"There exists an irrational number." Proof: √2 is irrational. Here it is.

Non-constructive proof: Shows something must exist without finding it.

"There exist irrational numbers a, b such that aᵇ is rational."

Proof: Consider √2^√2. Either it's rational (done) or it's irrational. If irrational, let a = √2^√2 and b = √2. Then aᵇ = (√2^√2)^√2 = √2^2 = 2, which is rational. ∎

This proves such a, b exist without determining whether √2^√2 is rational.

Choosing Your Technique

No hard rules — but experience teaches you to recognize which technique fits.

The Logical Equivalences Underlying These Techniques

Direct proof uses: P → Q directly.

Contrapositive uses: (P → Q) ≡ (¬Q → ¬P)

Contradiction uses: (P → Q) ≡ ¬(P ∧ ¬Q)

These equivalences guarantee all three methods prove the same thing. The choice is purely strategic — which one gives you the easiest path.

Practice Recognition

"Suppose for contradiction that there are finitely many primes..." — contradiction proof incoming.

"We prove the contrapositive: if n is divisible by 4..." — contrapositive proof.

"Let n be an arbitrary even number..." — direct proof.

"We consider two cases..." — proof by cases.

Recognizing the technique helps you follow and construct proofs efficiently.

Part 10 of the Logic series.

Previous: Quantifiers: For All and There Exists Next: Mathematical Induction: Infinite Dominos