Mathematical proof is the mechanism by which mathematics advances: every theorem rests on a chain of deductive reasoning from axioms through established results to a new conclusion. Knowing which technique to reach for — direct proof, contradiction, induction, well-ordering, or a combinatorial argument — is itself a core mathematical skill. The techniques covered here range from foundational (direct proof and contrapositive) through structural (induction and its variants) to powerful specialized tools (the probabilistic method and bijective proof). A unifying insight is that several pairs of techniques are logically equivalent — induction and well-ordering, contrapositive and direct proof of the negation — so the choice is always about which path produces the clearest argument.
What This Cheat Sheet Covers
This topic spans 13 focused tables and 89 indexed concepts, 79 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Proof Terminology & Logical Framework
The vocabulary of proof is the first thing to master: these terms define what you are trying to establish, what you may assume, and how the result relates to the broader mathematical landscape. Confusing a lemma with a theorem, or a conjecture with a proved result, leads to imprecise communication and reasoning.
| Term | Example | Description | |
|---|---|---|---|
Axiom (postulate) | Euclid: "The whole is greater than the part" | • Self-evident foundational truth assumed without proof • everything in a formal system is derived from axioms | |
Pythagorean theorem: $a^2 + b^2 = c^2$ | • Major proved mathematical result that can stand independently • the primary goal of a proof | ||
Euclid's lemma: if $p \mid ab$ and $p$ is prime, then $p \mid a$ or $p \mid b$ | • Auxiliary result proved specifically to support proving a larger theorem • important on its own only incidentally | ||
From $\sqrt{2}$ irrational: $\sqrt{2}$ is not expressible as $p/q$ with $p,q \in \mathbb{Z}$ | Easy, direct consequence of a theorem requiring little or no additional proof | ||
Goldbach's conjecture: every even integer $> 2$ is the sum of two primes | • Unproven statement believed to be true • becomes a theorem once proved, or a disproven claim once a counterexample is found | ||
"If $n$ is odd, then $n^2$ is odd" | • A minor theorem of intermediate importance • stated and proved formally, but less significant than a theorem | ||
$P \to Q$; $P$; $\therefore Q$ | Fundamental inference rule: if the implication and its hypothesis hold, the conclusion follows (also called law of detachment) | ||
$P \to Q$; $\lnot Q$; $\therefore \lnot P$ | Contrapositive inference rule: if conclusion is false and implication holds, the hypothesis must be false | ||
$n = 2$ disproves "all primes are odd" | • Single specific instance that makes a universal statement false • one counterexample is sufficient to disprove $\forall x, P(x)$ | ||
Written at the end of a proof | • "Quod erat demonstrandum" (what was to be demonstrated) • the ∎ (Halmos tombstone) is the modern convention | ||
Hypothesis (premise) | "Let $n$ be an even integer" | • The assumption at the start of a proof or the antecedent of $P \to Q$ • must not be confused with the conclusion | |
Biconditional (iff) | "$n$ is even $\iff$ $n^2$ is even" | • Requires proving both directions: $P \to Q$ and $Q \to P$ • both must hold for the iff to be valid |