Set Theory Basics
Countability and the Axiom of Choice
Basics (undergraduate years 1–2)
About This Level
At the basic level we learn how to compare the “size” of infinite sets. Cantor's diagonal argument shows that infinity itself comes in a hierarchy. We then meet the axiom of choice together with its equivalent forms (Zorn's lemma and the well-ordering theorem), acquiring a powerful tool that modern mathematics uses as a matter of course.
Prerequisites
- The introductory material (sets, mappings, relations)
- An understanding of surjections, injections and bijections
- Reading and writing logical symbols
Contents
1. Power Sets and Cartesian Products
Building new sets from old ones.
- The power set $\mathcal{P}(A)$
- Ordered pairs and the product $A \times B$
- Products of $n$ sets
2. Comparing Cardinalities
The size of an infinite set.
- Equal cardinality $|A| = |B|$
- Comparison $|A| \leq |B|$
- The Cantor–Bernstein theorem
3. Countable Sets
Finite or countably infinite sets.
- Definition of a countable set
- Countability of the integers $\mathbb{Z}$
- Countability of the rationals $\mathbb{Q}$
4. Properties of Countable Sets
When countability is preserved.
- Infinite subsets of a countable set
- A countable union of countable sets
- Finite products
5. The Diagonal Argument
Cantor's revolutionary idea.
- Uncountability of 0-1 sequences and of the reals
- What the “diagonal” assignment means
- The pitfall of double decimal expansions
6. Cantor's Theorem
No set is as large as its own power set.
- The statement $|S| < |\mathcal{P}(S)|$
- Proof by the diagonal argument
- Going further: the continuum hypothesis and Cantor's paradox
7. The Cardinality of the Continuum
How big the reals are.
- $|\mathbb{R}| = |[0,1]| = |\mathcal{P}(\mathbb{N})|$
- The continuum $\mathfrak{c}$
- The cardinality of $\mathbb{R}^n$
8. The Cantor Set
An uncountable set of measure zero, built by removing middle thirds.
- Construction and ternary expansions
- Going further: self-similarity and Hausdorff dimension
- Going further: the Cantor function (devil's staircase)
9. The Axiom of Choice
Choosing without a rule.
- What the axiom asserts
- How it differs from finite choice
- Where it is genuinely needed
10. Zorn's Lemma
Existence of a maximal element.
- Partially ordered sets
- Chains and upper bounds
- The statement of Zorn's lemma
11. The Well-Ordering Theorem
Every set can be well-ordered.
- Definition of a well-order
- The statement of the theorem
- The three equivalences
12. Applications of the Axiom of Choice
Theorems that use the axiom.
- Existence of a basis of a vector space
- Maximal ideals
- Tychonoff's theorem
13. Consequences of the Axiom of Choice
Some strange results.
- Vitali sets
- The Banach–Tarski paradox
- Counterintuitive consequences of the axiom of choice
14. The Peano Axioms
Characterising the natural numbers axiomatically and constructing them inside set theory.
- The five axioms and the successor function
- Recursive definitions of addition and multiplication
- Categoricity of the second-order Peano axioms and the von Neumann construction
Going Deeper
Main Theorems
The Cantor–Bernstein theorem
If $|A| \leq |B|$ and $|B| \leq |A|$ then $|A| = |B|$. That is, if there are injections $f: A \to B$ and $g: B \to A$, then a bijection $h: A \to B$ exists as well.
Cantor's theorem
For every set $A$ we have $|A| < |\mathcal{P}(A)|$. In particular there is no surjection from $A$ onto $\mathcal{P}(A)$.
The diagonal argument
The set $\mathbb{R}$ of all real numbers (or $[0,1]$) is uncountable. There is no surjection from the natural numbers onto the reals.
The axiom of choice (AC)
Given a family $\{A_i\}_{i \in I}$ of non-empty sets, one may choose an element from each $A_i$ and form a new set out of the choices.
Zorn's lemma
In a non-empty partially ordered set $P$ in which every chain has an upper bound in $P$, a maximal element of $P$ exists.
Applications You Can Follow at This Level
In linear algebra
Every vector space has a basis (by Zorn's lemma). It is the general theorem, with its “every”, that requires the axiom of choice; for particular spaces a basis can sometimes be written down explicitly.
In algebra
Every proper ideal of a ring with unity is contained in a maximal ideal (Zorn's lemma). The existence of an algebraic closure of a field is also proved with Zorn's lemma.
In topology
A product of any family of compact spaces is compact (Tychonoff's theorem; in its general form it is equivalent to the axiom of choice).
Understanding infinity
The hierarchy $|\mathbb{N}| < |\mathbb{R}| < |\mathcal{P}(\mathbb{R})| < \cdots$ continues without end.
Study Tips
- Understand the diagonal argument: Cantor's idea is the central one for understanding infinite sets
- What the axiom of choice means: recognise that “being able to choose” is not self-evident
- The three equivalences: AC ⟺ Zorn ⟺ well-ordering
- Know the applications: see how an abstract axiom is used in concrete theorems
- A caveat about countable unions: that a countable union of countable sets is countable cannot be proved in ZF alone; it uses a weak choice principle such as countable choice. If an enumeration of each set is given in advance, however, no choice is needed. Chapter 4 meets it first, but its meaning becomes clear from Chapter 9 onward
Indexes
Definition Index (General Concepts)
A list of the terms, symbols and people appearing at this level.
Reading Pieces
A Full Hotel with Room to Spare [Reading]
An infinite hotel that takes in guests even when every room is occupied. From the trick of shifting rooms to countable versus uncountable, and on to Cantor's discovery that infinities come in different sizes — told at an easy pace.
Comparing Without Counting [Reading]
Sizes can be compared without counting. From a shepherd's pebbles to mappings as a measuring device, and on to the Cantor–Bernstein theorem: two one-way injections already make two sets the same size.
Choosing: A Small Yet Momentous Act [Reading]
Picking one item from each of infinitely many boxes. Why did so little a thing have to become an axiom? From Russell's socks and shoes to the surprise that the axiom of choice, Zorn's lemma and the well-ordering theorem are one and the same, and on to the Banach–Tarski paradox.