Proof Techniques — Mathematics Knowledge System

Overview

A mathematical proof is a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems, but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning that establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning that establish 'reasonable expectation.' Presenting many cases in which a statement holds is not enough for a proof, which must demonstrate that the statement is true in all possible cases. A proposition that has not been proved but is believed to be true is known as a conjecture, or a hypothesis if frequently used as an assumption for further mathematical work.

Intuition

A proof is a chain of dominoes: each statement must be knocked over (justified) by the ones before it — an axiom, a definition, or a previously toppled domino (an earlier theorem) — until you reach the final domino, the claim you wanted. Different proof techniques are just different strategies for arranging the dominoes. Direct proof lines them up straight from hypothesis to conclusion. Contradiction assumes the last domino DOESN'T fall, then shows that breaks something earlier in the chain — an absurdity — so it must fall after all. Contrapositive rearranges the chain backwards, proving 'not conclusion implies not hypothesis' instead, which is logically the same claim. Induction is a chain with infinitely many dominoes: you show the first one falls, and that each domino knocks over the next, so — by an unstoppable chain reaction — all of them fall.

Formal Definition

Definition

Given a conditional statement P → Q that we want to establish as a theorem, the major proof techniques are logically distinct routes to the same conclusion, each justified by a tautology of propositional logic.

P \to Q

Direct proof: assume P, derive Q through a valid chain of implications

(P \to Q) \iff (\lnot Q \to \lnot P)

Contrapositive: logically equivalent restatement

(P \to Q) \iff \lnot(P \land \lnot Q)

Contradiction: assume P and ¬Q, derive a contradiction (False)

[P(0) \land \forall k\,(P(k) \to P(k+1))] \to \forall n\, P(n)

Mathematical induction (over the natural numbers)

Notation

Notation	Meaning
$P \to Q$	The conditional statement being proved: hypothesis implies conclusion
$\therefore$	'Therefore' — introduces the conclusion drawn from prior steps
$\bot$	Contradiction / absurdity (False), the target of a proof by contradiction
$\blacksquare$	Marks the end of a proof ('quod erat demonstrandum' — 'which was to be demonstrated')
$P(k) \to P(k+1)$	The inductive step: assuming the statement for k (inductive hypothesis), prove it for k+1

Derivation

Why is proof by contrapositive valid? It rests on the propositional tautology that P → Q and ¬Q → ¬P are logically equivalent — they have identical truth tables, so proving one proves the other.

P \to Q \equiv \lnot P \lor Q

Rewrite the conditional using its definition

\lnot Q \to \lnot P \equiv \lnot(\lnot Q) \lor \lnot P \equiv Q \lor \lnot P

Rewrite the contrapositive the same way

\lnot P \lor Q \equiv Q \lor \lnot P

Disjunction is commutative, so the two rewritten forms are identical

\therefore (P \to Q) \equiv (\lnot Q \to \lnot P)

The two statements are logically equivalent — proving either proves both

Proofs

√2 is irrational (proof by contradiction)

$\text{Suppose, for contradiction, that } \sqrt{2} \text{ is rational.}$ (Negation of the claim, assumed for contradiction)
$\sqrt{2} = \frac{a}{b} \text{ for integers } a, b \text{ with } \gcd(a,b)=1$ (Definition of rational number, written in lowest terms)
$2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$ (Square both sides and clear the denominator)
$a^2 \text{ is even} \implies a \text{ is even}, \text{ so } a = 2k$ (A square is even only if its root is even (parity argument))
$(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$ (Substitute a = 2k and simplify)
$b^2 \text{ is even} \implies b \text{ is even}$ (Same parity argument applied to b)
$\text{But then } \gcd(a,b) \geq 2, \text{ contradicting } \gcd(a,b)=1.$ (Both a and b are even, contradicting the lowest-terms assumption)
$\therefore \sqrt{2} \text{ is irrational.}$ (The assumption led to a contradiction, so it must be false)

The sum of the first n positive integers is n(n+1)/2 (proof by induction)

$\text{Base case: } n=1: \; \sum_{i=1}^{1} i = 1 = \frac{1(1+1)}{2}$ (Directly verify the formula holds for the smallest case)
$\text{Inductive hypothesis: assume } \sum_{i=1}^{k} i = \frac{k(k+1)}{2} \text{ for some } k \geq 1$ (Assume the statement holds for an arbitrary k)
$\sum_{i=1}^{k+1} i = \sum_{i=1}^{k} i + (k+1) = \frac{k(k+1)}{2} + (k+1)$ (Split off the last term and apply the inductive hypothesis)
$= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$ (Factor out (k+1) — this matches the formula at n = k+1)
$\therefore \forall n \geq 1, \; \sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ (Base case plus inductive step establish the claim for all n by the principle of induction)

There exist irrational numbers a, b with a^b rational (non-constructive existence proof)

$\text{Consider } \sqrt{2}^{\sqrt{2}}. \text{ Either it is rational or irrational.}$ (Law of excluded middle: exactly one of the two cases holds)
$\text{Case 1: if } \sqrt{2}^{\sqrt{2}} \text{ is rational, take } a=b=\sqrt{2}.$ (Both are irrational, and a^b is rational by assumption — done)
$\text{Case 2: if } \sqrt{2}^{\sqrt{2}} \text{ is irrational, let } a = \sqrt{2}^{\sqrt{2}}, \; b=\sqrt{2}.$ (a is irrational by this case's assumption, b is irrational (√2 is irrational))
$a^b = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2}\cdot\sqrt{2}} = \sqrt{2}^2 = 2$ (Exponent laws simplify the double power; 2 is rational)
$\therefore \text{ in either case, irrational } a,b \text{ with } a^b \text{ rational exist.}$ (The proof establishes existence without ever determining which case is actually true)

Properties

Direct proof

P \to Q \text{ proved by assuming } P \text{ and deriving } Q \text{ through valid steps}

Proof by contrapositive

(P \to Q) \equiv (\lnot Q \to \lnot P)

Proof by contradiction

\text{Assume } P \land \lnot Q, \text{ derive } \bot, \text{ conclude } P \to Q

Weak induction

[P(0) \land \forall k (P(k)\to P(k+1))] \to \forall n\, P(n)

Strong induction

[P(0) \land \forall k(\forall j \le k\, P(j) \to P(k+1))] \to \forall n\, P(n)

Proof by cases

[(A_1 \lor A_2 \lor \cdots \lor A_n) \land \bigwedge_i (A_i \to Q)] \to Q

Applications

Correctness proofs for algorithms (e.g. loop invariants) are essentially induction arguments; program verification tools automate contrapositive/contradiction-style reasoning about code paths.

Worked Examples

Assume n is even, so n = 2k for some integer k.
$n = 2k$
Square both sides and factor out 2, showing n² is a multiple of 2.
$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$

Answer: n² = 2(2k²), which is even, completing the direct proof.

Practice Problems

Difficulty 4/10

Prove by contradiction that there is no smallest positive rational number.

Difficulty 5/10

Prove by induction that 2ⁿ > n for all positive integers n.

Difficulty 3/10

Which proof technique proves P → Q by instead proving ¬Q → ¬P?

Direct proofProof by contrapositiveProof by contradictionProof by induction

Common Mistakes

Common Mistake

Confusing proof by contradiction with proof by contrapositive.

Contrapositive proves ¬Q → ¬P directly (no contradiction needed) and concludes P → Q by logical equivalence. Contradiction assumes BOTH P and ¬Q simultaneously and derives an explicit falsehood (⊥).

Common Mistake

Treating a handful of verified examples as a complete proof (e.g. 'n²+n+41 is prime for n=0..5, so it's always prime').

A proof must cover ALL cases, not a sample. n²+n+41 is in fact composite at n=40 — checking finitely many cases never establishes a universal claim.

Common Mistake

In induction, forgetting to verify the base case, or assuming what you're trying to prove in the inductive step.

Both the base case AND the inductive step are required; the inductive step must derive P(k+1) using P(k) as a hypothesis, not assume P(k+1) itself.

Quiz

In a proof by contradiction of P → Q, what do you assume at the start?

P and QP and ¬Q¬P and Q¬P and ¬Q

Which statement is logically equivalent to 'if it rains, the ground is wet'?

If the ground is wet, it rains.If the ground is not wet, it did not rain.If it does not rain, the ground is not wet.The ground is wet, and it rains.

Flashcards

1 / 4

Historical Background

The demand for rigorous, logically airtight proof traces to the ancient Greeks. Thales and the Pythagoreans are credited with early deductive arguments, but it was Euclid's Elements (c. 300 BCE) that codified proof as a chain of statements each justified by axioms, definitions, or previously proved propositions — a template still recognizable today. Proof by contradiction (reductio ad absurdum) appears already in Euclid's proof that there are infinitely many primes and in the Pythagoreans' proof that √2 is irrational. Mathematical induction was used implicitly by early mathematicians but was first formalized explicitly by Blaise Pascal (17th century) and later placed on rigorous footing by Giuseppe Peano's axioms for the natural numbers (1889). In the 19th and 20th centuries, the foundational crises in mathematics — paradoxes in naive set theory, Hilbert's program, and Gödel's incompleteness theorems — sharpened attention to exactly what counts as a valid proof, formalizing proof itself as an object of mathematical study (proof theory).

c. 300 BCE
Euclid's Elements establishes the axiomatic-deductive template for proof, including a proof by contradiction that there are infinitely many primes
Euclid
c. 500 BCE
Pythagoreans prove √2 is irrational using an early proof by contradiction
Pythagoras (school)
1654
Blaise Pascal gives an explicit, formal statement of the principle of mathematical induction
Blaise Pascal
1889
Giuseppe Peano axiomatizes the natural numbers, giving induction rigorous foundations
Giuseppe Peano
1931
Kurt Gödel's incompleteness theorems reveal fundamental limits on what formal proof systems can establish
Kurt Gödel

Summary

A proof is a deductive chain from axioms/hypotheses to a conclusion, establishing logical certainty — not just many examples.
Direct proof assumes the hypothesis and derives the conclusion step by step.
Contrapositive proof exploits (P→Q) ≡ (¬Q→¬P); contradiction proof assumes P ∧ ¬Q and derives an absurdity.
Mathematical induction proves a base case plus an inductive step (P(k)→P(k+1)) to establish a claim for all natural numbers.
Existence proofs can be non-constructive (e.g. the irrational^irrational example), proving something exists without identifying it explicitly.

References

WebsiteWikipedia — Mathematical proof
BookVelleman, D. How to Prove It: A Structured Approach, 2nd ed.
BookEuclid. Elements, Book IX, Proposition 20 (infinitude of primes).