Mathematical proofs are the foundation of all rigorous mathematics. They provide a method for establishing mathematical truth through logical reasoning, transforming intuition and conjecture into certain knowledge. Unlike empirical sciences where theories are supported by evidence, mathematics demands absolute certainty through deductive proof.
Logic Fundamentals
Propositions and Logical Connectives
A proposition is a declarative statement that is either true or false, but not both. For example, “7 is a prime number” is a proposition (true), whilst “x > 5” is not a proposition until x is specified.
The fundamental logical connectives are:
| Symbol | Name | Meaning |
|---|---|---|
| ∧ | Conjunction (AND) | Both must be true |
| ∨ | Disjunction (OR) | At least one must be true |
| ¬ | Negation (NOT) | Reverses truth value |
| → | Implication (IF…THEN) | False only when P true and Q false |
| ↔ | Biconditional (IFF) | Both have same truth value |
Truth Table for Implication (P → Q):
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Note that an implication is vacuously true when the hypothesis P is false.
Quantifiers
Universal quantifier (∀): “For all” or “for every”
- ∀x ∈ ℝ, x² ≥ 0 means “for all real numbers x, x squared is non-negative”
Existential quantifier (∃): “There exists” or “for some”
- ∃x ∈ ℤ such that x² = 4 means “there exists an integer whose square is 4”
Negating quantified statements:
- ¬(∀x, P(x)) ≡ ∃x, ¬P(x)
- ¬(∃x, P(x)) ≡ ∀x, ¬P(x)
Set Theory Basics
Set theory provides the language for modern mathematics.
Set notation:
- x ∈ A means “x is an element of A”
- x ∉ A means “x is not an element of A”
- {1, 2, 3} is roster notation
- {x ∈ ℤ : x > 0} is set-builder notation
Set relationships:
- A ⊆ B (A is a subset of B): every element of A is in B
- A ⊂ B (A is a proper subset of B): A ⊆ B and A ≠ B
- 𝒫(A) is the power set: the set of all subsets of A
Set operations:
- A ∪ B (union): elements in A or B or both
- A ∩ B (intersection): elements in both A and B
- A \ B (set difference): elements in A but not in B
- Aᶜ (complement): elements not in A (relative to a universal set)
- A × B (Cartesian product): {(a, b) : a ∈ A, b ∈ B}
Proof Techniques
Direct Proof
In a direct proof, we assume the hypothesis P and derive the conclusion Q through a sequence of logical steps.
Structure:
- Assume P is true
- Use definitions, axioms, and previously proven results
- Arrive at Q
Example: Prove that the sum of two even integers is even.
Proof: Let m and n be even integers. By definition, m = 2a and n = 2b for some integers a and b. Then m + n = 2a + 2b = 2(a + b). Since a + b is an integer, m + n is even. ∎
Proof by Contradiction
Assume the negation of what you want to prove, then derive a logical contradiction.
Structure:
- Assume ¬Q (the negation of the conclusion)
- Derive a contradiction (something of the form R ∧ ¬R)
- Conclude Q must be true
Example: Prove that √2 is irrational.
Proof: Suppose √2 is rational. Then √2 = p/q for some integers p, q with q ≠ 0, expressed in lowest terms. Squaring both sides: 2 = p²/q², so p² = 2q². Thus p² is even, which means p is even (since odd² is odd). Write p = 2k. Then 4k² = 2q², so q² = 2k². Thus q is also even. But this contradicts p/q being in lowest terms. Therefore √2 is irrational. ∎
Proof by Contraposition
Instead of proving P → Q, prove the logically equivalent ¬Q → ¬P.
Structure:
- Assume ¬Q
- Derive ¬P
- Conclude P → Q
Example: Prove that if n² is even, then n is even.
Proof: We prove the contrapositive: if n is odd, then n² is odd. Assume n is odd. Then n = 2k + 1 for some integer k. Thus n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. ∎
Mathematical Induction
Induction proves statements about natural numbers.
Structure:
- Base case: Prove P(1) (or P(0))
- Inductive hypothesis: Assume P(k) for some k ≥ 1
- Inductive step: Prove P(k) → P(k + 1)
Example: Prove that 1 + 2 + … + n = n(n + 1)/2 for all n ≥ 1.
Proof:
- Base case: When n = 1, LHS = 1 and RHS = 1(2)/2 = 1. ✓
- Inductive hypothesis: Assume 1 + 2 + … + k = k(k + 1)/2.
- Inductive step: 1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2. ∎
Strong Induction: Instead of assuming only P(k), assume P(1), P(2), …, P(k) are all true, then prove P(k + 1).
Proof by Cases
Divide the problem into exhaustive cases and prove each separately.
Example: Prove that n² + n is even for all integers n.
Proof:
- Case 1: n is even. Then n = 2k, so n² + n = 4k² + 2k = 2(2k² + k), which is even.
- Case 2: n is odd. Then n = 2k + 1, so n² + n = (2k + 1)² + (2k + 1) = 4k² + 6k + 2 = 2(2k² + 3k + 1), which is even. ∎
Existence and Uniqueness Proofs
Existence proofs show that an object with certain properties exists.
- Constructive: Explicitly exhibit the object
- Non-constructive: Prove existence without constructing the object (often using contradiction)
Example (constructive): Prove there exists a rational number between 0 and 1.
Proof: Take r = 1/2. Then 0 < 1/2 < 1 and 1/2 ∈ ℚ. ∎
Uniqueness proofs show there is exactly one such object. Typically: assume two objects x and y both satisfy the property, then prove x = y.
Common Proof Patterns
Proving Set Equalities
To prove A = B, show A ⊆ B and B ⊆ A.
Example: Prove that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Proof sketch: Take arbitrary x in LHS, show x is in RHS (and vice versa).
Infinitude of Primes
Theorem (Euclid): There are infinitely many primes.
Proof: Suppose there are finitely many primes: p₁, p₂, …, pₙ. Consider N = p₁p₂…pₙ + 1. Then N is not divisible by any pᵢ (remainder 1). So either N is prime, or N has a prime factor not in our list. Contradiction. ∎
Divisibility Arguments
To prove a | b (a divides b), show b = ak for some integer k.
Reading and Writing Proofs
Reading proofs:
- Read actively with pen and paper
- Verify each step yourself
- Identify the proof technique being used
- Ask “why?” at each step
Writing proofs:
- Start with what you know and what you want to show
- Write in complete sentences
- Justify each step
- Be precise with definitions
- Introduce variables clearly (“Let n be an integer…“)
- End with a clear conclusion (∎ or QED)
Common pitfalls:
- Assuming what you need to prove
- Using examples as proof (examples are not proofs!)
- Circular reasoning
- Incomplete case analysis
Glossary
| Term | Definition |
|---|---|
| Axiom | A statement accepted as true without proof |
| Theorem | A significant result that has been proven |
| Lemma | A helper result used to prove a theorem |
| Corollary | A result that follows easily from a theorem |
| Proposition | A minor theorem |
| Conjecture | A statement believed to be true but not yet proven |
| QED | ”Quod erat demonstrandum” — that which was to be demonstrated |
Learning Resources
Books
- How to Prove It by Daniel Velleman — excellent introduction to proof techniques
- How to Solve It by George Pólya — classic on problem-solving strategies
- Introduction to Mathematical Thinking by Keith Devlin
- A Gentle Introduction to the Art of Mathematics — https://osj1961.github.io/giam/
Courses
- Introduction to Mathematical Thinking (Coursera, Stanford)