Proof Methods: Direct, Contrapositive, Contradiction Guide

A direct proof of "if p then q" assumes p is true and, through valid steps, arrives at q: suppose the hypothesis, do the algebra, reach the conclusion. Most first proofs, like "the sum of two even integers is even", are direct.

Two indirect methods handle stubborn statements. A proof by contrapositive proves the equivalent ¬q → ¬p instead, handy when the negation is easier. A proof by contradiction assumes p ∧ ¬q, derives something impossible like r ∧ ¬r, and concludes the assumption was wrong. Choosing the right method is half the art of proving things.

Key Concepts

• Direct proof: assume p, derive q through valid steps.
• Contrapositive: p → q ≡ ¬q → ¬p. Prove "if not q then not p" instead.
• Contradiction: assume p ∧ ¬q, derive a contradiction (some statement and its negation), conclude p → q.
• When to use which: direct when the hypothesis gives you something concrete; contrapositive when ¬q is simpler than p; contradiction when both stall or when proving impossibility.

How It Works

Follow the recipe for the method you chose:

1. Direct: write "Assume p." Unpack definitions, manipulate, and end with "Therefore q."
2. Contrapositive: write "We prove the contrapositive: assume ¬q." Derive ¬p, then note the contrapositive is equivalent to the original.
3. Contradiction: write "Suppose, for contradiction, that p is true and q is false." Derive two contradictory statements, then conclude the supposition is impossible, so q holds.
4. In every method, each step must follow by a rule of inference or a definition.

Worked Example

Prove: if n² is even, then n is even. A direct proof stalls, so use the contrapositive: assume n is odd and show n² is odd.

• Assume n is odd, so n = 2k + 1 for some integer k.
• Square it: n² = (2k + 1)² = 4k² + 4k + 1.
• Factor: n² = 2(2k² + 2k) + 1 = 2m + 1, an odd number.
• So n² is odd. The contrapositive is proved, hence the original holds.

Check: n = 7 gives n² = 49, odd, confirming the pattern.

Common Misconceptions

• "Proof by contrapositive proves the converse." It does not. The contrapositive ¬q → ¬p is equivalent to p → q, while the converse q → p is a different statement entirely. Proving the contrapositive proves exactly what was asked.
• "In a contradiction proof you may assume anything." You may assume only the negation of what you want to prove (p ∧ ¬q). Assuming extra facts invalidates the argument.
• "Assuming the conclusion in a contradiction proof is circular." It is the method: assume ¬q temporarily, derive impossibility, then discharge the assumption.

Real-World Applications

• Number theory: the classic proof that √2 is irrational is a contradiction proof: assume √2 = a/b in lowest terms and derive that both a and b are even.
• Computer science: impossibility results, such as "no program can decide halting for all programs", are proved by contradiction.
• Geometry: Euclid's proof of infinitely many primes assumes finitely many and constructs a contradiction.

Direct proof assumes the hypothesis and derives the conclusion; contrapositive proves ¬q → ¬p instead; contradiction assumes p ∧ ¬q and derives an impossibility. Pick the method whose starting assumption gives you the most to work with.