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.3, where a decimal expansion is defined with finite sums only, and $0.999\ldots = 1$ becomes true by that definition. Sections 3.1–3.4 teach one method of proof each on the way: list a set, name the choices a proof makes, run a diagonal, and compare sizes by injections both ways. The last section adds, multiplies and raises sizes to powers, and finds that the plane, the sequences of natural numbers and the subsets of $\mathbb{N}$ all have exactly as many elements as the line; it teaches two more methods, encode and decode, and prove a law of sizes by a bijection.

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. It starts from the finite sets of Section 2.5 and the pigeonhole principle.

What you need. Logic and Proof, Chapters 1–8, and Sets and Functions, 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.2 shows why one use of it names one object and cannot name infinitely many. From Logic and Proof, Chapters 2 and 6, excluded middle (Logic and Proof, Proposition 2.5.3) and the negation of quantifiers (Logic and Proof, Proposition 6.2.1). From Logic and Proof, Chapter 8, the catalogue of what a proof may not do (Logic and Proof, Example (What is not allowed)). The irrationality of $\sqrt 2$ (Logic and Proof, Theorem 2.2.1), used in one example of Section 3.1. From Chapter 1: the empty set and its uniqueness (Definition 1.2.4, Proposition 1.2.3); sets cut out by a property (Definition 1.2.3) and Russell’s theorem (Theorem 1.2.4); power sets, families and their unions (Definition 1.3.2, Definition 1.3.3, Definition 1.3.4); ordered pairs and products (Definition 1.4.1, Definition 1.4.2, Proposition 1.4.1); functions, the empty function and equality of functions (Definition 1.5.1, Proposition 1.5.2, Proposition 1.5.1); injective, surjective and bijective maps and their composites (Definition 1.5.3, Definition 1.5.4, Theorem 1.5.4), with the methods for proving injectivity and surjectivity (Example (Method: proving injectivity), Example (Method: proving surjectivity)); inverses (Definition 1.6.1, Theorem 1.6.4, Theorem 1.6.1, Proposition 1.6.2); images and preimages (Definition 1.7.1, Definition 1.7.2); the indicator function of a subset (Section 1.5, Example (First functions) (d)) and associativity of composition (Proposition 1.5.3). 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), powers and sums (Definition 2.3.2, Proposition 2.3.4, Definition 2.3.1, Proposition 2.3.6), and the largest element of a finite set of numbers (Proposition 2.3.8); equinumerous, finite and infinite sets (Definition 2.5.1, Proposition 2.5.1, Definition 2.5.2, Definition 2.5.3), removing a point and the uniqueness of the number of elements (Corollary 2.5.7, Corollary 2.5.4), the pigeonhole principle (Theorem 2.5.2, Corollary 2.5.3), subsets and disjoint unions of finite sets (Proposition 2.5.6, Proposition 2.5.5), the $2^n$ subsets of an $n$ -element set (Proposition 2.5.8), the number of elements of a product (Exercise (C2: Counting products and functions)), and the fact that no finite set is equinumerous with a proper subset (Theorem 2.5.9, Example (Hilbert’s Hotel)); and the methods of the least element and of pigeonhole (Example (Method: the least element), Example (Method: the pigeonhole principle)). The arithmetic and order of $\mathbb{R}$ are school facts in examples, as in the earlier chapters. Section 3.3 states three school facts about decimal expansions, (D1)–(D3), and Sections 3.3, 3.4 and 3.6 use them by name without proof; Section 3.2 uses one fact from school algebra, that a non-zero polynomial of degree $d$ has at most $d$ real roots.

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

Roadmap

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}$ ; the method: list a set, by a surjection from $\mathbb{N}$ or an injection into $\mathbb{N}$ .
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; the method: name each choice a proof makes.
Diagonal arguments: uncountable sets and Cantor’s theorem. The diagonal argument for 0–1 sequences, opening with the five-string game of Section 1.5, 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; the method: the diagonal.
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}$ ; the method: injections both ways; whether any two sets are comparable is left open.
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.
Cardinal arithmetic. Sums as disjoint unions, products and powers of sets compared by size; the laws $\left| X^{Y \sqcup Z} \right| = \left| X^Y \times X^Z \right|$ and $\left| (X^Y)^Z \right| = \left| X^{Y \times Z} \right|$ proved by bijections; subsets as 0–1 functions; no set of all sets, once more; and $\mathbb{R}$ , $\mathbb{R} \times \mathbb{R}$ , $\mathbb{N}^{\mathbb{N}}$ , $\mathbb{R}^{\mathbb{N}}$ and $\mathcal{P}\left( \mathbb{N} \right)$ all of one size; the methods: encode and decode, and prove a law of sizes by a bijection. The review exercises reach back across this volume and Logic and Proof.

Named moves

Each is a method box in the section named at the end of its line; the later sections use the move again.

List it (Example (Method: list it)). To show a set countable, give a surjection from $\mathbb{N}$ or an injection into $\mathbb{N}$ , whichever is cheaper to check; a list may repeat, and an injection only has to keep different elements apart. (Section 3.1)
Name the choice (Example (Method: name the choice)). When a proof picks one object for each of infinitely many indices and no rule names it, say at that line that the axiom of choice is used; a least element or a formula is a rule, and needs no choice. (Section 3.2)
The diagonal (Example (Method: 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. (Section 3.3)
Injections both ways (Example (Method: 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, instead of hunting for the bijection. (Section 3.4)
Encode and decode (Example (Method: build a bijection by encoding and decoding)). To build a bijection, say what an element must record, write the code and the decoder, and check both round trips. (Section 3.6)
A law by a bijection (Example (Method: prove a law of sizes by a bijection of sets)). To prove a law of sizes, write out an element of each side and regroup it into an element of the other side, never computing with $\left| \cdot \right|$ as if it were a number. (Section 3.6)

Threads

The five strings. Section 1.5 plants a game: write a string of five symbols not on a given list of five. Section 3.3 opens with the rule that always works (Example (Back to the five strings)), and the same rule, run on infinitely long strings, proves that the 0–1 sequences cannot be listed (Theorem 3.3.1).
Russell to Cantor. Russell’s theorem (Section 1.2) built a set that disagrees with each candidate on the candidate itself; Cantor’s theorem (Section 3.3, Theorem 3.3.2) is the same construction, as a theorem about sizes, and Section 3.6 proves the last clause of Russell’s theorem by sizes: a set of all sets would carry a surjection onto its power set (“No set of all sets, once more”).
Choice. Section 1.6 could not build a right inverse of an arbitrary surjection; Section 3.2 adds the axiom of choice that does (Axiom 3.2.1, Theorem 3.2.2), Section 3.5 uses it again (Theorem 3.5.1), and Chapter 6 states its strongest everyday form, Zorn’s lemma.
Comparability. Section 3.4 asks whether any two sets are comparable and leaves the question open; Section 6.2 answers it.
Same size. Section 2.5 defined it, Section 3.6 makes it arithmetic, and Section 4.2 names the requirement that arithmetic of sizes not depend on representatives: well-definedness.

Summary

Countable means listable (Definition 3.1.1), in three equivalent forms (Theorem 3.1.2). Countable sets are closed under subsets, images, finite products and, with the axiom of choice, countable unions (Theorem 3.2.3), so $\mathbb{Z}$ , $\mathbb{Q}$ and the algebraic numbers are countable. The diagonal shows that the 0–1 sequences, $\mathbb{R}$ and every power set are too big to be listed (Theorem 3.3.1, Theorem 3.3.4, Theorem 3.3.2), so transcendental numbers exist. Sizes are compared by injections, and injections both ways give a bijection, without choice (Theorem 3.4.3). Every infinite set contains a copy of $\mathbb{N}$ , by choice (Theorem 3.5.1), and has a proper subset of its own size (Theorem 3.5.2).

Sizes add, multiply and exponentiate by disjoint unions, products and sets of functions, with the laws of exponents proved by bijections (Theorem 3.6.3); so $\left| \mathbb{R} \right| = \left| \mathcal{P}\left( \mathbb{N} \right) \right|$ and the plane, $\mathbb{N}^{\mathbb{N}}$ and $\mathbb{R}^{\mathbb{N}}$ are the size of the line (Theorem 3.6.6, Theorem 3.6.7, Theorem 3.6.8, Corollary 3.6.9).

What is open: are any two sets comparable? Chapter 6 answers it. Next, Chapter 4 studies relations, and “same size” returns there as an example.

Terms

algebraic number: a real root of a non-zero polynomial with integer coefficients (Section 3.2, before Theorem 3.2.4).
at most as big as, strictly smaller: $\left| A \right| \le \left| B \right|$ if there is an injection $A \to B$ ; $\left| A \right| < \left| B \right|$ if moreover there is no bijection (Definition 3.4.1).
choice function: a function $c$ on the index set of a family with $c(i) \in A_i$ for every $i$ (Axiom 3.2.1).
countable: empty, or the image of a surjection $\mathbb{N} \to A$ (Definition 3.1.1).
countably infinite: equinumerous with $\mathbb{N}$ (Definition 3.1.2).
decimal expansion of $x \in [0, 1]$ : a digit sequence with $t_n \le x \le t_n + 10^{-n}$ for every $n \ge 1$ , where $t_n$ is the finite sum of the first $n$ digits (Definition 3.3.1).
digit sequence: a function from $\mathbb{Z}_{>0}$ to $\{0, 1, \dots, 9\}$ (Definition 3.3.1).
disjoint union $A \sqcup B$ : the set $(A \times \{0\}) \cup (B \times \{1\})$ (Definition 3.6.1).
transcendental number: a real number that is not algebraic (Section 3.3, before Corollary 3.3.5).
uncountable: not countable (Definition 3.1.1).