Tabla de contenido
How do we know that a mathematical theorem is true? It’s not enough to verify some cases or rely on intuition: we need a mathematical proof. In this guide, you’ll learn the main proof methods, from direct proof to mathematical induction.
What is a Mathematical Proof?
A mathematical proof is a rigorous logical argument that establishes the truth of a proposition, starting from axioms, definitions, and previously proven theorems.
Formal Definition
A proof is a finite sequence of propositions where each one is:
- An axiom (truth accepted without proof)
- A definition (agreed meaning of a term)
- A hypothesis (initial assumption of the theorem)
- A proposition derived from the previous ones using inference rules
Why are they important?
Proofs are what distinguishes mathematics from other sciences. While in physics or biology we accept theories because they work in practice, in mathematics we demand absolute certainty. Verifying a thousand cases is not enough; if there’s no proof, there’s no theorem. This rigor is what allows mathematical results to be eternal: what Euclid proved 2300 years ago is still as valid today as it was then.
| Aspect | Explanation |
|---|---|
| Certainty | They guarantee absolute truth, not probability |
| Universality | They prove for ALL cases, not just some |
| Foundation | They are the basis of all mathematical knowledge |
| Communication | They allow verification and sharing of results |
Structure of a Theorem
Every theorem has the form: “If P, then Q” (P → Q)
| Component | Name | Role |
|---|---|---|
| P | Hypothesis | What we assume to be true |
| Q | Thesis (or Conclusion) | What we want to prove |
| P → Q | Theorem | The complete implication |
Example:
- Theorem: If n is an even number, then n² is even.
- Hypothesis (P): n is an even number
- Thesis (Q): n² is even
Important note: Although we colloquially write the theorem as “If P, then Q” using the conditional symbol (→), when we prove that the theorem is true, we’re proving that P → Q is a tautology. Therefore, a proven theorem is really an implication (P ⇒ Q), that is, a conditional that is always true.
Proof Methods
There are several methods for proving theorems. The choice depends on the nature of the problem.
| # | Method | Central Idea | When to Use It |
|---|---|---|---|
| 1 | Direct | Assume P, deduce Q | General case, first attempt |
| 2 | Contraposition | Prove ¬Q → ¬P | When Q is easier to negate |
| 3 | Contradiction | Assume ¬(P→Q), reach absurdity | Existence, uniqueness, irrationality |
| 4 | Induction | Base case + inductive step | Properties of natural numbers |
| 5 | By Cases | Divide into subcases | When there are different scenarios |
| 6 | Counterexample | One case that refutes | To prove falsity |
1. Direct Proof
Direct proof is the most natural and common method. It consists of starting from the hypothesis and, through logical steps, arriving at the conclusion.
Structure
1. Assume P is true (hypothesis)
2. Apply definitions, axioms, and known theorems
3. Through logical steps, deduce that Q is true
4. Conclude: P → Q is proven ✓
Logical Scheme
Direct proof leverages the definition of the conditional:
To prove P → Q, we assume P and derive Q.
If we manage to derive Q from P, then P → Q is true.
Example 1: Even Numbers
Theorem: If n is an even number, then n² is an even number.
Proof:
| Step | Statement | Justification |
|---|---|---|
| 1 | Let n be an even number | Hypothesis |
| 2 | n = 2k, for some integer k | Definition of even number |
| 3 | n² = (2k)² | We square |
| 4 | n² = 4k² | We expand |
| 5 | n² = 2(2k²) | We factor out 2 |
| 6 | Let m = 2k², where m is an integer | k is an integer, so 2k² is an integer |
| 7 | n² = 2m | Substitution |
| 8 | n² is an even number | By definition of even number ∎ |
Note: The symbol ∎ (or the letters Q.E.D.) is written at the end of a proof to indicate it has been completed. Q.E.D. comes from Latin “Quod Erat Demonstrandum”, meaning “what was to be demonstrated”.
Example 2: Odd Numbers
Theorem: If n is an odd number, then n² is an odd number.
Proof:
| Step | Statement | Justification |
|---|---|---|
| 1 | Let n be an odd number | Hypothesis |
| 2 | n = 2k + 1, for some integer k | Definition of odd number |
| 3 | n² = (2k + 1)² | We square |
| 4 | n² = 4k² + 4k + 1 | We expand the binomial |
| 5 | n² = 2(2k² + 2k) + 1 | We factor |
| 6 | Let m = 2k² + 2k, where m is an integer | Operations with integers |
| 7 | n² = 2m + 1 | Substitution |
| 8 | n² is an odd number | By definition of odd number ∎ |
Example 3: Sum of Evens
Theorem: The sum of two even numbers is an even number.
Proof:
| Step | Statement | Justification |
|---|---|---|
| 1 | Let a and b be even numbers | Hypothesis |
| 2 | a = 2k₁ and b = 2k₂ | Definition of even number |
| 3 | a + b = 2k₁ + 2k₂ | Sum |
| 4 | a + b = 2(k₁ + k₂) | Common factor |
| 5 | Let m = k₁ + k₂ | m is an integer |
| 6 | a + b = 2m | Substitution |
| 7 | a + b is even | By definition ∎ |
Fun fact: This proof shows that the set of even numbers is closed under the addition operation. In algebra, this is known as the closure axiom: if you apply an operation to elements of a set and the result always belongs to the same set, that set is closed under that operation.
2. Proof by Contraposition
Proof by contraposition leverages the logical equivalence:
P → Q ≡ ¬Q → ¬P
Instead of proving “If P, then Q”, we prove its contrapositive: “If not Q, then not P”.
When to use it?
- When it’s difficult to work directly with P
- When ¬Q provides more useful information
- When the structure of Q allows for easier negation
Structure
1. We want to prove: P → Q
2. Instead, we prove: ¬Q → ¬P
3. We assume ¬Q (the negation of the conclusion)
4. Through logical steps, we deduce ¬P
5. Since ¬Q → ¬P is true, P → Q is also true ✓
Example 1: Even Squares
Theorem: If n² is even, then n is even.
Analysis:
- P: n² is even
- Q: n is even
- Contraposition: If n is NOT even, then n² is NOT even
- That is: If n is odd, then n² is odd
Proof (by contraposition):
| Step | Statement | Justification |
|---|---|---|
| 1 | Suppose n is odd | We assume ¬Q |
| 2 | n = 2k + 1 | Definition of odd |
| 3 | n² = (2k + 1)² = 4k² + 4k + 1 | Expansion |
| 4 | n² = 2(2k² + 2k) + 1 | Factorization |
| 5 | n² is odd | It has the form 2m + 1 |
| 6 | By contraposition, if n² is even, n is even | ∎ |
Example 2: Divisibility
Theorem: If n² is not divisible by 3, then n is not divisible by 3.
Contraposition: If n IS divisible by 3, then n² IS divisible by 3.
Proof:
| Step | Statement | Justification |
|---|---|---|
| 1 | Suppose n is divisible by 3 | Hypothesis (¬Q) |
| 2 | n = 3k for some integer k | Definition of divisibility |
| 3 | n² = (3k)² = 9k² | We square |
| 4 | n² = 3(3k²) | We factor |
| 5 | n² is divisible by 3 | We conclude ¬P |
| 6 | By contraposition, the original theorem is true | ∎ |
3. Proof by Contradiction (Reductio ad Absurdum)
Proof by contradiction is one of the most powerful methods. It’s based on the principle:
If assuming something is false leads to a contradiction, then it must be true.
Logical Foundation
It’s based on two principles:
- Principle of non-contradiction: A proposition cannot be T and F at the same time
- Law of excluded middle: A proposition is T or F, there’s no middle ground
Structure
1. We want to prove: P
2. We assume the opposite: ¬P (assumption for contradiction)
3. We derive logical consequences from ¬P
4. We reach a CONTRADICTION (something impossible)
5. We conclude: ¬P is false, therefore P is true ✓
Classic Example: √2 is Irrational
Theorem: √2 is an irrational number.
This is one of the most famous theorems, attributed to the Pythagoreans.
Proof (by contradiction):
| Step | Statement | Justification |
|---|---|---|
| 1 | Suppose √2 is rational | Assumption (¬P) |
| 2 | Then √2 = a/b, where a,b are integers with no common factors | Definition of rational, reduced form |
| 3 | 2 = a²/b² | We square |
| 4 | 2b² = a² | We multiply by b² |
| 5 | a² is even | It’s twice something |
| 6 | a is even | If a² is even, a is even (proven earlier) |
| 7 | a = 2c for some integer c | Definition of even |
| 8 | 2b² = (2c)² = 4c² | We substitute |
| 9 | b² = 2c² | We divide by 2 |
| 10 | b² is even, so b is even | Same argument as a |
| 11 | a and b are both even | From steps 6 and 10 |
| 12 | CONTRADICTION | We said a/b has no common factors, but both are divisible by 2 |
| 13 | The assumption is false, √2 is irrational | ∎ |
Example 2: Infinity of Primes
Theorem: There are infinitely many prime numbers. (Euclid, ~300 BCE)
Proof (by contradiction):
| Step | Statement | Justification |
|---|---|---|
| 1 | Suppose there’s a finite number of primes | Assumption |
| 2 | Let the complete list be: p₁, p₂, p₃, …, pₙ | All primes |
| 3 | Let’s construct N = (p₁ × p₂ × … × pₙ) + 1 | Product of all primes plus 1 |
| 4 | N > 1 and N is not divisible by any pᵢ | When dividing N by any pᵢ, the remainder is 1 |
| 5 | N is prime, or N has a prime divisor not in the list | By the fundamental theorem of arithmetic |
| 6 | In either case, there exists a prime not in the list | |
| 7 | CONTRADICTION | We said the list was complete |
| 8 | There are infinitely many prime numbers | ∎ |
Note: The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be expressed as a product of prime numbers in a unique way (except for the order of factors). For example: 60 = 2² × 3 × 5. In step 5, we use this theorem to assert that N, being greater than 1, must have at least one prime divisor.
4. Proof by Mathematical Induction
Mathematical induction is the method for proving properties that apply to all natural numbers (or from a certain value onwards).
Intuitive Idea
It’s like an infinite row of dominoes:
- If the first domino falls (base case)
- And each domino, when falling, knocks down the next one (inductive step)
- Then ALL dominoes will fall
Formal Structure
To prove that P(n) is true for all n ≥ n₀:
Step 1: BASE CASE
Prove that P(n₀) is true
Step 2: INDUCTIVE HYPOTHESIS
Assume that P(k) is true for some k ≥ n₀
Step 3: INDUCTIVE STEP
Prove that P(k) → P(k+1)
That is, if P(k) is true, then P(k+1) is also true
CONCLUSION: P(n) is true for all n ≥ n₀
Example 1: Sum of Natural Numbers (Gauss’s Formula)
Theorem: For all \( n ≥ 1 \): \(1 + 2 + 3 + … + n = \frac{ n(n+1) }{2} \)
Proof by induction:
Base Case (n = 1):
| Left side | Right side | Equal? |
|---|---|---|
| 1 | 1(1+1)/2 = 1 | ✓ |
Inductive Hypothesis:
We assume that for some k ≥ 1:
Inductive Step (prove for k+1):
We must prove: \( 1 + 2 + … + k + (k+1) = \frac{(k+1)(k+2)}{2} \)
| Step | Expression | Justification |
|---|---|---|
| 1 | 1 + 2 + … + k + (k+1) | We want to simplify |
| 2 | = [k(k+1)/2] + (k+1) | By inductive hypothesis |
| 3 | = k(k+1)/2 + 2(k+1)/2 | Common denominator |
| 4 | = [k(k+1) + 2(k+1)]/2 | We add fractions |
| 5 | = [(k+1)(k + 2)]/2 | We factor out (k+1) |
| 6 | = (k+1)(k+2)/2 | This is exactly P(k+1) ✓ |
Conclusion: The theorem is true for all n ≥ 1 ∎
Example 2: Sum of Squares
Theorem: For all \( n ≥ 1 \): \( 1² + 2² + … + n² = \frac{ n(n+1)(2n+1)}{6} \)
Base Case (n = 1):
- Left side: 1² = 1
- Right side: 1(2)(3)/6 = 6/6 = 1 ✓
Inductive Hypothesis: We assume \( \color{red}{ K = 1² + 2² + … + k² = \frac{ k(k+1)(2k+1) }{ 6 } } \)
Inductive Step:
\( \begin{align} \color{red}{ K } & = \color{red}{ 1² + 2² + … + k² + ( \underline{k+1} )² } \\ & = \frac{ k(k+1)(2k+1)}{6} + (k+1)² \\ & = (k+1)[ \frac{k(2k+1)}{6} + (k+1)] \\ & = (k+1)[ \frac{k(2k+1) + 6(k+1)}{6} ] \\ & = (k+1)[ \frac{2k² + k + 6k + 6}{6} ] \\ & = (k+1)[ \frac{2k² + 7k + 6}{6} ] \\ & = \frac{ (k+1)(k+2)(2k+3) }{6} \\ & = \frac{ ( \underline{k+1} )(( \underline{k+1} )+1)(2( \underline{k+1} )+1) }{6} ✓ \end{align} \)
Conclusion: The theorem is true for all n ≥ 1 ∎
Example 3: Inequality
Theorem: For all n ≥ 1: 2ⁿ > n
Base Case (n = 1): 2¹ = 2 > 1 ✓
Inductive Hypothesis: We assume 2ᵏ > k for some k ≥ 1
Inductive Step:
| Step | Expression | Justification |
|---|---|---|
| 1 | 2ᵏ⁺¹ = 2 · 2ᵏ | Property of exponents |
| 2 | > 2 · k | By inductive hypothesis (2ᵏ > k) |
| 3 | = k + k | |
| 4 | ≥ k + 1 | Because k ≥ 1 |
Therefore, 2ᵏ⁺¹ > k + 1 ✓
Conclusion: 2ⁿ > n for all n ≥ 1 ∎
5. Proof by Cases
Proof by cases divides the problem into subcases that cover all possibilities.
Structure
1. Identify all possible cases (exhaustive)
2. Prove the conclusion for each case
3. Conclude that the theorem is true in all cases
Example 1: Parity of the Product
Theorem: For any integer n, n(n+1) is even.
Proof by cases:
Case 1: n is even
- n = 2k for some integer k
- n(n+1) = 2k(n+1) = 2[k(n+1)]
- It’s twice an integer, therefore it’s even ✓
Case 2: n is odd
- n+1 is even (the successor of an odd number is even)
- n+1 = 2m for some integer m
- n(n+1) = n(2m) = 2(nm)
- It’s twice an integer, therefore it’s even ✓
Conclusion: In both cases, n(n+1) is even ∎
Example 2: Absolute Value
Theorem: For every real number x: |x| ≥ 0
Proof by cases:
Case 1: x ≥ 0
- By definition, |x| = x
- Since x ≥ 0, then |x| ≥ 0 ✓
Case 2: x < 0
- By definition, |x| = -x
- Since x < 0, then -x > 0
- Therefore |x| > 0 ≥ 0 ✓
Conclusion: In all cases, |x| ≥ 0 ∎
6. Proof by Counterexample
A counterexample doesn’t prove that something is true; it proves that a universal claim is false.
Idea
To refute “For all x, P(x)”, it’s enough to find one single x where P(x) is false.
Examples
False claim 1: “All prime numbers are odd”
- Counterexample: 2 is prime and is even ✗
False claim 2: “n² > n for every positive integer n”
- Counterexample: For n = 1: 1² = 1, which is not greater than 1 ✗
False claim 3: “If n is odd, then n+2 is even”
- Counterexample: n = 3 is odd, but 3+2 = 5 is odd ✗
False claim 4: “The sum of two irrationals is irrational”
- Counterexample: √2 + (-√2) = 0, which is rational ✗
Common Errors in Proofs
1. Assuming what you want to prove (Begging the question)
Incorrect:
"Prove that a = b"
Step 1: Suppose a = b
Step 2: Then a - b = 0
Conclusion: a = b ✘
2. Proving only particular cases
Incorrect:
"Prove that n² ≥ n for all n ≥ 1"
For n = 2: 4 ≥ 2 ✓
For n = 5: 25 ≥ 5 ✓
Conclusion: It's true for all n ✘
Verifying examples is NOT a proof.
3. Forgetting the base case in induction
Without the base case, induction proves:
"If P(k) then P(k+1)"
But it never establishes that P is true for some initial value.
4. Dividing by zero or undefined quantities
Incorrect:
Let a = b
a² = ab
a² - b² = ab - b²
(a+b)(a-b) = b(a-b)
a + b = b ← we conclude this because we divided by (a-b), but a-b = 0! ✗
Connection with Propositional Logic
Proof methods are based on logical laws:
| Method | Logical Basis |
|---|---|
| Direct | P → Q (affirm antecedent, derive consequent) |
| Contraposition | P → Q ≡ ¬Q → ¬P |
| Contradiction | ¬P → Contradiction, therefore P |
| By cases | (P₁ → Q) ∧ (P₂ → Q) ∧ … ⊢ Q, if P₁ ∨ P₂ ∨ … is exhaustive |
The inference rules studied earlier are the tools we use in each step of the proof:
- Modus Ponens: To apply known theorems
- Hypothetical Syllogism: To chain implications
- Simplification/Conjunction: To handle compound propositions
Summary Table of Methods
| Method | Structure | Best for |
|---|---|---|
| Direct | Assume P, derive Q | First attempt, clear cases |
| Contraposition | Assume ¬Q, derive ¬P | When ¬Q gives more information |
| Contradiction | Assume ¬P, reach absurdity | Existence, irrationality |
| Induction | Base + Inductive step | Properties of ℕ |
| By Cases | Divide and conquer | Discrete variables |
| Counterexample | One case that refutes | Proving falsity |
Limitations of Proof Methods
Although proof methods are powerful tools, they have some inherent limitations that are important to know.
1. Gödel’s Incompleteness Theorems
In 1931, Kurt Gödel proved that in any sufficiently powerful formal system (like arithmetic):
- Incompleteness: There exist true propositions that cannot be proven within the system
- Consistency: The system cannot prove its own consistency
Implication: No matter what method you use, there will be mathematical truths that you simply cannot prove.
2. Proof by Contradiction: Non-Constructive Nature
Proof by contradiction has an important practical limitation:
- Proves existence without constructing: It can prove that something EXISTS without showing HOW to find or construct it
- Provides no algorithm: It doesn’t give you a method to obtain the object whose existence you proved
Example: We can prove that there are infinitely many primes, but the proof doesn’t give us an algorithm to find the next prime.
Philosophy: Intuitionist mathematicians (like Brouwer) reject this type of proof precisely because they are non-constructive.
3. Mathematical Induction: Doesn’t Discover, Only Verifies
Induction has a methodological limitation:
- Requires prior conjecture: You need to first suspect or intuit the pattern before you can prove it
- Not useful for discovery: Induction verifies hypotheses, it doesn’t generate them
Example: To prove that 1 + 2 + … + n = n(n+1)/2, someone first had to discover that formula by other means (observation, experimentation, intuition).
Summary of Limitations
| Method | Real Limitation |
|---|---|
| All (Gödel) | There exist unprovable truths |
| Contradiction | Non-constructive: doesn’t show how to build |
| Induction | Doesn’t discover, only verifies known patterns |
| Direct/Contraposition | No inherent limitations |
Practice Exercises
Exercise 1: Direct Proof
Prove: The sum of three consecutive even numbers is divisible by 6.
Hint: Let the numbers be 2k, 2k+2, 2k+4
Exercise 2: Contraposition
Prove: If n³ is odd, then n is odd.
Hint: Prove the contraposition: If n is even, then n³ is even
Exercise 3: Contradiction
Prove: √3 is irrational.
Hint: Follow the same scheme as √2
Exercise 4: Induction
Prove: For all n ≥ 1, 1 + 3 + 5 + … + (2n-1) = n²
Exercise 5: By Cases
Prove: For every integer n, n³ – n is divisible by 3.
Hint: Consider the cases n ≡ 0, 1, 2
Answers
Answer to Exercise 1
Theorem: The sum of three consecutive evens is divisible by 6.
Let 2k, 2k+2, 2k+4 be three consecutive even numbers.
Sum = 2k + (2k+2) + (2k+4) = 6k + 6 = 6(k+1)
Since the sum is 6 times an integer, it’s divisible by 6 ∎
Answer to Exercise 2
Contraposition: If n is even, then n³ is even.
Let n = 2k. Then n³ = (2k)³ = 8k³ = 2(4k³).
n³ is twice an integer, therefore it’s even.
By contraposition, if n³ is odd, n is odd ∎
Answer to Exercise 3
Suppose √3 = a/b with a,b having no common factors.
3 = a²/b², so 3b² = a², meaning a² is divisible by 3, and so is a.
Let a = 3c. Then 3b² = 9c², b² = 3c², b is divisible by 3.
Contradiction: a and b are both divisible by 3, but we said they had no common factors.
Therefore, √3 is irrational ∎
Answer to Exercise 4
Base case (n=1): 1 = 1² ✓
Hypothesis: \( \color{red}{ A = 1 + 3 + … + (2k-1) = k² } \)
Inductive step:
\( \begin{align} \color{red}{A} & = \color{red}{1 + 3 + … + (2k-1)} + (2(k+1)-1) \\ & = \color{red}{ k² } + (2k+1) \\& = k² + 2k + 1 \\ & = (k+1)² ∎ \end{align} \)
Answer to Exercise 5
n³ – n = n(n² – 1) = n(n-1)(n+1) = (n-1)n(n+1)
This is the product of three consecutive integers.
In any group of three consecutive numbers, at least one is divisible by 3.
Therefore, the product is divisible by 3 ∎
What’s Next?
In the next article, we’ll study logic circuits and a post with multiple propositional logic exercises.
Did you find this post useful? Leave me a comment with your questions or suggestions! And don’t forget to check out the next installment in this series on mathematical logic.