Infinity and Cardinals
In 1874 Cantor proved that ℝ has strictly more elements than ℕ - one infinity larger than another. Kronecker called him a 'corrupter of youth.' His diagonal trick later powered Gödel's incompleteness and Turing's halting problem.
- Data compression: not all files can be compressed (countably many programs, uncountably many files)
- Relational databases are countable structures; real numbers are uncountable
- Random numbers: most real numbers are not computable
Cantor and Infinity
Georg Cantor developed set theory and transfinite numbers in the 1870s-1890s. His colleagues met his work with hostility: Kronecker called him a 'corrupter of youth', Poincaré called it a 'disease'. Cantor himself suffered from depression. Posthumously, his work was recognized as the foundation of mathematics.
Countable Sets
A set A is countable if it is finite or in bijection with ℕ. An infinite countable set has cardinality ℵ₀. Examples: ℤ, ℚ, all algebraic numbers, all finite words over a finite alphabet.
Is ℚ (the set of rational numbers) countable?
Uncountable Sets
Cantor's diagonal argument (1891): ℝ is uncountable. Suppose all real numbers in [0,1] can be listed. Build a number differing from the n-th number in the n-th digit. It doesn't match any number in the listing. Contradiction.
The diagonal argument is one of the most reused tools in mathematics. It proves ℝ is uncountable, the undefinability of truth (Tarski), the undecidability of the halting problem (Turing), and Gödel's incompleteness theorems. In every case-the same structure of self-reference.
What tool does Cantor's diagonal argument use to prove the uncountability of ℝ?
Cantor's Theorem and the Hierarchy of Infinities
Cantor's theorem: for any set A, |A| < |P(A)|. This means there is no largest cardinal: ℵ₀ < 2^ℵ₀ < 2^(2^ℵ₀) < ... There are infinitely many infinities.
What follows from Cantor's theorem |A| < |P(A)|?
The Continuum Hypothesis
The Continuum Hypothesis (CH): there is no cardinal κ such that ℵ₀ < κ < 2^ℵ₀. That is, 2^ℵ₀ = ℵ₁-the cardinality of the continuum equals the next cardinal after ℵ₀.
Cohen's forcing is a revolutionary method in set theory. It allows systematically adding new sets to a model of ZFC without violating the axioms. Since then, forcing has become the main tool for proving independence of statements from ZFC.
Independence of CH means it is false (or meaningless)
Independence means: neither CH nor ¬CH contradicts ZFC. This doesn't mean CH 'has no answer'-just that ZFC axioms are too weak to settle it. Additional axioms (large cardinals) may make it decidable.
The situation is analogous to Euclid's fifth postulate: it's independent of the other axioms of geometry. Accepting it or rejecting it gives different, but equally consistent, geometries.
The Continuum Hypothesis?
Review the concept above.
Infinity and Cardinals: Key Takeaways
- Countable sets: |A| = ℵ₀, bijection with ℕ; ℚ and ℤ are countable
- Diagonal argument: ℝ is uncountable; same method in Tarski, Gödel, and Turing theorems
- Cantor's theorem: |A| < |P(A)|-the hierarchy of infinities is infinite
- Cardinality of the continuum: 2^ℵ₀ = |ℝ|-where does it sit in the ℵ hierarchy?
- CH is independent of ZFC (Gödel 1938, Cohen 1963)-forcing as a method
Toward Recursive Functions
Cantor's diagonal argument returns in computability theory: there are uncountably many functions from ℕ to ℕ but only countably many algorithms-most functions are uncomputable. The next lesson builds computability theory.
- ml-10 — Related lesson
Вопросы для размышления
- There are only countably many computable real numbers. What does this mean for practical computation?
- If CH is independent of ZFC, is there physical meaning to the question of whether a cardinal exists between ℵ₀ and |ℝ|?
- Cohen's forcing allows adding new real numbers to a model. What does it mean to 'add' a real number that 'didn't exist before'?