Proof by Contrapositive

Math for CS · Axiom Academy

Prove ¬Q → ¬P instead of P → Q A proof by contrapositive uses a key logical principle: the statement "P → Q" is logically equivalent to "¬Q → ¬P". These two statements are always equivalent. If one is true, the other must be true. If one is false, the other must be false. Claim: If n² is odd, then n is odd. Instead of proving "n² odd → n odd", we prove "n even → n² even" Assume n is even (¬Q in contrapositive) Then n = 2k for some integer k Therefore n² is even (¬P in contrapositive) By contrapositive: If n² is odd, then n must be odd. QED Why this is easier: It's simpler to show "even number squared is even" than to work backwards from "odd square to odd root". Claim: If n is prime and n | ab, then n | a or n | b. This is actually a classic theorem in number theory. The direct proof requires careful case analysis, but the contrapositive is more straightforward conceptually. Instead: If (n ∤ a AND n ∤ b), then n ∤ ab This states: if n doesn't divide either factor, it can't divide the product This is easier to reason about algebraically Once proven, the original statement follows by contrapositive The hypothesis P is hard to work with directly The negation ¬Q is easier to understand and manipulate The negative case has a simpler structure Contradiction: Assume ¬Q, show it leads to impossibility (P ∧ ¬P) Contrapositive: Assume ¬Q, directly prove ¬P using logical steps Contrapositive is more direct and often cleaner

This is the written version of the interactive lesson above. See the full Math for CS course.