Cardinality: Countable and Uncountable Sets

Are there more rational numbers than natural numbers? The rationals are dense, with a third between any two, while the naturals are spread out one unit apart; and yet the answer is no, because the rationals can be listed. Are there more real numbers than rationals? Yes: no list of real numbers, however cleverly it is made, contains them all. This chapter makes “more” exact, with bijections and injections in place of counting, and proves both answers. It then shows that there is no largest size at all: by Cantor’s theorem, the set of subsets of any set is strictly bigger than the set itself. A second motivating question comes from school: why does $0.999\ldots = 1$ need a definition at all? The answer is in Section 3.4, where a decimal expansion is defined with finite sums only, and $0.999\ldots = 1$ becomes true by that definition.

On the way the chapter meets a principle that the rules of logic and the working rules for sets do not supply: making infinitely many arbitrary choices at once. The obvious proof that a countable union of countable sets is countable needs a list of every set of the family at the same time, and no rule produces one. The chapter states the missing principle as the axiom of choice, marks the line of each proof that uses it, and shows how often a rule (the least element, a formula) makes it unnecessary. The finite sets come first, with the pigeonhole principle and the facts about counting that the earlier chapters took on trust.

What you need. Logic and Proof, Chapters 1–8, and Sets, Relations, and Cardinality, Chapters 1–2. Induction (Logic and Proof, Axiom 4.2.1) from Logic and Proof, Chapter 4. From Logic and Proof, Chapter 5, the rule $\mathrm{\exists E}$ (Logic and Proof, Definition 5.6.1): Section 3.3 shows why one use of it names one object and cannot name infinitely many. From Logic and Proof, Chapter 8, the catalogue of what a proof may not do (Logic and Proof, Example (What is not allowed)). From Chapter 1: sets cut out by a property (Definition 1.1.3) and Russell’s theorem (Theorem 1.1.4); power sets, families and their unions (Definition 1.2.2, Definition 1.2.3, Definition 1.2.4); ordered pairs and products (Definition 1.3.1, Definition 1.3.2); functions, the empty function and equality of functions (Definition 1.4.1, Proposition 1.4.2, Proposition 1.4.1); injective, surjective and bijective maps and their composites (Definition 1.4.3, Definition 1.4.4, Theorem 1.4.4); inverses (Theorem 1.5.4, Theorem 1.5.1, Proposition 1.5.2); images and preimages (Definition 1.6.1, Definition 1.6.2). From Chapter 2: the arithmetic of $\mathbb{N}$ and $\mathbb{Z}$ (Lemma 2.1.1, Proposition 2.1.2), well-ordering (Theorem 2.1.3), induction from any base (Theorem 2.2.1), the division algorithm (Theorem 2.2.3), definition by recursion (Theorem 2.3.1), and powers and sums (Definition 2.3.2, Proposition 2.3.4, Definition 2.3.1, Proposition 2.3.6). The arithmetic and order of $\mathbb{R}$ are school facts in examples, as in the earlier chapters. Section 3.4 states three school facts about decimal expansions, (D1)–(D3), and Sections 3.4–3.5 use them by name without proof; Section 3.3 uses one fact from school algebra, that a non-zero polynomial of degree $d$ has at most $d$ real roots.

Time. About 30 hours on the core track (all of A, one B and one C per section, the exit checks); about 40 hours for everything.

Roadmap

Equinumerous sets and finite sets. “The same size” defined by a bijection, finite sets and their number of elements, the pigeonhole principle and the uniqueness of that number, subsets, disjoint unions and the $2^n$ subsets of an $n$ -element set, and the theorem that no finite set is equinumerous with a proper subset, which Hilbert’s hotel turns into a proof that $\mathbb{N}$ is infinite.
Countable sets. Countable as listable with repetitions allowed (empty, or the image of $\mathbb{N}$ ), the equivalent forms “an injection into $\mathbb{N}$ ” and “finite or countably infinite”, closure under subsets, images, unions of two sets and finite products, and the countability of $\mathbb{N} \times \mathbb{N}$ , $\mathbb{Z}$ and $\mathbb{Q}$ .
Countable unions and the axiom of choice. The step in the proof for countable unions that no rule justifies, the axiom of choice that licenses it, the constructions that look like choice and are not, right inverses of surjections, countable unions of countable sets, and the countability of the algebraic numbers.
Diagonal arguments: uncountable sets and Cantor’s theorem. The diagonal argument for 0–1 sequences, Cantor’s theorem that no map from a set onto its power set exists, decimal expansions defined with finite sums, the uncountability of $\mathbb{R}$ , and the existence of transcendental numbers.
Comparing sizes: the Schröder–Bernstein theorem. Comparing sizes by injections, its exchange with surjections at the price of choice, the Schröder–Bernstein theorem proved without choice, and every interval with more than one point equinumerous with $\mathbb{R}$ .
Infinite sets. Every infinite set contains a countably infinite subset (a stronger use of choice), so $\mathbb{N}$ is the smallest infinite size, and a set is infinite exactly when it is equinumerous with a proper subset of itself; the review exercises reach back across this volume and Logic and Proof.

Named moves

List it. To show that $A$ is countable, give a surjection $\mathbb{N} \to A$ or an injection $A \to \mathbb{N}$ , whichever is cheaper to write down and check; repetitions in a list are free. An injection only has to keep different elements apart, as $(m, n) \mapsto 2^m 3^n$ does for $\mathbb{N} \times \mathbb{N}$ .
The diagonal. Given any list, build an object that differs from the $n$ -th entry at the $n$ -th place. It is not on the list, and since the list was arbitrary, no list contains everything.
Injections both ways. To show $\left| A \right| = \left| B \right|$ , find an injection $A \to B$ and an injection $B \to A$ , and invoke the Schröder–Bernstein theorem; do not hunt for the bijection.
Name the choice. When a proof picks one object for each of infinitely many indices with no rule that names it, say at that line that the axiom of choice is used. When a rule names the object, such as the least element of a set of natural numbers or a formula, no choice is used.