title: "Proof by Contradiction"

Proof by Contradiction

Definition. A proof by contradiction establishes a statement $P$ by assuming $P$ is false and deriving something impossible. Valid steps from a true assumption can only produce truths, so the assumption must have been false, and $P$ is true.

The proof must open by negating $P$ correctly (Quantifier rules) and must actually use the negated assumption somewhere. Introduced in Lecture 1; it powers Diagonalization and returns throughout Units 2 and 3.