What is a Proof?
A proof is a valid argument that establishes the truth of a mathematical statement. It consists of a sequence of statements, where each statement is either:
- An axiom (a basic assumption accepted as true)
- A previously proven theorem
- A statement that logically follows from earlier statements using rules of inference
Why Study Proofs?
Proofs are essential in mathematics and computer science for several reasons:
- Establish Truth: Verify that statements are absolutely true, not just probably true
- Understand Concepts: Deep understanding comes from seeing why something is true
- Develop Reasoning: Train systematic and logical thinking
- Verify Algorithms: Prove that algorithms work correctly
- Foundation Building: Create a solid base for advanced topics
- Problem Solving: Develop analytical skills applicable beyond mathematics
Key Components of Proofs
1. Axioms (Postulates)
Basic statements accepted as true without proof.
Examples:
- In geometry: “Through any two points, there exists exactly one line”
- In algebra: “a + b = b + a” (commutative property)
- In logic: “p ∨ ¬p is always true” (law of excluded middle)
2. Definitions
Precise meanings of mathematical terms.
Examples:
- Even integer: An integer n is even if n = 2k for some integer k
- Prime number: A natural number p > 1 is prime if its only divisors are 1 and p
- Rational number: A number that can be expressed as a/b where a, b are integers and b ≠ 0
3. Theorems
Statements that have been proven to be true.
Examples:
- “The sum of two even numbers is even”
- “There are infinitely many prime numbers”
- “√2 is irrational”
4. Corollaries
Theorems that follow directly from other theorems.
Example:
- Theorem: n² is even if and only if n is even
- Corollary: If n² is odd, then n is odd
5. Lemmas
Helper theorems used to prove larger theorems.
Example:
- Lemma: If a | b and b | c, then a | c
- (Used to prove more complex divisibility theorems)
Basic Proof Terminology
Hypothesis (Assumption)
The “if” part of a conditional statement - what we assume to be true.
Example: In “If n is even, then n² is even”
- Hypothesis: “n is even”
Conclusion
The “then” part - what we want to prove.
Example: In “If n is even, then n² is even”
- Conclusion: “n² is even”
Necessary vs. Sufficient
p is sufficient for q: p → q (“if p, then q”)
- If p happens, q is guaranteed
p is necessary for q: q → p (“if q, then p”)
- q cannot happen without p
Example: Consider “breathing” and “living”
- Breathing is necessary for living (can’t live without breathing)
- Breathing is not sufficient for living (breathing alone doesn’t guarantee living - need food, water, etc.)
Types of Proofs: Quick Overview
1. Direct Proof
Start with the hypothesis, deduce the conclusion step by step.
Structure:
Assume p.
[logical steps]
Therefore q.2. Indirect Proof (Contrapositive)
Instead of proving p → q, prove ¬q → ¬p.
Structure:
To prove p → q, we prove ¬q → ¬p.
Assume ¬q.
[logical steps]
Therefore ¬p.3. Proof by Contradiction
Assume the opposite of what you want to prove, show it leads to a contradiction.
Structure:
Suppose, for contradiction, that ¬p.
[logical steps]
This contradicts [known fact].
Therefore p.4. Proof by Cases
Divide the problem into exhaustive cases and prove each separately.
Structure:
Case 1: [condition]
[proof for case 1]
Case 2: [condition]
[proof for case 2]
All cases covered, therefore statement is true.Understanding Logical Equivalence in Proofs
Important Equivalences
-
p → q ≡ ¬q → ¬p (Contrapositive)
- Can prove either form
-
p → q ≡ ¬p ∨ q
- “If p then q” = “not p or q”
-
p ↔ q ≡ (p → q) ∧ (q → p)
- To prove “if and only if”, prove both directions
-
¬(p → q) ≡ p ∧ ¬q
- Negation of implication
Non-Equivalences (Common Mistakes!)
-
p → q NOT≡ q → p (Converse)
- These are different!
- Example: “If it rains, ground is wet” ≠ “If ground is wet, it rains”
-
p → q NOT≡ ¬p → ¬q (Inverse)
- These are different!
- Example: “If you study, you pass” ≠ “If you don’t study, you don’t pass”
Writing a Good Proof: Guidelines
1. State What You’re Proving Clearly
Good: “Theorem: For all integers n, if n is even, then n² is even.”
Bad: “Let’s prove something about even numbers.”
2. Start with the Right Assumption
For direct proof: “Assume n is even.”
For proof by contradiction: “Suppose, for the sake of contradiction, that n is odd.”
3. Use Definitions Precisely
Good: “Since n is even, by definition n = 2k for some integer k.”
Bad: “Since n is even, it’s like 2, 4, 6, etc.”
4. Show Each Step Clearly
Don’t skip steps - each line should follow logically from previous lines.
Good:
n = 2k (definition of even)
n² = (2k)² (squaring both sides)
n² = 4k² (expanding)
n² = 2(2k²) (factoring out 2)5. End with a Clear Conclusion
Good: “Since n² = 2(2k²) where 2k² is an integer, n² is even. ✓”
Bad: “So yeah, it’s even.”
6. Use Mathematical Symbols Correctly
Good: ∀, ∃, ∈, ∈, ⊂, ≤, ≥, ≡, →
Bad: Mixing symbols incorrectly or using them as abbreviations in sentences
First Simple Proofs
Example 1: Sum of Even Numbers
Theorem: The sum of two even integers is even.
Proof: Let m and n be even integers.
By definition of even:
- m = 2a for some integer a
- n = 2b for some integer b
Then: m + n = 2a + 2b = 2(a + b)
Since a + b is an integer, m + n = 2(a + b) is even by definition.
Therefore, the sum of two even integers is even. ✓
Example 2: Product with Even
Theorem: The product of any integer with an even integer is even.
Proof: Let m be any integer and let n be an even integer.
By definition, n = 2k for some integer k.
Then: m × n = m × 2k = 2(mk)
Since mk is an integer, m × n = 2(mk) is even by definition.
Therefore, the product of any integer with an even integer is even. ✓
Example 3: Odd Times Odd
Theorem: The product of two odd integers is odd.
Proof: Let m and n be odd integers.
By definition of odd:
- m = 2a + 1 for some integer a
- n = 2b + 1 for some integer b
Then: m × n = (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1
Since 2ab + a + b is an integer, m × n = 2(2ab + a + b) + 1 is odd by definition.
Therefore, the product of two odd integers is odd. ✓
Example 4: Divisibility Property
Theorem: If a | b and b | c, then a | c.
Proof: Assume a | b and b | c.
By definition of divisibility:
- a | b means b = ak for some integer k
- b | c means c = bm for some integer m
Substituting: c = bm = (ak)m (since b = ak) = a(km)
Since km is an integer, a | c by definition.
Therefore, if a | b and b | c, then a | c. ✓
Common Proof Patterns
Pattern 1: Proving “For All” Statements (∀x P(x))
- Let x be an arbitrary element of the domain
- Show P(x) is true
- Since x was arbitrary, P(x) is true for all x
Example: Prove ∀n ∈ ℤ, n² ≥ 0
Let n be any integer.
If n > 0, then n² = n × n > 0 (positive times positive) If n = 0, then n² = 0 If n < 0, then n² = n × n > 0 (negative times negative)
In all cases, n² ≥ 0. ✓
Pattern 2: Proving “There Exists” Statements (∃x P(x))
- Find a specific example x₀
- Show P(x₀) is true
- Conclude ∃x P(x)
Example: Prove ∃n ∈ ℤ, n² = n
Consider n = 1.
Then n² = 1² = 1 = n.
Therefore, there exists an integer n such that n² = n. ✓
(Note: n = 0 also works)
Pattern 3: Proving “If and Only If” (p ↔ q)
- Prove p → q (forward direction)
- Prove q → p (backward direction)
- Conclude p ↔ q
Example: Prove n is even ↔ n + 2 is even
Forward (⇒): Assume n is even, so n = 2k. Then n + 2 = 2k + 2 = 2(k + 1), which is even. ✓
Backward (⇐): Assume n + 2 is even, so n + 2 = 2k. Then n = 2k - 2 = 2(k - 1), which is even. ✓
Therefore, n is even ↔ n + 2 is even. ✓
Counterexamples
A counterexample is a single example that proves a statement is false.
When to Use Counterexamples
To disprove a universal statement ∀x P(x), find one x where P(x) is false.
Example 1: Disprove “All prime numbers are odd”
Counterexample: 2 is prime and even. ✗
Example 2: Disprove “If n² = 25, then n = 5”
Counterexample: n = -5 gives n² = 25, but n ≠ 5. ✗
Example 3: Disprove “For all real numbers x, x² > x”
Counterexample: x = 0 gives 0² = 0, not > 0. ✗
Vacuous and Trivial Proofs
Vacuous Proof
If the hypothesis is always false, then p → q is vacuously true.
Example: “If 0 = 1, then pigs can fly” is vacuously true because 0 ≠ 1.
Trivial Proof
If the conclusion is always true, then p → q is trivially true.
Example: “If n > 5, then n² ≥ 0” is trivially true because n² ≥ 0 is always true.
Common Beginner Mistakes
1. Assuming What You Want to Prove (Circular Reasoning)
Wrong:
We want to prove n² is even.
Assume n² is even.
...
Therefore n² is even.2. Proving the Converse Instead
Want to prove: If n is even, then n² is even
Wrong: Proving “If n² is even, then n is even” instead
3. Using Specific Examples as Proof
Wrong:
2 is even and 2² = 4 is even.
4 is even and 4² = 16 is even.
Therefore, if n is even, n² is even.Right: Use general n = 2k, not specific values
4. Incomplete Case Analysis
Wrong: Forgetting case n = 0 when dividing into positive and negative
5. Misusing “Therefore” and “Because”
Wrong: “Therefore n = 2k, because n is even”
Right: “Because n is even, we have n = 2k”
Key Points for Exams
- State definitions clearly at the start
- Show all steps - don’t skip logical connections
- Use correct mathematical language and symbols
- For ∀ statements, use arbitrary element, not specific
- For ∃ statements, provide specific example
- Label your proof method (direct, contrapositive, contradiction, etc.)
- End with a clear conclusion (QED or ✓)
- To disprove, give a counterexample
- Check your logic - does each step really follow?
- Write for someone else to understand, not just yourself
Practice Problems
-
Prove: The sum of an even integer and an odd integer is odd.
-
Prove: If n is odd, then n + 7 is even.
-
Prove: For all integers n, n(n + 1) is even.
-
Disprove: For all integers n, n² + n + 1 is prime.
-
Prove: If n² is divisible by 2, then n is divisible by 2.
-
Prove or disprove: For all real numbers x, |x + 1| = |x| + 1.
-
Prove: For all integers a, b, c, if a | b and a | c, then a | (b + c).
-
Prove: The square of an even number is divisible by 4.