Proof by Contradiction in Logic

Math for CS · Axiom Academy

Assume the opposite, derive the impossible, conclude the original The logical foundation: ( P F) P , where F represents a contradiction. State what you want to prove: " P " Write: "Assume, for contradiction, that P " Use logical reasoning from P (plus known facts) to derive a statement that is clearly false — a contradiction Conclude: "This is a contradiction. Therefore P is false, so P is true." This technique is especially powerful when: The statement is negative: "There is no X with property Y" — assume X exists and derive a contradiction Direct proof is hard to start: When you don't see a clear path forward, assuming the opposite often gives you more to work with Uniqueness proofs: "There is at most one X" — assume two exist and show they must be equal Don't confuse proof by contradiction with proof by contrapositive: Contrapositive is more targeted (and often cleaner). Use contradiction when contrapositive doesn't apply or when you're proving something that isn't an implication. Assume the negation of what you want to prove, then derive a contradiction. The contradiction proves the assumption was false, so the original statement is true. Best for: negative statements, existence of infinitely many objects, and undecidability proofs. Classic examples: irrational, infinitely many primes, the Halting Problem.

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