3.3 Countable Unions and the Axiom of Choice

Section 3.2 listed $\mathbb{N} \times \mathbb{N}$ , $\mathbb{Z}$ and $\mathbb{Q}$ , and showed that a union of two countable sets is countable (Proposition 3.2.5). The next question is a union of countably many countable sets. The natural proof is short, and it contains one step that none of the rules met so far can justify. This section isolates that step, adds the principle that licenses it, the axiom of choice, and then shows how to tell a proof that needs the axiom from one that only seems to.

3.3.1. A union of countably many lists

Let $A_0, A_1, A_2, \dots$ be countable sets, a family $(A_n)_{n \in \mathbb{N}}$ in the sense of Definition 1.2.3. We want to prove that $\bigcup_{n \in \mathbb{N}} A_n$ is countable.

Here is the proof most people write first. List each set: $A_n = \{ a_{n,0}, a_{n,1}, a_{n,2}, \dots \}$ . Put $a_{n,m}$ in row $n$ and column $m$ of an infinite grid. Every element of the union stands somewhere in the grid, and the grid is indexed by $\mathbb{N} \times \mathbb{N}$ , which is countable (Theorem 3.2.6). So the union is the image of a countable set, and it is countable.

Every step but the first, “list each set”, is a result of Section 3.2. Where do the lists come from?

3.3.2. The obstacle, rule by rule

For a non-empty $A_n$ , “ $A_n$ is countable” says that there exists a surjection $\mathbb{N} \to A_n$ (Definition 3.2.1). To use it we apply $\mathrm{\exists E}$ (Logic and Proof, Definition 5.6.1): we name the object and argue inside the box of that name. One $\mathrm{\exists E}$ names one surjection, for one $n$ .

Finitely many sets. The proof of Proposition 3.2.5 used two $\mathrm{\exists E}$ ’s; for $A_0, \dots, A_9$ we could nest ten boxes.
All $n \in \mathbb{N}$ at once. The grid needs a list of $A_n$ for every $n$ , assembled into one object: a function that sends each $n$ to a surjection $\mathbb{N} \to A_n$ . A proof is a finite object. It cannot contain one $\mathrm{\exists E}$ for each of infinitely many indices, and no rule of Logic and Proof, Chapter 5 makes infinitely many choices in one step.

Two escape routes fail. Recursion (Theorem 2.3.1) defines a function on all of $\mathbb{N}$ at once, but from a rule $g$ given in advance, each value determined by the previous one. The list of $A_{n+1}$ is not determined by the list of $A_n$ , and a rule producing a list of every $A_{n+1}$ would already be the missing object. Induction on $k$ , with Proposition 3.2.5 at each step, proves “for every $k$ , $A_0 \cup \dots \cup A_k$ is countable” (Exercise C3 writes it out), but that is a statement about each $k$ separately; nothing makes the lists for different $k$ fit together.

Section 1.5 met the same wall: a right inverse of a surjection must pick a preimage of every point at once, and the rules could do that only for finitely many points, or when a rule names the preimage.

3.3.3. The axiom of choice

None of the working rules (W1)–(W6) of Section 1.1 forms a set out of infinitely many arbitrary picks. The principle we add is the simplest statement that does.

From any family of non-empty sets, one may pick one element from each set, all at once.

Axiom 3.3.1 (Axiom of Choice)

Let $I$ be a set, and let $(A_i)_{i \in I}$ be a family of sets such that $A_i$ is non-empty for every $i \in I$ . Then there exists a function $c \colon I \to \bigcup_{i \in I} A_i \quad \text{with} \quad c(i) \in A_i \ \text{ for every } i \in I .$ Such a function $c$ is called a choice function for the family.

In symbols, with $Y^X$ the set of functions of Section 1.4 and $U \mathrel{:=} \bigcup_{i \in I} A_i$ : $\forall i \in I \ (A_i \ne \emptyset) \ \to \ \exists c \in U^{I} \ \ \forall i \in I \ \ c(i) \in A_i .$

In words: the hypothesis says that each set of the family has an element; the conclusion says that one function picks an element of every $A_i$ at the same time. The codomain, a set by (W3), only gives $c$ somewhere to take its values. The axiom asserts that $c$ exists and gives no recipe for it.

Its status. For finitely many indices the axiom adds nothing (proved below); for infinitely many it is a genuinely new principle. It is independent of the other axioms of set theory: Gödel (1938) showed that adding it creates no contradiction that was not there already, and Cohen (1963) that it cannot be proved from them. A later chapter states its best-known equivalent, Zorn’s lemma; the companion volume on set theory proves it equivalent to the axiom, together with the other equivalents such as the well-ordering theorem, and surveys the independence results. This book uses the axiom openly on the main line, among other places: here, for countable unions and right inverses; in Section 3.6, for infinite subsets that can be listed; in Analysis on the Real Line, Chapter 1, for sup approximations (the remark below); in Measure and Integration, Chapter 1, for the Vitali set; in Functional Analysis, Chapter 4, through Zorn’s lemma, for the Hahn–Banach theorem; and in Functional Analysis, Chapter 6, for Tychonoff’s theorem. Each use is flagged at its line.

Remark. A corollary in Analysis on the Real Line, Chapter 1 gives, for each $n \ge 1$ separately, some $a_n \in A$ with $a_n > \sup A - \frac1n$ : one $\mathrm{\exists E}$ per $n$ , and no axiom. Forming the sequence $(a_n)_{n \ge 1}$ from these is a choice function for the family $\bigl( \{ a \in A : a > \sup A - \tfrac1n \} \bigr)_{n \in \mathbb{Z}_{>0}}$ , an instance of Axiom 3.3.1 with the countable index set $I = \mathbb{Z}_{>0}$ . Analysis on the Real Line, Chapter 1 flags exactly this step.

Examples.

The empty family. If $I = \emptyset$ , the empty function $\emptyset \to \bigcup_{i \in \emptyset} A_i = \emptyset$ (Proposition 1.4.2 (a)) is a choice function: the condition “for every $i \in \emptyset$ ” holds vacuously. No axiom is needed.
A family with a rule. Let $I = \mathbb{Z}_{>0}$ and $A_n \mathrel{:=} \{ k \in \mathbb{N} : n \mid k, \ k \ne 0 \}$ , the positive multiples of $n$ . Each $A_n$ contains $n$ . The rule $c(n) \mathrel{:=} n$ is a choice function, defined by specification (Definition 1.1.3); no axiom is needed.
A family with no rule in sight. Let $I$ be the set of non-empty subsets of $\mathbb{R}$ , and $A_S \mathrel{:=} S$ for $S \in I$ . A choice function picks an element of every non-empty set of reals. “The least element” fails, since $(0, 1)$ has none, and no rule that works for every $S$ is known. Here the axiom supplies what the other rules do not.

A non-example by minimal change. In Example 2, add the index $n = 0$ . The positive multiples of $0$ form the empty set ( $0 \mid k$ means $k = 0$ ), so $A_0 = \emptyset$ , and no function can have $c(0) \in A_0$ . Only the clause “ $A_i$ is non-empty for every $i$ ” fails, and without it the conclusion is false. That is why the proofs below remove the empty sets from a family before they choose. (Dropping “all at once” instead would leave nothing beyond the hypothesis.)

3.3.4. When choice is not needed

Two kinds of construction look like choice and are not; telling them apart from a real use is the skill this section is for.

Finitely many sets. For every finite set $I$ and every family $(A_i)_{i \in I}$ of non-empty sets, a choice function exists, with no appeal to the axiom. For $I = \{1, 2, 3\}$ , three applications of $\mathrm{\exists E}$ name $a_i \in A_i$ , and $\{ (1, a_1), (2, a_2), (3, a_3) \}$ is the graph of a choice function. For a finite set of arbitrary size we induct on its number of elements (Definition 3.1.2). Let $P(n)$ be: “for every set $I$ with $n$ elements and every family $(A_i)_{i \in I}$ of non-empty sets, there is a choice function”. Base case $P(0)$ : a set with $0$ elements is the image of a bijection from $\{1, \dots, 0\} = \emptyset$ , so it is empty, and the empty function is a choice function (Example 1). Inductive step: assume $P(n)$ , and let $I$ have $n + 1$ elements. Then $I \ne \emptyset$ , since a bijection $\{1, \dots, n + 1\} \to I$ has a value at $1$ ; pick $i_0 \in I$ by $\mathrm{\exists E}$ . The set $I' \mathrel{:=} I \setminus \{i_0\}$ has $n$ elements (Corollary 3.1.7), so $P(n)$ gives a choice function $c'$ for $(A_i)_{i \in I'}$ . Since $A_{i_0} \ne \emptyset$ , one more $\mathrm{\exists E}$ names $a_0 \in A_{i_0}$ . The graph of $c'$ together with the pair $(i_0, a_0)$ , with codomain $\bigcup_{i \in I} A_i$ , is a function on $I' \cup \{i_0\} = I$ , because $i_0 \notin I'$ ; and it is a choice function. So $P(n + 1)$ holds, and Logic and Proof, Axiom 4.2.1 gives $P(n)$ for every $n \in \mathbb{N}$ . Each step uses two $\mathrm{\exists E}$ ’s and no new principle; the induction says nothing about an infinite $I$ , which has no number of elements.

A rule that picks. If one description names an element of each $A_i$ , the choice function is defined by specification (W1), as the set of pairs $(i, a)$ with $a$ the element named for $i$ . Typical rules: the least element of a non-empty set of natural numbers (Theorem 2.1.3); the non-negative square root of a positive real; in a bisection, the left half if it has the property in question, and otherwise the right half. The first rule is how Theorem 3.2.2 passed from a surjection $\mathbb{N} \to A$ to an injection $A \to \mathbb{N}$ with no axiom: the least preimage is named, not chosen.

Warning. Choice is not “picking an element”. “Let $a \in A$ ” is a single $\mathrm{\exists E}$ and needs no axiom; neither does picking from ten sets. The axiom is needed only for picking one element from each of infinitely many sets, with no rule. A proof that says “choose” need not use it, and one that never says “choose” may: “for each $n$ , let $g_n$ be a list of $A_n$ ” is a use, however it is worded.

3.3.5. Right inverses

The first consequence settles the question Section 1.5 left open. By Proposition 1.5.2, a function with a right inverse is surjective; the converse is where choice enters.

Theorem 3.3.2 (Surjections Have Right Inverses)

Let $f \colon X \to Y$ be a surjective function. Then $f$ has a right inverse: there is a function $g \colon Y \to X$ with $f(g(y)) = y$ for every $y \in Y$ .

Idea. A right inverse must name a preimage of every $y$ . The preimages of the points of $Y$ form a family of sets indexed by $Y$ , each non-empty because $f$ is onto. A choice function for that family is exactly a right inverse.

Proof. For $y \in Y$ , let $P_y \mathrel{:=} f^{-1}(\{y\}) = \{ x \in X : f(x) = y \}$ (Definition 1.6.2). This defines a family $(P_y)_{y \in Y}$ of subsets of $X$ , indexed by $Y$ . Each $P_y$ is non-empty, since $f$ is surjective (Definition 1.4.4). By Axiom 3.3.1 there is a function $c \colon Y \to \bigcup_{y \in Y} P_y$ with $c(y) \in P_y$ for every $y \in Y$ . The union is a subset of $X$ , so the graph of $c$ is a subset of $Y \times X$ , and with codomain $X$ it is a function $g \colon Y \to X$ with $g(y) = c(y)$ (Definition 1.4.1). For every $y \in Y$ , $g(y) \in P_y$ , that is, $f(g(y)) = y$ . So $f \circ g = \operatorname{id}_Y$ , and $g$ is a right inverse of $f$ (Definition 1.5.1 (b)).

Together with Proposition 1.5.2: a function is surjective if and only if it has a right inverse. The theorem is in fact equivalent to the axiom: a right inverse of the projection $(i, a) \mapsto i$ , from the set of pairs with $a \in A_i$ onto $I$ , is a choice function in disguise.

Quick check. Let $f \colon \mathbb{Z} \to \mathbb{N}$ , $f(k) \mathrel{:=} \left| k \right|$ . It is surjective. Does the existence of a right inverse of $f$ need Axiom 3.3.1?

Solution. No. Each $n \in \mathbb{N}$ has the preimages $n$ and $-n$ , and the rule “take the non-negative one” names one of them: $g(n) \mathrel{:=} n$ . Then $f(g(n)) = \left| n \right| = n$ , so $g \colon \mathbb{N} \to \mathbb{Z}$ is a right inverse, defined by a formula. The axiom is needed only when no such rule is available.

3.3.6. Countable unions

Now the theorem the section opened with. The second form, with any countable index set, is the one used in practice.

Theorem 3.3.3 (Countable Unions of Countable Sets)

(a) Let $(A_n)_{n \in \mathbb{N}}$ be a family of sets such that $A_n$ is countable for every $n \in \mathbb{N}$ . Then $\bigcup_{n \in \mathbb{N}} A_n$ is countable.
(b) Let $I$ be a countable set and $(A_i)_{i \in I}$ a family of sets such that $A_i$ is countable for every $i \in I$ . Then $\bigcup_{i \in I} A_i$ is countable.

Idea. This is the grid of the opening, with the lists supplied by the axiom. ① Throw away the empty sets: the axiom needs non-empty ones, and they add nothing to the union. ② For each remaining $n$ , the surjections $\mathbb{N} \to A_n$ form a non-empty set; choose one from each, all at once. ③ The chosen lists turn the grid $J \times \mathbb{N}$ into a surjection onto the union, and the grid is countable by Section 3.2. Part (b) is part (a) after renumbering the index set by a list.

Before reading on: which line uses choice, and why can $\mathrm{\exists E}$ not replace it?

Proof.

(a) Let $U \mathrel{:=} \bigcup_{n \in \mathbb{N}} A_n$ and $J \mathrel{:=} \{ n \in \mathbb{N} : A_n \ne \emptyset \}$ .
If $J = \emptyset$ , every $A_n$ is empty, so $U = \emptyset$ , which is countable by Definition 3.2.1.

Suppose $J \ne \emptyset$ . For $n \in J$ , let $S_n \mathrel{:=} \{ h \in A_n^{\mathbb{N}} : h \text{ is surjective} \} ,$ the set of surjections $\mathbb{N} \to A_n$ (Definition 1.1.3, with $A_n^{\mathbb{N}}$ the set of functions of Section 1.4). Since $A_n$ is countable and non-empty, $S_n \ne \emptyset$ (Definition 3.2.1). By Axiom 3.3.1, applied to the family $(S_n)_{n \in J}$ , there is a function $c \colon J \to \bigcup_{n \in J} S_n$ with $c(n) \in S_n$ for every $n \in J$ . This is the only line of the proof that uses the axiom.

Define $F \colon J \times \mathbb{N} \to U$ by $F(n, m) \mathrel{:=} c(n)(m)$ . It takes values in $U$ : $c(n)$ maps into $A_n \subseteq U$ . It is surjective: let $x \in U$ ; then $x \in A_n$ for some $n \in \mathbb{N}$ (Definition 1.2.4), so $A_n \ne \emptyset$ and $n \in J$ ; since $c(n)$ is a surjection onto $A_n$ , there is $m \in \mathbb{N}$ with $c(n)(m) = x$ , that is, $F(n, m) = x$ .

The set $J$ is countable by Proposition 3.2.3, as a subset of $\mathbb{N}$ , which is countable (the identity is a surjection). So $J \times \mathbb{N}$ is countable by Corollary 3.2.7 (a), and it is non-empty, since it contains $(n_0, 0)$ for any $n_0 \in J$ . By Definition 3.2.1 there is a surjection $s \colon \mathbb{N} \to J \times \mathbb{N}$ . Then $F \circ s \colon \mathbb{N} \to U$ is surjective (Theorem 1.4.4 (b)), and $U$ is countable.
(b) Let $U \mathrel{:=} \bigcup_{i \in I} A_i$ . If $I = \emptyset$ , then $U = \emptyset$ , which is countable. Otherwise Definition 3.2.1 gives a surjection $s \colon \mathbb{N} \to I$ ; fix one. For $n \in \mathbb{N}$ put $B_n \mathrel{:=} A_{s(n)}$ , a countable set. Then $\bigcup_{n \in \mathbb{N}} B_n = U$ . $(\subseteq)$ An element of $B_n$ lies in $A_{s(n)}$ with $s(n) \in I$ . $(\supseteq)$ If $x \in A_i$ with $i \in I$ , then $i = s(n)$ for some $n \in \mathbb{N}$ , because $s$ is onto, and $x \in B_n$ . By (a), $U$ is countable.

The line in bold is the only use of the axiom. The surjections $s$ of parts (a) and (b) are single objects, each named by one $\mathrm{\exists E}$ . What needed the axiom was a surjection for every $n \in J$ at once: $\mathrm{\exists E}$ supplies $c(n)$ only inside the box of a fixed $n$ , and $F$ needs all of them outside every such box. The set $J$ is there because for $A_n = \emptyset$ there is no function $\mathbb{N} \to A_n$ at all (Proposition 1.4.2 (b)), so $S_n = \emptyset$ . The theorem completes the closure properties of countable sets: subsets, images, finite products, countable unions.

Neither hypothesis can be dropped: Section 3.4 shows that $\mathbb{R}$ is not countable, and $\mathbb{R}$ is the union of the single set $\mathbb{R}$ , and also of the countable sets $\{x\}$ , $x \in \mathbb{R}$ .

Warning. The choice is of the lists, not of preimages. A surjection $\mathbb{N} \to A$ gives least preimages by a rule (Theorem 3.2.2), but only once the surjection is in hand. In Theorem 3.3.3, what is missing is the surjection itself, one for each $A_n$ , and the sets $A_n$ need not be sets of natural numbers, so no “least” is available to name one.

3.3.7. Unions without choice

Many countable unions met in practice come with their lists, and then no axiom is used.

Example (Unions that come with their lists)

(a) Show that $\mathbb{Q} = \bigcup_{n \in \mathbb{Z}_{>0}} Q_n$ , where $Q_n \mathrel{:=} \{ m/n : m \in \mathbb{Z} \}$ , and list the union without using Axiom 3.3.1.
(b) Does the proof in Theorem 3.2.8 that $\mathbb{Q}$ is countable use Axiom 3.3.1?

Solution.

(a) By the definition $\mathbb{Q} \mathrel{:=} \{ m/n : m \in \mathbb{Z}, \ n \in \mathbb{Z}_{>0} \}$ , a number is rational exactly when it lies in $Q_n$ for some $n \in \mathbb{Z}_{>0}$ , so the two sets are equal. Fix the bijection $z \colon \mathbb{N} \to \mathbb{Z}$ of Theorem 3.2.8 ( $z(2k) = k$ , $z(2k + 1) = -(k + 1)$ ). Then $k \mapsto z(k)/n$ lists $Q_n$ , and the whole family of lists is the single function $L \colon \mathbb{Z}_{>0} \times \mathbb{N} \to \mathbb{Q} , \qquad L(n, k) \mathrel{:=} z(k)/n ,$ defined by specification. It is onto $\mathbb{Q}$ : for $m/n$ with $m \in \mathbb{Z}$ , $n \in \mathbb{Z}_{>0}$ , take $k$ with $z(k) = m$ . Since $\mathbb{Z}_{>0} \times \mathbb{N}$ is countable and non-empty (Proposition 3.2.3, Corollary 3.2.7), composing $L$ with a surjection $\mathbb{N} \to \mathbb{Z}_{>0} \times \mathbb{N}$ lists $\mathbb{Q}$ . The grid is the same as in Theorem 3.3.3; the difference is that the rows were written down, not chosen.
(b) No, and its place before Axiom 3.3.1 does not settle this, since by the warning in “When choice is not needed” a proof can use the axiom without naming it; we check the lines. The maps $z$ and $(m, n) \mapsto m/n$ are formulas. The results cited name finitely many objects by $\mathrm{\exists E}$ : one injection in Proposition 3.2.3, two in Corollary 3.2.7 (a), one surjection in Proposition 3.2.4. The passage from a surjection to an injection in Theorem 3.2.2 takes the least preimage, a rule; the return from an injection to a list goes through Lemma 3.2.1, whose list is defined by recursion from least elements (Theorem 2.1.3), again a rule. No line picks from infinitely many sets without a rule.

The pattern is general: if one formula in $n$ lists every $A_n$ , the family of lists is a single function, and no axiom is used. Choice enters only when each $A_n$ is known to be countable as a bare existence statement.

3.3.8. Algebraic numbers

The theorem pays off at once. A real number is called algebraic if it is a root of a non-zero polynomial with integer coefficients. To keep this inside what the book has defined, we speak of coefficient tuples. For $d \ge 1$ and $c = (c_0, c_1, \dots, c_d) \in \mathbb{Z}^{d+1}$ (a $(d + 1)$ -tuple, entries numbered from $0$ ), let $p_c(x) \mathrel{:=} \sum_{k=0}^{d} c_k x^k \qquad (x \in \mathbb{R})$ (Definition 2.3.1, Definition 2.3.2), and call $c$ non-zero if $c_k \ne 0$ for some $k$ . Then $x \in \mathbb{R}$ is algebraic if $p_c(x) = 0$ for some $d \ge 1$ and some non-zero $c \in \mathbb{Z}^{d+1}$ . Constant polynomials are left out without loss, since a non-zero constant has no roots.

For example, $\sqrt 2$ is algebraic, a root of $x^2 - 2$ ( $c = (-2, 0, 1)$ ). Every rational $m/n$ is algebraic, a root of $nx - m$ ( $c = (-m, n)$ ). So is $\sqrt 2 + \sqrt 3$ , a root of $x^4 - 10x^2 + 1$ .

We use one fact from school algebra, not proved here: if $c \in \mathbb{Z}^{d+1}$ is non-zero, then $p_c$ has at most $d$ real roots. (It follows from the factor theorem.) In particular the set $R(c) \mathrel{:=} \{ x \in \mathbb{R} : p_c(x) = 0 \}$ is finite.

Theorem 3.3.4 (The Algebraic Numbers Are Countable)

The set of algebraic real numbers is countable.

Idea. Sort the polynomials by degree. For each $d$ , the coefficient tuples form a countable set, and each polynomial contributes finitely many roots: a countable union of finite sets. Then take the union over $d$ . Both unions are instances of Theorem 3.3.3 (b).

Proof. Let $\mathrm{Alg}$ be the set of algebraic real numbers, and for $d \ge 1$ let $Z_d$ be the set of non-zero tuples in $\mathbb{Z}^{d+1}$ .

Step 1. Let $d \ge 1$ . The set $\mathbb{Z}$ is countable (Theorem 3.2.8), and $\mathbb{Z}^{d+1}$ is the product of $d + 1 \ge 2$ factors all equal to $\mathbb{Z}$ , so it is countable by Corollary 3.2.7 (b). Hence $Z_d \subseteq \mathbb{Z}^{d+1}$ is countable (Proposition 3.2.3).

Step 2. For $c \in Z_d$ , the root set $R(c)$ is finite by the school fact above, hence countable (Theorem 3.2.2, (iii) $\Rightarrow$ (i)). So $\mathrm{Alg}_d \mathrel{:=} \bigcup_{c \in Z_d} R(c)$ , the set of roots of the non-zero polynomials of degree at most $d$ , is countable by Theorem 3.3.3 (b), with the countable index set $Z_d$ .

Step 3. By definition, $\mathrm{Alg} = \bigcup_{d \in \mathbb{Z}_{>0}} \mathrm{Alg}_d$ . The index set $\mathbb{Z}_{>0} \subseteq \mathbb{N}$ is countable (Proposition 3.2.3). So $\mathrm{Alg}$ is countable by Theorem 3.3.3 (b).

The proof cites Theorem 3.3.3 twice, and so it uses Axiom 3.3.1. Here the axiom can be avoided (not proved in the text; nothing later uses it): list each finite root set in increasing order, which is a rule, and replace the two unions by one fixed enumeration of all integer coefficient tuples. Exercise C2 asks you to carry this out. The countability of $\mathrm{Alg}$ has a striking consequence once we know that $\mathbb{R}$ is not countable: Section 3.4 deduces that some real numbers are not algebraic.

3.3.9. Exercises

A. Check your understanding

Exercise (A1)

These parts are about the proof of Theorem 3.3.3.

(a) Which line of the proof of part (a) uses Axiom 3.3.1? What are the index set $I$ and the sets $A_i$ of the axiom at that line?
(b) Why does the proof introduce the set $J$ ?
(c) Run the proof on $A_n \mathrel{:=} \{ n, n + 1 \}$ for $n \in \mathbb{N}$ , with the lists $c(n)(m) \mathrel{:=} n$ for odd $m$ and $c(n)(m) \mathrel{:=} n + 1$ for even $m$ . What is $J$ , and what is $F(3, 2)$ ?
(d) State the idea of the proof in two sentences.
(e) Is Axiom 3.3.1 needed to show that $\bigcup_{n \in \mathbb{N}} A_n$ is countable when every $A_n$ is a subset of $\mathbb{N}$ ? Justify your answer.

Solution.

(a) The line “By Axiom 3.3.1, applied to the family $(S_n)_{n \in J}$ , there is a function $c$ on $J$ with $c(n) \in S_n$ ”. There $I = J$ , the set of indices with $A_n \ne \emptyset$ , and the sets of the axiom are the $S_n$ , the sets of surjections $\mathbb{N} \to A_n$ . The axiom chooses lists, not elements of the $A_n$ .
(b) The axiom applies only to families of non-empty sets. If $A_n = \emptyset$ , there is no function $\mathbb{N} \to A_n$ at all (Proposition 1.4.2 (b)), so $S_n = \emptyset$ , and the family $(S_n)_{n \in \mathbb{N}}$ would not qualify. Empty sets add nothing to the union, so restricting to $J$ loses nothing.
(c) Every $A_n$ is non-empty, so $J = \mathbb{N}$ . The pair $(3, 2)$ has $m = 2$ even, so $F(3, 2) = c(3)(2) = 3 + 1 = 4$ . (Each $c(n)$ is onto $\{n, n + 1\}$ : $c(n)(1) = n$ and $c(n)(0) = n + 1$ .)
(d) Choose, with the axiom, a list of each non-empty $A_n$ , all at once. The lists turn the countable grid $J \times \mathbb{N}$ into a surjection onto the union, so the union is countable.
(e) No. The union is a subset of $\mathbb{N}$ , so it is countable by Proposition 3.2.3. (Even the proof can run without the axiom: $h_A(m) \mathrel{:=} m$ for $m \in A$ and $h_A(m) \mathrel{:=} \min A$ otherwise (Theorem 2.1.3) is a rule that maps $\mathbb{N}$ onto any non-empty $A \subseteq \mathbb{N}$ .)

B. Practice

Exercise (B1: Which constructions need choice?)

Determine which of the following constructions need Axiom 3.3.1. Justify your answer.

(a) Choose a real number in each interval $(n, n + 1)$ , $n \in \mathbb{N}$ .
(b) Choose an element of each non-empty subset of $\mathbb{N}$ .
(c) Choose an element of each non-empty subset of $\mathbb{R}$ .
(d) Choose one of the two square roots of each positive real number.

Solution.

(a) No. The rule $n \mapsto n + \frac12$ names an element of each interval, since $n < n + \frac12 < n + 1$ .
(b) No. The rule “the least element” names one, by Theorem 2.1.3: $S \mapsto \min S$ is a choice function, defined by specification.
(c) Yes, as far as this book is concerned. The rule “the least element” fails, since $(0, 1)$ has no least element, and no rule is known that names an element of every non-empty set of reals. A proof that needs such a function uses the axiom, and says so.
(d) No. The rule “the positive one” names one root of each $y > 0$ : $y \mapsto \sqrt y$ .

Exercise (B2: Finite sequences)

Prove that the set of all finite sequences of natural numbers is countable, and say whether your proof uses Axiom 3.3.1. Here a finite sequence of length $k \in \mathbb{N}$ is a function $\{1, \dots, k\} \to \mathbb{N}$ , represented by its graph, a subset of $\mathbb{Z}_{>0} \times \mathbb{N}$ ; the sequence of length $0$ is $\emptyset$ .

Hint: Theorem 2.3.1, together with one fixed surjection $\mathbb{N} \to \mathbb{N} \times \mathbb{N}$ .

Solution. Let $\mathrm{Seq}$ be the set of $x \in \mathcal{P}\left( \mathbb{Z}_{>0} \times \mathbb{N} \right)$ such that $x$ is the graph of a function $\{1, \dots, k\} \to \mathbb{N}$ for some $k \in \mathbb{N}$ (Definition 1.1.3, Definition 1.2.2). This $k$ is determined by $x$ , since $\{1, \dots, k\}$ is the set of first coordinates of $x$ , and $k$ is its number of elements (Corollary 3.1.4); call it the length of $x$ , and let $\mathrm{Seq}_k$ be the set of elements of length $k$ . So $\mathrm{Seq} = \bigcup_{k \in \mathbb{N}} \mathrm{Seq}_k$ , and $\mathrm{Seq}_0 = \{\emptyset\}$ .

With choice. Each $\mathrm{Seq}_k$ is countable (for $k \ge 2$ it is in bijection with $\mathbb{N}^k$ , by $x \mapsto (x(1), \dots, x(k))$ ; $\mathrm{Seq}_1$ with $\mathbb{N}$ ; $\mathrm{Seq}_0$ has one element), so Theorem 3.3.3 (a) applies. This route uses Axiom 3.3.1, through the theorem.

Without choice. Fix one surjection $\sigma \colon \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ (Theorem 3.2.6, Definition 3.2.1; a single $\mathrm{\exists E}$ ), and write $\sigma(n) = (\sigma_1(n), \sigma_2(n))$ . For $x \in \mathrm{Seq}$ of length $k$ and $m \in \mathbb{N}$ , let $x \frown m \mathrel{:=} x \cup \{ (k + 1, m) \}$ , the sequence $x$ with $m$ appended; it has length $k + 1$ . Every $y \in \mathrm{Seq}_{k+1}$ is $x \frown m$ for $x$ the restriction of $y$ to $\{1, \dots, k\}$ and $m = y(k + 1)$ .

Let $X \mathrel{:=} \mathrm{Seq}^{\mathbb{N}}$ , the set of functions $\mathbb{N} \to \mathrm{Seq}$ , let $a \in X$ be the constant function with value $\emptyset$ , and define $g \colon \mathbb{N} \times X \to X$ by $g(k, s)(n) \mathrel{:=} s\bigl(\sigma_1(n)\bigr) \frown \sigma_2(n) .$ By Theorem 2.3.1 there is a function $k \mapsto s_k$ from $\mathbb{N}$ to $X$ with $s_0 = a$ and $s_{k+1}(n) = s_k(\sigma_1(n)) \frown \sigma_2(n)$ for all $k, n \in \mathbb{N}$ .

Claim: for every $k \in \mathbb{N}$ , $s_k$ maps $\mathbb{N}$ onto $\mathrm{Seq}_k$ . By Logic and Proof, Axiom 4.2.1 on $k$ . For $k = 0$ , every value of $s_0$ is $\emptyset$ , and $\mathrm{Seq}_0 = \{\emptyset\}$ . Assume the claim for $k$ . Each value $s_{k+1}(n) = s_k(\sigma_1(n)) \frown \sigma_2(n)$ has length $k + 1$ , because $s_k(\sigma_1(n))$ has length $k$ . Let $y \in \mathrm{Seq}_{k+1}$ , say $y = x \frown m$ with $x \in \mathrm{Seq}_k$ . By the hypothesis there is $j$ with $s_k(j) = x$ , and since $\sigma$ is onto there is $n$ with $\sigma(n) = (j, m)$ . Then $s_{k+1}(n) = s_k(j) \frown m = y$ . This proves the claim.

Now $n \mapsto s_{\sigma_1(n)}(\sigma_2(n))$ maps $\mathbb{N}$ onto $\mathrm{Seq}$ : for $y \in \mathrm{Seq}_k$ , the claim gives $j$ with $s_k(j) = y$ , and some $n$ has $\sigma(n) = (k, j)$ . So $\mathrm{Seq}$ is countable. One surjection was named, and the lists $s_k$ were defined from it by recursion: no choice is used. Either route earns full credit if the use of choice is reported correctly.

Exercise (B3)

A rational point of the plane is a point of $\mathbb{Q} \times \mathbb{Q}$ . Prove that the set of lines in the plane that pass through two different rational points is countable. Does your proof use Axiom 3.3.1?

Solution. Let $D \mathrel{:=} \{ (p, q) \in (\mathbb{Q} \times \mathbb{Q}) \times (\mathbb{Q} \times \mathbb{Q}) : p \ne q \}$ . The set $\mathbb{Q} \times \mathbb{Q}$ is countable by Theorem 3.2.8 and Corollary 3.2.7; so is its product with itself, again by Corollary 3.2.7, and so is the subset $D$ (Proposition 3.2.3). For $(p, q) \in D$ , let $\mathrm{line}(p, q)$ be the line through $p$ and $q$ , as a subset of $\mathbb{R}^2$ : $\mathrm{line}(p, q) \mathrel{:=} \{ p + t(q - p) : t \in \mathbb{R} \}$ . Two different points lie on exactly one line (school geometry), so the lines in question form the image $\mathrm{line}(D)$ , countable by Proposition 3.2.4. The map $\mathrm{line}$ is a formula, so no choice is used.

C. Going deeper

Exercise (C1: Exit check: countable unions)

Prove that if $A_n$ is countable for every $n \in \mathbb{N}$ , then so is $\bigcup_{n \in \mathbb{N}} A_n$ . Point to the step of your proof that uses Axiom 3.3.1.

Solution. Let $U \mathrel{:=} \bigcup_{n \in \mathbb{N}} A_n$ and $J \mathrel{:=} \{ n \in \mathbb{N} : A_n \ne \emptyset \}$ . If $J = \emptyset$ , then $U = \emptyset$ , which is countable. Let $J \ne \emptyset$ . For $n \in J$ , the set $S_n$ of surjections $\mathbb{N} \to A_n$ is non-empty (Definition 3.2.1). By Axiom 3.3.1, applied to $(S_n)_{n \in J}$ , there is a function $c$ on $J$ with $c(n) \in S_n$ for every $n \in J$ : a list of every $A_n$ at once, which no finite number of $\mathrm{\exists E}$ ’s gives. This is the step that uses the axiom.

Put $F(n, m) \mathrel{:=} c(n)(m) \in A_n \subseteq U$ for $(n, m) \in J \times \mathbb{N}$ . It is onto $U$ : if $x \in U$ , then $x \in A_n$ for some $n \in \mathbb{N}$ (Definition 1.2.4), so $n \in J$ , and $c(n)(m) = x$ for some $m$ , as $c(n)$ is onto $A_n$ . Since $J \subseteq \mathbb{N}$ is countable (Proposition 3.2.3), $J \times \mathbb{N}$ is countable (Corollary 3.2.7 (a)) and non-empty, so some $s \colon \mathbb{N} \to J \times \mathbb{N}$ is onto (Definition 3.2.1), and so is $F \circ s \colon \mathbb{N} \to U$ (Theorem 1.4.4 (b)). This is the proof of Theorem 3.3.3 (a).

Marking scheme. (10 points) - 1: handles the empty sets: the case where every $A_n$ is empty, and the restriction to the non-empty ones before choosing. - 3: obtains, by Axiom 3.3.1, a surjection onto $A_n$ for every $n$ simultaneously, and says at that line that the axiom is used. - 2: defines a map from a set of pairs (or another index set) to the union. - 2: shows that this map is onto the union. - 2: shows that the index set is countable and non-empty, citing the product result, and concludes. Through injections $\iota_n \colon A_n \to \mathbb{N}$ : 1 for noting that they exist for every $n$ , empty $A_n$ included (the empty function), so nothing is discarded; 3 for choosing all $\iota_n$ by Axiom 3.3.1, flagged; 2 for $x \mapsto (n_x, \iota_{n_x}(x))$ into $\mathbb{N} \times \mathbb{N}$ , with $n_x$ the least $n$ with $x \in A_n$ (Theorem 2.1.3); 2 for its injectivity; 2 for concluding with Theorem 3.2.6 and Theorem 3.2.2, (ii) $\Rightarrow$ (i). Fatal errors (0 for the step): “for each $n$ let $f_n$ be a list of $A_n$ ” with no mention of choice, an unflagged infinite $\mathrm{\exists E}$ that no rule licenses (0 for the choice step); listing $\mathbb{N} \times \mathbb{N}$ row by row, as in Example (Listing the rows one after another) (0 for the countability step).

Exercise (C2: Algebraic numbers without choice)

Prove Theorem 3.3.4 without using Axiom 3.3.1.

Solution (Hint 1). Use Exercise (B2: Finite sequences) to obtain, without choice, one surjection from $\mathbb{N}$ onto all coefficient tuples of all lengths together.

Solution (Hint 2). For an algebraic $r$ , let $n(r)$ be the least index whose tuple has $r$ as a root; it exists by Theorem 2.1.3.

Solution. Use the notation of Theorem 3.3.4, and let $\mathrm{Alg}$ be the set of algebraic numbers.

One list of all coefficient tuples. Let $\mathrm{ZSeq}$ be defined as $\mathrm{Seq}$ in Exercise (B2: Finite sequences), with $\mathbb{Z}$ in place of $\mathbb{N}$ , and let $z \colon \mathbb{N} \to \mathbb{Z}$ be the bijection of Theorem 3.2.8. Sending $x \in \mathrm{Seq}$ to the sequence $i \mapsto z(x(i))$ maps $\mathrm{Seq}$ onto $\mathrm{ZSeq}$ (use $z^{-1}$ entrywise to find a preimage), so $\mathrm{ZSeq}$ is countable without choice, by that exercise and Proposition 3.2.4. Since $\mathrm{ZSeq}$ is non-empty (it contains $\emptyset$ , the sequence of length $0$ ), fix one surjection $\mu \colon \mathbb{N} \to \mathrm{ZSeq}$ (Definition 3.2.1), a single $\mathrm{\exists E}$ . A sequence $y$ of length $d + 1 \ge 2$ is read as the tuple $c = (y(1), \dots, y(d + 1)) \in \mathbb{Z}^{d+1}$ , and every such tuple arises; write $p_y \mathrel{:=} p_c$ and $R(y) \mathrel{:=} R(c)$ . Call $n \in \mathbb{N}$ good for $r \in \mathbb{R}$ if $\mu(n)$ has length at least $2$ , is non-zero, and $p_{\mu(n)}(r) = 0$ . Then $r$ is algebraic if and only if some $n$ is good for $r$ , since $\mu$ is onto.

An injection, by rules. For $r \in \mathrm{Alg}$ , let $n(r)$ be the least $n \in \mathbb{N}$ that is good for $r$ (Theorem 2.1.3), and let $\rho(r) \mathrel{:=} \text{the number of elements of } \{ s \in R(\mu(n(r))) : s < r \} ,$ well defined because this set is a subset of the finite set $R(\mu(n(r)))$ (Proposition 3.1.6, Corollary 3.1.4). Both are named by rules, so $r \mapsto (n(r), \rho(r))$ is a function $\mathrm{Alg} \to \mathbb{N} \times \mathbb{N}$ , defined by specification.

It is injective. Let $r, r' \in \mathrm{Alg}$ with $n(r) = n(r')$ and $\rho(r) = \rho(r')$ ; call this common index $n$ , and suppose $r \ne r'$ , say $r < r'$ . Both are roots of $p_{\mu(n)}$ . The set $\{ s \in R(\mu(n)) : s < r \}$ is a subset of $\{ s \in R(\mu(n)) : s < r' \}$ , and a proper one, since $r$ lies in the second and not in the first. By Proposition 3.1.6, the first has fewer elements: $\rho(r) < \rho(r')$ , a contradiction. So $r = r'$ .

Following it with the injection $(m, k) \mapsto 2^m 3^k$ of Theorem 3.2.6 gives an injection $\mathrm{Alg} \to \mathbb{N}$ (Theorem 1.4.4 (a)), so $\mathrm{Alg}$ is countable by Theorem 3.2.2, (ii) $\Rightarrow$ (i). Apart from the single surjection $\mu$ , every object was named by a rule, so Axiom 3.3.1 is not used.

Marking scheme. (10 points) - 3: produces, without choice, one surjection (or injection) relating $\mathbb{N}$ to the coefficient tuples of all degrees at once, citing Exercise (B2: Finite sequences) or an explicit coding. - 3: assigns to each algebraic number its data (an index of a polynomial and a position among its roots) by rules, such as a least index and a count or the increasing order of the finite root set. - 4: proves that the resulting map is injective (or a map onto $\mathrm{Alg}$ surjective), concludes, and says why no step uses choice. Fatal errors (0 for the step): citing Theorem 3.3.3, which uses the axiom; “for each polynomial (or each $d$ ), take a list” with no rule given.

Exercise (C3: Finite unions)

(a) Prove, without Axiom 3.3.1, that for every finite set $I$ and every family $(A_i)_{i \in I}$ of countable sets, $\bigcup_{i \in I} A_i$ is countable.
(b) Explain in two sentences why your induction does not prove Theorem 3.3.3.

Solution.

(a) We use Logic and Proof, Axiom 4.2.1 on the number of elements of $I$ . Let $P(n)$ be: “for every set $I$ with $n$ elements and every family $(A_i)_{i \in I}$ of countable sets, $\bigcup_{i \in I} A_i$ is countable”.
Base case. A set $I$ with $0$ elements is empty, so $\bigcup_{i \in I} A_i = \emptyset$ , which is countable.

Inductive step. Assume $P(n)$ , and let $I$ have $n + 1$ elements and $(A_i)_{i \in I}$ be a family of countable sets. Since $n + 1 \ge 1$ , $I \ne \emptyset$ ; pick $i_0 \in I$ . Then $I' \mathrel{:=} I \setminus \{i_0\}$ has $n$ elements (Corollary 3.1.7), so $B \mathrel{:=} \bigcup_{i \in I'} A_i$ is countable by $P(n)$ , applied to the family $(A_i)_{i \in I'}$ . Since $I = I' \cup \{i_0\}$ , an element lies in some $A_i$ with $i \in I$ exactly when it lies in $B$ or in $A_{i_0}$ , so $\bigcup_{i \in I} A_i = B \cup A_{i_0} ,$ which is countable by Proposition 3.2.5. So $P(n + 1)$ holds, and Logic and Proof, Axiom 4.2.1 gives $P(n)$ for every $n$ . Each step makes finitely many $\mathrm{\exists E}$ ’s, so no choice is used.
(b) The induction proves the statement for each finite number $n$ of sets, and $\mathbb{N}$ is not finite (Example (Hilbert’s Hotel)), so no instance of $P(n)$ is about the family $(A_n)_{n \in \mathbb{N}}$ . Writing $\bigcup_{n \in \mathbb{N}} A_n$ as the union of the finite unions $A_0 \cup \dots \cup A_k$ does not help, since that needs a list of every finite union at once, which is a choice of infinitely many lists again.