Mathematical Proof Techniques

A proof is a finite sequence of statements, each of which is an axiom, a definition, a hypothesis, or follows from earlier statements by a valid rule of inference, ending in the claim to be proved. Proof is what distinguishes mathematics from empirical science: a mathematical truth, once correctly proved, is certain and never overturned by new data. Mastering proof techniques means learning which strategy fits a given problem — and recognising the logical structure ("for all", "there exists", "if-then") that dictates that choice. A surprising fact: some true statements about whole numbers can be proven impossible to prove from the standard axioms (Gödel's incompleteness theorems), yet the everyday proofs a student writes remain perfectly valid within their system.

The Core Insight

A proof transports you from what you are allowed to assume (the hypothesis $P$) to what you must show (the conclusion $Q$) using only logically guaranteed steps. The art is choosing the form of the journey: go forward from $P$ (direct), flip the implication ($\neg Q\Rightarrow \neg P$), assume the opposite and crash ($P\wedge \neg Q\Rightarrow \perp$), or climb an infinite ladder one rung at a time (induction). The logic never changes — only the route.

Formal Statement

Most theorems have the form of a conditional: "If $P$, then $Q$", written $P\Rightarrow Q$. Understanding the logic of this connective is the foundation of every technique.

The Conditional and Its Relatives

For statements $P$ (hypothesis) and $Q$ (conclusion), the implication $P\Rightarrow Q$ is false only when $P$ is true and $Q$ is false. Three related conditionals are:

Here $P$, $Q$ are propositions; $\neg$ is logical negation ("not"); $\Rightarrow$ is "implies"; $\perp$ denotes a contradiction (a statement that is always false).

Logical Equivalence of Contrapositive

The implication $P\Rightarrow Q$ and its contrapositive $\neg Q\Rightarrow \neg P$ have identical truth values in every case:

The quantifiers determine which proof technique is even possible.

Universal and Existential Statements

A universal statement claims something for all members of a set; an existential statement claims at least one member exists:

Their negations swap the quantifier:

Why It Holds / Derivation

The validity of each technique rests on the truth table of $\Rightarrow$. Here we justify the three deductive methods and induction.

Direct Proof Is Valid

1. Goal. Prove $P\Rightarrow Q$.
2. Method. Assume $P$ is true. (If $P$ is false the implication is automatically true, so this case needs no work.)
3. From $P$, apply definitions, axioms, and known theorems in a chain of valid inferences.
4. Arrive at $Q$.
5. Since we reached $Q$ whenever $P$ holds, the only case that could falsify $P\Rightarrow Q$ (namely $P$ true, $Q$ false) never occurs. $■$

Proof by Contrapositive Is Valid

1. Goal. Prove $P\Rightarrow Q$.
2. By equation $[4]$, this is logically equivalent to $\neg Q\Rightarrow \neg P$.
3. Assume $\neg Q$ (the conclusion fails).
4. Derive $\neg P$ by direct reasoning.
5. Having proven the equivalent statement, the original $P\Rightarrow Q$ holds. $■$

Proof by Contradiction Is Valid

1. Goal. Prove a statement $R$ (which may itself be $P\Rightarrow Q$).
2. Assume $\neg R$ alongside all hypotheses.
3. Derive a contradiction $\perp$ (e.g. $0=1$, or a number both even and odd).
4. Since true premises can never yield a falsehood, the added assumption $\neg R$ must be false.
5. Therefore $R$ is true. (When proving $P\Rightarrow Q$, one assumes $P\wedge \neg Q$ and reaches $\perp$.) $■$

The Principle of Mathematical Induction

1. Goal. Prove $\forall n\ge n_0,P(n)$ for integers $n$.
2. Base case. Prove $P(n_0)$ directly.
3. Inductive step. Prove the implication $P(k)\Rightarrow P(k+1)$ for arbitrary $k\ge n_0$. The assumption $P(k)$ is the inductive hypothesis.
4. Conclusion. By the well-ordering of the integers, $P(n)$ holds for all $n\ge n_0$.

Euclid of Alexandria | c. 325 – c. 265 BCE

Euclid's Elements is the founding document of the axiomatic method. From five geometric postulates and five "common notions", he deduced 465 propositions across thirteen books, each justified by explicit logical steps from what came before. His proof that there are infinitely many primes — assume finitely many, multiply them all and add one, derive a contradiction — remains the textbook model of proof by contradiction over two millennia later. The phrase "Q.E.D." (quod erat demonstrandum, "which was to be demonstrated") descends directly from his closing formula.

Building Intuition

Think of each technique as a tool with a natural job:

• Direct proof — when a clear chain of cause-and-effect runs from $P$ to $Q$. Best for algebraic identities and definitional unpacking.
• Contrapositive — when assuming $\neg Q$ gives you something concrete to manipulate but assuming $P$ gives a vague existence claim. ("If $n^2$ is even then $n$ is even" is awkward forward but easy backward: assume $n$ odd, square it, get odd.)
• Contradiction — when the statement asserts something is impossible or unique ("$\sqrt{2}$ is irrational", "there is no largest prime"). You give your opponent what they want and watch it self-destruct.
• Induction — when a statement is indexed by the natural numbers and each case builds on the previous one (sums, divisibility, inequalities for all $n$).
• Construction — for existence claims: don't argue that a thing exists, build it.
• Exhaustion (cases) — when finitely many situations cover everything; check each.

Decision flowchart for selecting a proof technique

Worked Examples

Irrationality of √2 — Proof by Contradiction

1. Square: $2=a^2/b^2$, hence $a^2=2b^2$.
2. So $a^2$ is even, which forces $a$ even (contrapositive: odd² is odd). Write $a=2m$.
3. Substitute: $(2m{)}^2=2b^2\Rightarrow 4m^2=2b^2\Rightarrow b^2=2m^2$.
4. So $b^2$ is even, hence $b$ is even.
5. But then $a$ and $b$ share the factor $2$ — contradicting "lowest terms".

Sum of First n Integers — Proof by Induction

1. Base case $n=1$: left side $=1$; right side $=\frac{1\cdot 2}{2}=1$. ✓
2. Inductive hypothesis. Assume $\sum _{i=1}^{k}i=\frac{k(k+1)}{2}$ for some $k\ge 1$.
3. Inductive step. Add $(k+1)$:

1. This is exactly the formula with $n=k+1$.
2. By induction, the formula holds for all $n\ge 1$.

Common Misconceptions

A proof of the converse is NOT a proof of the original

Proving $Q\Rightarrow P$ tells you nothing about $P\Rightarrow Q$ (equation $[1]$). "If it rained, the ground is wet" is not established by "if the ground is wet, it rained" — a sprinkler wets the ground. Likewise, one example is never a proof of a universal statement, and a picture is not a proof (it can suggest but cannot guarantee). Finally, in contradiction proofs you must reach a genuine logical impossibility, not merely something surprising.

Disproving "every odd number is prime"

The statement $\forall n(n\text{ odd}\Rightarrow n\text{ prime})$ is false. By equation $[6]$, one counterexample suffices: $n=9$ is odd but $9=3\times 3$ is composite. A single witness destroys a universal claim — this is the asymmetry between proving "for all" (needs a general argument) and disproving it (needs one case).

The flawed-induction trap: "all horses are the same colour"

A famous fallacy "proves" all horses share one colour by induction on the number of horses, failing only because the inductive step silently assumes overlap between two sub-groups that does not exist when $k=1$. Moral: the inductive step $P(k)\Rightarrow P(k+1)$ must hold for every $k\ge n_0$, including the smallest. Always check that the step's reasoning is valid right from the base case.

Connections

Proof techniques are the connective tissue of mathematics. Mathematical Induction is the engine behind nearly every formula indexed by $n$ and underlies Recursion in computer science. Proof by Contradiction depends on Propositional Logic and the law of the excluded middle, linking proof to the foundations of Set Theory. The structure of Quantifiers dictates whether you build a witness (Constructive Proof) or argue abstractly. The deductive method itself was systematised in Euclidean Geometry and is formalised by First-Order Logic and Truth Tables.

Real-World Applications

1. Cryptography (RSA). The security of RSA encryption rests on proven theorems in Number Theory (Fermat's little theorem, properties of modular arithmetic), all established by direct and inductive proofs.
2. Software verification. Tools like Coq and Isabelle/HOL use machine-checked proofs by induction to certify that programs (e.g. the CompCert C compiler) are bug-free.
3. Algorithm correctness. Computer scientists prove that algorithms (Dijkstra's shortest path, mergesort) terminate and return correct output using loop invariants — a disguised form of induction.
4. Engineering tolerances. Proving inequalities (by cases or contradiction) guarantees a control system stays within safe bounds for all inputs, not just tested ones.
5. Database integrity. Formal proofs ensure that transaction protocols preserve consistency under every possible interleaving of operations.
6. Blockchain consensus. Protocols like Byzantine fault tolerance are accompanied by mathematical proofs that agreement holds whenever fewer than one-third of nodes are faulty.
7. Error-correcting codes. Reed–Solomon and Hamming codes used in CDs, QR codes, and deep-space communication rely on proven algebraic guarantees about recoverable errors.

Historical Development

• c. 600 BCE — Thales of Miletus is credited with the first deductive proofs in geometry, moving beyond empirical measurement.
• c. 300 BCE — Euclid's Elements codifies the axiomatic-deductive method; the infinitude-of-primes proof by contradiction appears.
• c. 250 BCE — Archimedes uses the method of exhaustion, an early limiting/case argument, to compute areas and the value of $\pi$.
• 1654 — Pascal articulates a clear principle of mathematical induction in his treatise on the arithmetic triangle.
• 1847 — George Boole's Mathematical Analysis of Logic turns logical inference into algebra, the seed of Truth Tables.
• 1879 — Gottlob Frege's Begriffsschrift introduces formal quantifier logic, making "for all" and "there exists" precise.
• 1889 — Giuseppe Peano states his axioms for the natural numbers, putting induction on a rigorous footing.
• 1931 — Kurt Gödel proves the incompleteness theorems: any consistent system rich enough for arithmetic contains true statements it cannot prove.
• 1976 — Appel and Haken prove the Four Colour Theorem by computer-assisted exhaustion of 1,936 cases, igniting debate over what counts as a proof.

Subtleties & Limits

See Also