Understand the concept of comparing infinite sets using bijections
Learn Georg Cantor's revolutionary discoveries about infinity
Master the definition and properties of countable sets
Prove that ℤ and ℚ are countable despite intuition
Understand Cantor's diagonalization proof that ℝ is uncountable
Grasp the hierarchy of infinite cardinalities and its implications
10.1 The Question
🤔 Are some infinities larger than others?
Is |ℕ| < |ℤ|? (Are there more integers than natural numbers?)
Is |ℤ| < |ℚ|? (Are there more rationals than integers?)
Is |ℚ| < |ℝ|? (Are there more reals than rationals?)
👨🔬 Studied by: Georg Cantor (1870s)
Georg Cantor revolutionized mathematics by showing that not all infinities are equal. His work initially faced strong opposition but is now fundamental to mathematics.
🔧 Tool: Use bijections to compare infinite sets
Two sets have the same cardinality if and only if there exists a bijection between them.
10.2 Countable Sets
🔑 Definition: Countable Set
A set X is countable if there exists a bijection f: ℕ → X
Interpretation:
Can enumerate X as {f(0), f(1), f(2), ...}
X can be "counted" via f
X has same cardinality as ℕ
ℕ is Countable (by definition)
Identity function works: f(n) = n
This gives us our baseline for comparison.
10.3 Are Integers Countable?
🤯 Intuition vs Reality
Intuition: ℤ seems twice as large as ℕ (has negative numbers too)
Surprising Result: ℤ is countable!
📊 Bijection Strategy
Interleave positive and negative integers. Map ℕ → ℤ as follows:
ℕ
0, 1, 2, 3, 4, 5, 6, ...
↓
ℤ
0, 1, -1, 2, -2, 3, -3, ...
Explicit Formula:
f(0) = 0
f(i) = (i+1)/2 if i is odd
f(i) = -(i/2) if i is even (and i > 0)
Uncountable Infinities:
|ℝ| > |ℚ| (reals are uncountable)
🌟 About Irrational Numbers
ℚ is countable
ℝ = ℚ ∪ {irrationals}
ℝ is uncountable
Therefore: Irrational numbers are uncountable
There are VASTLY more irrational numbers than rational numbers!
🔍 Even Tiny Intervals
Even the tiny interval (0, 1) is uncountable
Any non-trivial interval of reals is uncountable
This shows how "dense" the irrationals really are
10.7 Continuum Hypothesis
❓ The Ultimate Question
Question: Is there a set whose cardinality is strictly between |ℕ| and |ℝ|?
🏛️ Historical Importance:
Posed by Cantor in late 1800s
One of the most important open questions in set theory
Listed as Hilbert's First Problem (1900)
🎯 Resolution by Paul Cohen (1960s):
Proved the Continuum Hypothesis is independent of set theory axioms
Cannot be proven true or false from standard axioms
One of the most profound results in mathematical logic
Shows the limitations of axiomatic systems
🧮 Practice Problems
Problem 1: Bijection Construction
Show that the set of even natural numbers {0, 2, 4, 6, 8, ...} is countable by constructing an explicit bijection with ℕ.
Solution:
Bijection f: ℕ → {even naturals}
f(n) = 2n
f(0) = 0
f(1) = 2
f(2) = 4
f(3) = 6
...
This is clearly injective (different inputs give different outputs) and surjective (every even natural is 2n for some n). Therefore, the even naturals are countable.
Problem 2: Understanding Cardinalities
Explain why |ℕ × ℕ| = |ℕ| even though ℕ × ℕ seems "two-dimensional".
Solution:
The diagonal enumeration shows we can systematically count all pairs:
Organize by sum: Group pairs (a,b) by their sum a+b
Within each group, enumerate systematically
This creates a bijection ℕ → ℕ × ℕ
Key insight: Even though ℕ × ℕ appears "bigger" (two-dimensional), we can still count all pairs in a systematic way. Cardinality depends on the existence of a bijection, not on intuitive "size."
Problem 3: Diagonalization Understanding
In Cantor's diagonalization proof, why can't the diagonal sequence d be in our original enumeration?
Solution:
By construction, d cannot be anywhere in the list:
d ≠ s₁ because they differ in position 1
d ≠ s₂ because they differ in position 2
d ≠ s₃ because they differ in position 3
Generally: d ≠ sₙ because they differ in position n
This is the genius of the proof: We construct d specifically to differ from every sequence in our supposed "complete" enumeration, showing that no such complete enumeration can exist.
Problem 4: Cardinality Hierarchy
Arrange the following sets in order of increasing cardinality: ℝ, ℚ, ℤ, ℕ, {irrational numbers}.