Mathematical Logic
ZFC Set Theory
All of modern mathematics rests on 9 axioms. Numbers, functions, spaces, groups: all are sets, and all their properties are derived from these 9 statements. Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC) is the standard foundation of mathematics.
- The Axiom of Choice is equivalent to Zorn's Lemma; it is used in every proof of the existence of a basis in an arbitrary vector space
- Measure-theoretic theorems in analysis depend on ZFC
- The question P = NP may be independent of ZFC
Controversies over the Axiom of Choice
Zermelo formulated the Axiom of Choice (AC) in 1904 to prove the well-ordering theorem. It sparked fierce debate: some mathematicians found it self-evident, others found it unacceptably non-constructive. Banach and Tarski showed in 1924 that AC implies the paradoxical decomposition of a ball, the Banach-Tarski theorem.
The Axioms of ZFC
ZFC is built on a single relation of membership ∈. All mathematical objects are encoded as sets: number 0 = ∅, number 1 = {∅}, number 2 = {∅, {∅}}, and so on.
The Separation axiom is restricted: from a set x one can extract a subset {z ∈ x : φ(z)}. But collecting {z : φ(z)} for arbitrary φ is not allowed; this leads to Russell's paradox. This distinction is precisely what Zermelo introduced to fix Cantor's naive theory.
Why is the Separation axiom in ZFC restricted to the form {z ∈ x : φ(z)} rather than {z : φ(z)}?
Ordinals
An ordinal is a transitive set that is well-ordered by ∈. Ordinals generalize natural numbers to infinity: 0 = ∅, 1 = {∅}, 2 = {∅,{∅}}, ..., ω = ℕ, ω+1 = ω∪{ω}, ω+2, ..., ω·2, ..., ω², ..., ω^ω, ..., ε₀, ...
How does ω+1 differ from ω in ordinal theory?
Cardinals
A cardinal is an ordinal that is not in bijection with any smaller ordinal. Cardinals measure the 'size' of sets: |A| = |B| if and only if there exists a bijection between A and B.
Why does ℵ₀ · ℵ₀ = ℵ₀ (countable × countable = countable)?
The Axiom of Choice
The Axiom of Choice allows 'arbitrarily' constructing any set
AC guarantees the existence of a choice function but says nothing about how to construct it. It is non-constructive: we know a choice exists but cannot describe it explicitly in the general case.
This non-constructiveness sparked the controversy. Constructive mathematicians (Bishop, Martin-Löf) develop mathematics without AC, where every object must be built explicitly.
The Axiom of Choice?
Review the concept above.
ZFC Set Theory: Key Takeaways
- ZFC: 9 axioms, single primitive ∈, foundation of all mathematics
- Separation axiom is restricted: protection against Russell's paradox
- Ordinals: the 'length' of a well-order; cardinals: the 'size' of a set
- Cantor's theorem: |P(A)| > |A|; infinitely many uncountable cardinals
- AC is independent of ZF; it is equivalent to Zorn's Lemma and the well-ordering theorem
Toward the Infinity of Cardinals
ZFC generates a whole hierarchy of infinities, from ℵ₀ to the hierarchy of inaccessible cardinals. Cantor's Continuum Hypothesis: whether there is a cardinal between ℵ₀ and 2^ℵ₀, is also independent of ZFC.
- ml-09 — Related lesson
Вопросы для размышления
- The Banach-Tarski theorem: a ball can be decomposed into finitely many pieces and reassembled into two balls of the same size. How is this possible? What goes wrong?
- Zorn's Lemma says every vector space has a basis. Can a basis be explicitly exhibited for all real numbers ℝ over ℚ?
- If AC is independent of ZF, how important is it whether we accept it? What theorems would we 'lose'?