Set Theory Guide: Foundations, Cardinals, and the Axiom of Choice
Introduction
Set theory is the foundation upon which all of modern mathematics is built. Every mathematical object — numbers, functions, spaces, groups, rings, manifolds — can be defined in terms of sets. This reduction to a single primitive concept is one of the great achievements of mathematical thought, providing a unified framework for the entire discipline.
The development of set theory was driven by the need to understand infinity. Cantor’s revolutionary work in the 1870s showed that infinite sets come in different sizes, that some infinities are larger than others, and that there is no largest infinity. These discoveries were met with resistance from some contemporaries — Kronecker called Cantor a corrupter of youth — but eventually became central to mathematics.
Naive Set Theory and Paradoxes
Naive set theory, as developed by Cantor, allowed any definable collection to be a set. This freedom led to paradoxes. Russell’s paradox asks whether the set of all sets that do not contain themselves contains itself. Either answer leads to a contradiction, showing that unrestricted set comprehension is inconsistent.
ZFC Axioms
The Zermelo-Fraenkel axioms with the Axiom of Choice (ZFC) resolve these paradoxes by restricting which collections count as sets. The axioms specify: Extensionality (sets with the same elements are equal), Foundation (no infinite descending ∈-chains), Empty Set, Pairing, Union, Power Set, Infinity, Separation (restricted comprehension), Replacement (images of sets under functions are sets), and Choice.
The axiom of foundation deserves special mention. It ensures that sets are well-founded — there is no infinite descending membership chain. This allows induction on sets and prevents the kind of circularity that leads to paradoxes. The connection between set theory and logic is deep and essential.
Ordinal Numbers
Ordinal numbers extend the counting numbers into the transfinite. An ordinal represents a position in a well-ordered sequence. The finite ordinals are 0, 1, 2, … corresponding to the natural numbers. The first infinite ordinal is ω, followed by ω + 1, ω + 2, …, ω + ω = ω·2, and so on.
Transfinite Induction
Transfinite induction and recursion generalize ordinary mathematical induction to the ordinals. To prove a statement P(α) for all ordinals α, one proves P(0), that P(α) implies P(α + 1), and that P holds at limit ordinals if it holds at all smaller ordinals.
The ordinal arithmetic operations of addition, multiplication, and exponentiation extend the familiar operations. Unlike finite arithmetic, ordinal arithmetic is not commutative: 1 + ω = ω, while ω + 1 ≠ ω.
Cardinal Numbers
Cardinal numbers measure the size of sets. Two sets have the same cardinality if there exists a bijection between them. Finite cardinals are natural numbers. The cardinality of the natural numbers is ℵ₀ (aleph-null). The cardinality of the real numbers is 2^ℵ₀, also called the continuum.
Cantor’s Theorem
Cantor’s Theorem states that the power set of any set has strictly larger cardinality than the set itself. This theorem has profound consequences: there is no largest cardinal, and there are infinitely many levels of infinity. The proof uses a diagonal argument that has become one of the most versatile techniques in logic and proof theory.
The Continuum Hypothesis (CH) asserts that there is no cardinal strictly between ℵ₀ and 2^ℵ₀. Cohen proved in 1963 that CH is independent of ZFC — it can neither be proved nor disproved from the axioms. This result inaugurated the era of independence proofs in set theory.
Axiom of Choice
The Axiom of Choice (AC) states that for any collection of nonempty sets, there exists a choice function selecting one element from each set. AC is independent of the other ZF axioms: both ZF + AC (ZFC) and ZF + ¬AC are consistent (if ZF is consistent).
Consequences of the Axiom of Choice
AC implies many theorems that seem intuitively obvious: the Cartesian product of nonempty sets is nonempty, every vector space has a basis, every set can be well-ordered. However, AC also implies counterintuitive results like the Banach-Tarski paradox: a solid ball can be decomposed into finitely many pieces and reassembled into two balls of the same size.
The debate over AC has been one of the most fascinating in mathematics. Constructivists reject AC because it asserts existence without providing a construction. Most working mathematicians accept AC because it simplifies proofs and seems to cause no contradictions in practice.
Large Cardinals
Large cardinal axioms assert the existence of very large infinite cardinals with strong closure properties. Inaccessible cardinals, measurable cardinals, Woodin cardinals, and supercompact cardinals form a hierarchy of increasing strength. These axioms cannot be proved from ZFC (assuming ZFC is consistent), but they are consistent with ZFC and have fruitful consequences.
The study of large cardinals connects set theory to model theory, inner model theory, and descriptive set theory. Large cardinals provide a yardstick for measuring the consistency strength of mathematical statements.
Descriptive Set Theory
Descriptive set theory studies the complexity of subsets of Polish spaces — completely metrizable separable topological spaces. The Borel hierarchy classifies sets by the number of iterations of complement and countable union needed to construct them from open sets. The projective hierarchy extends beyond Borel sets using continuous images.
The theory of determinacy states that under certain large cardinal assumptions, every projective set of reals is determined — in the infinite game where players alternate picking digits, one player has a winning strategy. The axiom of projective determinacy has profound consequences for the behavior of projective sets and connects set theory to analysis.
Forcing and Independence Proofs
Forcing, invented by Paul Cohen in 1963, is the most powerful technique for proving independence results in set theory. Cohen used forcing to prove that the continuum hypothesis is independent of ZFC — it can neither be proved nor disproved from the axioms.
Forcing extends a countable transitive model of set theory by adding a generic set that encodes new information while preserving the axioms. The technique has been generalized enormously and is now used to prove independence for a vast range of mathematical statements. The connections between forcing and mathematical logic are deep and essential.
Applications in Mathematics
Set theory provides the language for all of modern mathematics. Topological spaces are defined as sets with additional structure. Groups and rings are sets with operations. Functions are sets of ordered pairs. The set-theoretic foundation ensures that all mathematical objects live in a single universe.
The concept of cardinality underlies measure theory, where countable additivity is a fundamental property. The Banach-Tarski paradox shows the limitations of finitely additive measures and motivates the search for countably additive measures.
Inner Model Theory
Inner model theory constructs canonical models of set theory that contain all ordinals and satisfy the ZFC axioms. Gödel’s constructible universe L is the smallest inner model, built by iterating definable subsets through the ordinals. The axiom V = L states that every set is constructible.
Gödel proved that if ZF is consistent, so is ZFC + V = L, establishing the relative consistency of the axiom of choice and the generalized continuum hypothesis. However, V = L imposes restrictions on large cardinals — measurable cardinals cannot exist in L.
Core Models
Core models generalize L to accommodate large cardinals. The Dodd-Jensen core model K, the Steel core model for Woodin cardinals, and the current inner model programs provide canonical inner models for increasingly strong large cardinal axioms.
The connection between inner model theory and mathematical logic is essential. The study of inner models has led to deep results about the structure of the set-theoretic universe and the relationships between large cardinal axioms.
Ultrafilters and Nonstandard Analysis
An ultrafilter on a set is a maximal filter — a collection of subsets closed under finite intersections and supersets that contains either every set or its complement for any subset. Ultrafilters are essential in model theory and topology. The Stone-Čech compactification of a discrete space is the space of ultrafilters.
Nonstandard analysis, developed by Abraham Robinson, uses ultrafilters to construct extensions of the real numbers that contain infinitesimal and infinite elements. A hyperreal number is an equivalence class of sequences of real numbers modulo an ultrafilter. The transfer principle states that true statements about the reals remain true about the hyperreals.
Applications of Nonstandard Methods
Nonstandard analysis provides an alternative foundation for calculus based on infinitesimals, recovering the intuition of Leibniz and Euler in a rigorous framework. The nonstandard proof of the Bolzano-Weierstrass theorem uses infinite indices to construct convergent subsequences.
Nonstandard methods have applications in measure theory, probability, and functional analysis. Loeb measure constructs standard measures from nonstandard counting measures. The nonstandard hull of a Banach space provides a rich extension that captures ultraproduct constructions.
What is the difference between a set and a class? A set is a collection that can be an element of other sets. A proper class is a collection too large to be a set, like the class of all sets.
Is the Continuum Hypothesis true? The Continuum Hypothesis is independent of ZFC. Whether it is true in some absolute sense is a matter of philosophical debate among set theorists.
Why is the axiom of choice controversial? AC implies existence without construction. The Banach-Tarski paradox shows that AC leads to consequences that conflict with geometric intuition.
What is the cardinality of the real numbers? The cardinality of R is 2^ℵ₀, the cardinality of the power set of the natural numbers. Whether this equals ℵ₁ is the Continuum Hypothesis.
Logic Foundations — Mathematical Proof Techniques — Number Theory Guide