21. Set Theory, Logic & Proof
CollegeEvery theorem in this course rests on a foundation of sets, logic, and rigorous proof. This closing chapter covers the language mathematicians use to state ideas precisely, and the techniques used to prove them beyond doubt.
Sets, logical connectives and proof techniques
A set is a well-defined collection of objects; x ∈ A means x is a member of A, and A ⊆ B means every element of A is also in B. Core operations: union A ∪ B, intersection A ∩ B, and complement Ac.
Logic combines statements with connectives: ∧ (and), ∨ (or), ¬ (not), → (implies), ↔ (if and only if). De Morgan's laws:
¬(P ∨ Q) = ¬P ∧ ¬Q
Quantifiers: ∀ ("for all") and ∃ ("there exists"). Standard proof techniques: direct proof (assume the hypothesis, derive the conclusion), proof by contradiction (assume the negation, derive an absurdity), proof by contrapositive, and proof by induction — establish a base case, then show each case implies the next.
Sets can even be compared in size beyond counting: a set is countably infinite if it can be matched one-to-one with ℕ. Cantor's diagonal argument shows the real numbers are uncountable — a strictly larger infinity than the naturals.
The grammar underneath every earlier chapter
Sets are just boxes for grouping things precisely; logic is the grammar that keeps an argument airtight, so a conclusion can't sneak in unearned. These tools were quietly at work all along: Chapter 6's proof that √2 is irrational is a proof by contradiction, and formulas like 1 + 2 + … + n = n(n+1)/2 are proved rigorously by induction, not just checked on a few examples.
Induction is best pictured as toppling a row of dominoes: showing the first domino falls (the base case), and that any falling domino knocks over the next (the inductive step), together guarantee that every domino falls — no matter how long the row is, even infinitely long. This is how mathematicians prove statements about "all positive integers" without checking each one individually.
Worked example: proof by induction
Prove by induction that 1 + 2 + … + n = n(n+1)/2 for every positive integer n.
- Base case (n = 1): LHS = 1. RHS = 1(2)/2 = 1. They match. ✓
- Inductive hypothesis: assume the formula holds for n = k, i.e. 1 + 2 + … + k = k(k+1)/2.
- Inductive step: show it then holds for n = k+1. Add (k+1) to both sides: 1 + … + k + (k+1) = k(k+1)/2 + (k+1).
- Factor the right side: (k+1)(k/2 + 1) = (k+1)(k+2)/2 — exactly the formula evaluated at n = k+1.
Answer: since the base case holds and each case implies the next, by induction the formula holds for all positive integers n. ∎
Test your understanding
What is the difference between ∀ and ∃?
∀ ("for all") claims something is true of every element, e.g. ∀x ∈ ℝ, x² ≥ 0 (true — every real square is non-negative). ∃ ("there exists") claims only that at least one example works, e.g. ∃x ∈ ℝ such that x² = 4 (true — x = 2 works, and so does x = −2).
State De Morgan's law for sets and explain it in words.
(A ∪ B)c = Ac ∩ Bc. In words: "not in A or B" is exactly the same as "not in A, AND not in B." If you're outside the combined region, you must be outside both pieces individually.
Why does Cantor's diagonal argument show the real numbers are uncountable?
Suppose, for contradiction, you could list every real number in [0,1] against the naturals, one per row of decimals. Build a new number by changing the n-th digit of the n-th listed number (say, add 1, wrapping 9 to 0). This new number differs from every number on the list in at least one digit, so it cannot appear anywhere on the list — contradicting the assumption that the list was complete. Hence no such listing exists, and the reals are strictly "more numerous" than the naturals.
What's the difference between a direct proof and a proof by contradiction?
A direct proof starts from the hypothesis and reasons forward, step by valid step, to the conclusion. A proof by contradiction instead assumes the opposite of what you want to prove, and shows that assumption leads to something impossible — which means the assumption must have been false, so the original claim is true. Chapter 6's proof that √2 is irrational is a proof by contradiction.
How the ideas connect
Every key idea in this chapter, branching from the core concept — use it to see the whole picture at a glance.
The process, step by step
Worked problems, step by step
Follow each solution line by line, then try to reproduce it on paper before moving on.
Example 1Prove by induction that 1 + 2 + ... + n = n(n+1)/2.
- Base: n=1 gives 1 = 1(2)/2, true
- Assume sum to k = k(k+1)/2
- Add k+1: k(k+1)/2 + (k+1) = (k+1)(k+2)/2
Example 2Prove that if n^2 is even then n is even, by contrapositive.
- Contrapositive: if n is odd then n^2 is odd
- Let n = 2k + 1
- n^2 = 4k^2 + 4k + 1 is odd
Now you try
Work each one out first, then tap to reveal the worked answer.