6.1 The Axiom of Choice

Chapter 4 avoided picking one element from each of infinitely many sets: every function it built was given by a formula, a least element, or a list fixed in advance. This chapter adds the one principle that allows such picking, the axiom of choice, and gathers the theorems that need it. Section 4.2 listed $\mathbb{N} \times \mathbb{N}$ , $\mathbb{Z}$ and $\mathbb{Q}$ , and showed that a union of two countable sets is countable (Proposition 4.2.5). The next question is a union of countably many countable sets. The natural proof is short, and one of its steps cannot be justified by any rule met so far. This section isolates that step, adds the axiom that licenses it, shows how to tell a proof that needs the axiom from one that only seems to, and proves the four results this book draws from it: right inverses, comparing sizes by surjections, countable unions, and the place of $\mathbb{N}$ among the infinite sets.

6.1.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.3.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 4.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 4.2. Where do the lists come from?

6.1.2. The axiom of choice

None of the working rules (W1)–(W6) of Section 1.2 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 6.1.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 2.1 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 can be neither proved nor refuted from the other axioms of set theory (Gödel, Cohen). Section 6.2 states Zorn’s lemma, and Section 6.3 proves that Zorn’s lemma gives the axiom and the well-ordering theorem; Axiomatic Set Theory, Chapter 4 proves the converse, and Chapter 5 surveys the independence results. This book uses the axiom openly on the main line, among other places: in this section, for right inverses, countable unions and infinite sets; in Analysis on the Real Line, Chapter 1, for sup approximations (the remark below); in Measure, Integration, and Real Analysis, Chapter 2, for the Vitali set; in the same volume, Chapter 10, through Zorn’s lemma, for the Hahn–Banach theorem; and in Functional Analysis, Chapter 2, 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 6.1.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 2.1.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.2.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.)

6.1.3. 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 4.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 4.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 3.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 4.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.

The warning is the whole method; here it is as a checklist.

Example (Method: name the choice)

Template. At each line that produces an object for each of many indices at once, ask whether one rule names it for every index: a formula, “the least”, “the unique”, or one list fixed in advance. If so, define the function by specification; no choice is used. If not, form the family $(S_i)$ of non-empty sets of candidates and write “by Axiom 6.1.1 there is $c$ with $c(i) \in S_i$ ” at that line, in bold.

When to use it. A proof says “for each $n$ , let …”, builds a sequence or a family of lists, or inverts a surjection.

The usual failure. An unflagged “for each $n$ , choose”. Flagging a single $\mathrm{\exists E}$ , or a rule, as a use. An empty $S_i$ left in the family (the non-example above).

Quick check. A proof says: “For each $n \in \mathbb{N}$ the set $\{ k \in \mathbb{N} : k^2 > n \}$ is non-empty; choose $k_n$ in it.” Does this line need Axiom 6.1.1? Rewrite it so that it plainly does not.

Solution. No: it need not. The least element (Theorem 3.1.3) names $k_n$ , and so does the formula $k_n \mathrel{:=} n + 1$ , since $(n + 1)^2 = n^2 + 2n + 1 > n$ . Either rewrite defines $n \mapsto k_n$ by specification.

Example (Choice or a rule?)

Which of the following needs Axiom 6.1.1?

(a) A function sending each non-empty finite set of reals to one of its elements.
(b) A function sending each open interval $\{ x \in \mathbb{R} : a < x < b \}$ with $a < b$ to a rational number in it.
(c) A function sending each countably infinite subset $A \subseteq \mathbb{R}$ to a bijection $\mathbb{N} \to A$ .
(d) For a given family $(A_n)_{n \in \mathbb{N}}$ of non-empty subsets of $\mathbb{Q}$ , a sequence with $a_n \in A_n$ for every $n$ .

Solution.

(a) No: $S \mapsto \max S$ , which exists by Proposition 3.3.8.
(b) No, once one list of $\mathbb{Q}$ is fixed. Take a surjection $q \colon \mathbb{N} \to \mathbb{Q}$ (Theorem 4.2.8, one $\mathrm{\exists E}$ ). Between two reals lies a rational (a school fact; Analysis on the Real Line, Chapter 1 proves it), so $\{ n \in \mathbb{N} : a < q(n) < b \}$ is non-empty, and $q$ of its least element (Theorem 3.1.3) is named by a rule.
(c) Yes, as far as this book is concerned. Each $A$ has bijections $\mathbb{N} \to A$ (Definition 4.2.2), but no rule names one for an arbitrary $A$ . The family $(S_A)$ of sets of bijections, indexed by the countably infinite subsets of $\mathbb{R}$ (a set, by specification in $\mathcal{P}\left( \mathbb{R} \right)$ ), consists of non-empty sets, and Axiom 6.1.1 gives the function.
(d) No: with the same fixed $q$ , $a_n \mathrel{:=} q\bigl(\min \{ k \in \mathbb{N} : q(k) \in A_n \}\bigr)$ ; the set is non-empty because $A_n \ne \emptyset$ and $q$ is onto.

One fixed list turns “pick an element” into “take the first one on the list”, and that is a rule.

6.1.4. Right inverses

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

Theorem 6.1.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. This is the method of Example (Method: name the choice): for an arbitrary $f$ no rule names a preimage, so the line is flagged.

Proof. For $y \in Y$ , let $P_y \mathrel{:=} f^{-1}(\{y\}) = \{ x \in X : f(x) = y \}$ (Definition 2.5.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 2.2.2). By Axiom 6.1.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 2.1.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 2.4.1 (b)).

Together with Proposition 2.4.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 6.1.1?

Solution. No. Each $n \in \mathbb{N}$ has the preimage $n$ , and also $-n$ when $n > 0$ ; 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.

6.1.5. Comparing sizes by surjections

Right inverses give a second reading of $\le$ . Section 4.4 compared sizes by injections, and turned an injection $A \to B$ into a surjection $B \to A$ (Proposition 4.4.2). This section supplies the converse, at the price of the axiom: the direction from a surjection to an injection uses Theorem 6.1.2.

Proposition 6.1.3 (Injections and Surjections)

Let $A$ and $B$ be sets with $A \ne \emptyset$ . Then $\left| A \right| \le \left| B \right|$ if and only if there is a surjection $B \to A$ .

Proof. $(\Rightarrow)$ This half is Proposition 4.4.2 (Section 4.4); it uses no choice.

$(\Leftarrow)$ Let $g \colon B \to A$ be a surjection. By Theorem 6.1.2, $g$ has a right inverse $h \colon A \to B$ , so $g \circ h = \operatorname{id}_A$ ; this step uses Axiom 6.1.1, through Theorem 6.1.2. Then $g$ is a left inverse of $h$ , so $h$ is injective by Theorem 2.4.1 (a). Hence $\left| A \right| \le \left| B \right|$ . This proves the proposition.

The hypothesis $A \ne \emptyset$ is needed for $(\Rightarrow)$ only, as Section 4.4 showed with $A = \emptyset$ , $B = \{b\}$ . The choice in $(\Leftarrow)$ is genuine in general, but not for $B = \mathbb{N}$ : a surjection from $\mathbb{N}$ has least preimages, a rule, which is how Theorem 4.2.2 went from (i) to (ii) without the axiom.

Quick check. Is $\left| \{0, 1\}^{\mathbb{N}} \right| \le \left| \mathcal{P}\left( \mathbb{N} \right) \right|$ ? Give an injection, and say whether your answer needed Proposition 6.1.3.

Solution. Yes. Send a sequence $a \in \{0, 1\}^{\mathbb{N}}$ to the set $\{ n \in \mathbb{N} : a(n) = 1 \}$ . If two sequences give the same set, they take the value $1$ at the same places, and so the value $0$ at the same places too; hence they are equal (Proposition 2.1.1), and the map is injective. No appeal to Proposition 6.1.3 is needed: the definition asks for an injection, and we wrote one down. (The map is in fact a bijection, with inverse $S \mapsto \mathbf{1}_S$ , by Theorem 2.3.5 with $X = \mathbb{N}$ .)

6.1.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 6.1.4 (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 (Scratch work). 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 4.2.

Part (b) is part (a) after renumbering the index set by a list. As givens and goal, for (a):

Givens	Goal
$A_n$ countable for every $n$	$\bigcup_{n \in \mathbb{N}} A_n$ countable
$J \mathrel{:=} \{ n : A_n \ne \emptyset \}$ ; $J \times \mathbb{N}$ countable (Corollary 4.2.7)	a surjection $F \colon J \times \mathbb{N} \to \bigcup_{n \in \mathbb{N}} A_n$
for each single $n \in J$ : some surjection $\mathbb{N} \to A_n$ (one $\mathrm{\exists E}$ per $n$ )	$F(n, m) \mathrel{:=}$ (a list of $A_n$ ) $(m)$ , which needs every list at once, as one function $n \mapsto c(n)$
gap: from “for every $n$ there is a list” to “there is one function giving a list for every $n$ ”	closed by Axiom 6.1.1 on $(S_n)_{n \in J}$ , the only flagged line

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 4.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.2.3, with $A_n^{\mathbb{N}}$ the set of functions of Section 2.1). Since $A_n$ is countable and non-empty, $S_n \ne \emptyset$ (Definition 4.2.1). By Axiom 6.1.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.3.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 4.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 4.2.7 (a), and it is non-empty, since it contains $(n_0, 0)$ for any $n_0 \in J$ . By Definition 4.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 2.2.1 (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 4.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 2.1.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 4.3 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 4.2.2), but only once the surjection is in hand. In Theorem 6.1.4, 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.

6.1.7. Every infinite set contains a copy of the natural numbers

Every infinite set met so far contains a copy of $\mathbb{N}$ , and Section 4.5 showed what such a copy does (Proposition 4.5.1). Picking new elements one at a time looks like a proof that every infinite set has one; it is not one, since “one at a time” is a recursion whose step must pick a new element from every set $X \setminus F$ , $F$ finite, at once. So the proof chooses once, on all non-empty subsets of $X$ . With Axiom 6.1.1 it becomes a proof, and it gives two results: $\mathbb{N}$ is the smallest infinite size, and a set is infinite exactly when it is the same size as a proper part of itself.

The question has a goal theorem: we want to show that an infinite set $X$ has a countably infinite subset, that is, a subset equinumerous with $\mathbb{N}$ (Definition 4.2.2). Equivalently, we want an injection $\mathbb{N} \to X$ : its image is then such a subset.

Theorem 6.1.5 (Infinite Sets Contain a Countably Infinite Subset)

Every infinite set $X$ has a countably infinite subset. Equivalently, there is an injection $\mathbb{N} \to X$ .

Idea. The natural attempt picks $x_0 \in X$ , then $x_1 \in X \setminus \{x_0\}$ , then $x_2 \in X \setminus \{x_0, x_1\}$ , and so on. Each pick is possible, because a finite set cannot exhaust the infinite $X$ , and each single pick is one $\mathrm{\exists E}$ . But “and so on” is a definition by recursion, and Theorem 3.3.1 needs a function $g$ that says, once and for all, which new element to take after any finite stage. That function must pick an element from every non-empty set of the form $X \setminus F$ at once, with no rule for doing so when $X$ is arbitrary. So we let Axiom 6.1.1 supply a choice function $c$ on all non-empty subsets of $X$ first, and then the recursion is an ordinary one, with $c$ as its rule.

Proof. Let $X$ be infinite. The family $(S)_{S \in \mathcal{P}\left( X \right) \setminus \{\emptyset\}}$ , indexed by the non-empty subsets of $X$ with each index as its own member, consists of non-empty sets, and its union is $X$ : every index is a subset of $X$ , and each $x \in X$ lies in the index $\{x\}$ . By Axiom 6.1.1 there is a function $c \colon \mathcal{P}\left( X \right) \setminus \{\emptyset\} \to X$ with $c(S) \in S \quad \text{for every non-empty } S \subseteq X .$ This is the one line of the proof that uses the axiom.

Define $g \colon \mathbb{N} \times \mathcal{P}\left( X \right) \to \mathcal{P}\left( X \right)$ by $g(n, F) \mathrel{:=} F \cup \{ c(X \setminus F) \}$ if $F \ne X$ , and $g(n, F) \mathrel{:=} F$ if $F = X$ . In the first case $X \setminus F$ is non-empty, so $c(X \setminus F)$ is defined; so $g$ is a function. By Theorem 3.3.1, applied with the set $\mathcal{P}\left( X \right)$ , the starting value $\emptyset$ and this $g$ , there are sets $F_n \subseteq X$ , for $n \in \mathbb{N}$ , with $F_0 = \emptyset$ and $F_{n+1} = g(n, F_n)$ .

We show by induction (Logic and Proof, Axiom 4.2.1) that $F_n$ has exactly $n$ elements, for every $n \in \mathbb{N}$ . For $n = 0$ , $F_0 = \emptyset$ has $0$ elements (Definition 4.1.2). Suppose $F_n$ has $n$ elements. Then $F_n$ is finite and $X$ is not, so $F_n \ne X$ , and $F_{n+1} = F_n \cup \{ c(X \setminus F_n) \}$ with $c(X \setminus F_n) \in X \setminus F_n$ . This is a union of disjoint sets with $n$ elements and $1$ element, so $F_{n+1}$ has $n + 1$ elements by Proposition 4.1.5.

In particular $F_n \ne X$ for every $n \in \mathbb{N}$ , so we may define $x_n \mathrel{:=} c(X \setminus F_n) \in X \setminus F_n , \qquad\text{and then}\qquad F_{n+1} = F_n \cup \{x_n\} .$ Hence $F_n \subseteq F_{n+1}$ for every $n$ , and by induction on $k$ , $F_m \subseteq F_{m+k}$ for all $m, k \in \mathbb{N}$ .

Now let $m, n \in \mathbb{N}$ with $m < n$ . Then $x_m \in F_{m+1} \subseteq F_n$ , because $m + 1 \le n$ (Lemma 3.1.1 (e)), so $k \mathrel{:=} n - (m + 1) \in \mathbb{N}$ (Lemma 3.1.1 (d)) and $F_{m+1} \subseteq F_{(m+1)+k} = F_n$ ; and $x_n \notin F_n$ . So $x_m \ne x_n$ . Hence $n \mapsto x_n$ is an injection $\mathbb{N} \to X$ . Its image $\{ x_n : n \in \mathbb{N} \} \subseteq X$ is equinumerous with $\mathbb{N}$ , since $n \mapsto x_n$ is a bijection from $\mathbb{N}$ onto it. This proves the theorem.

The proof shows where the axiom enters and why one $\mathrm{\exists E}$ per step is not enough: $\mathrm{\exists E}$ names one element for one set, while the recursion needs $g$ as a single function defined on every stage at once. Each $F_n$ is then determined by $c$ ; the only arbitrary thing is $c$ itself.

A non-example by a minimal change. Run the same construction on the finite set $X = \{a, b\}$ , with $a \ne b$ . The choice function $c$ and the recursion still make sense, since $g$ is defined on every $F \subseteq X$ . But $F_1 = \{ c(X) \}$ has one element, $F_2$ adds the other, so $F_2 = X$ , and from then on $g$ leaves $F_n$ unchanged. So $x_2 = c(X \setminus F_2) = c(\emptyset)$ is not defined. The step that fails is “ $F_n$ is finite and $X$ is not, so $F_n \ne X$ ”, exactly where the hypothesis that $X$ is infinite is used.

Remark. Compare Analysis on the Real Line, Chapter 1’s proof that the real numbers cannot be listed. There, a given list is used to build nested closed intervals, and each interval is obtained from the previous one by an explicit rule (keep an outer third that misses the next point of the list), so no choice principle is involved. Here $X$ is an arbitrary infinite set, and there is no rule available for picking an element of an arbitrary non-empty subset of it; the choice function is the rule.

For a particular $X$ a rule may exist: for $X \subseteq \mathbb{N}$ , “the least element” is one (Theorem 3.1.3), and then the proof needs no axiom. That the theorem cannot be proved in general from the other rules of set formation alone is a result of set theory; we state it without proof, and nothing depends on it.

6.1.8. Consequences: the smallest infinite size

The theorem says $\left| \mathbb{N} \right| \le \left| X \right|$ for every infinite $X$ (Definition 4.4.1). Three consequences follow at once.

$\mathbb{N}$ is the smallest infinite size. If $X$ is infinite and $\left| X \right| \le \left| \mathbb{N} \right|$ , then $\left| X \right| = \left| \mathbb{N} \right|$ , by Theorem 4.4.3 and the theorem. So no infinite set is strictly smaller than $\mathbb{N}$ .
Countable sets are exactly the sets of size at most $\left| \mathbb{N} \right|$ , by Theorem 4.2.2, (i) $\iff$ (ii). Combining with the first point: a countable set is finite or equinumerous with $\mathbb{N}$ , which Theorem 4.2.2 (iii) already said.
An uncountable set is strictly bigger than $\mathbb{N}$ . If $X$ is uncountable, then $X$ is infinite (a finite set is countable, by Theorem 4.2.2), so $\left| \mathbb{N} \right| \le \left| X \right|$ ; and $\left| \mathbb{N} \right| = \left| X \right|$ would make $X$ countable. So $\left| \mathbb{N} \right| < \left| X \right|$ . For example $\left| \mathbb{N} \right| < \left| \mathbb{R} \right|$ , since $\mathbb{R}$ is uncountable (Theorem 4.3.4).

Warning. “Infinite” and “uncountable” are different words. $\mathbb{Q}$ is infinite (it contains $\mathbb{N}$ , which is infinite by Example (Hilbert’s Hotel), and a subset of a finite set is finite, by Proposition 4.1.6) and countable (Theorem 4.2.8). Likewise “ $X$ contains a copy of $\mathbb{N}$ ” is not “ $X$ is equinumerous with $\mathbb{N}$ ”: $\mathbb{R}$ contains $\mathbb{N}$ , and $\left| \mathbb{N} \right| < \left| \mathbb{R} \right|$ (as above).

Quick check. Let $X$ be uncountable. Is $X \setminus \{x\}$ uncountable for every $x \in X$ ? Why must $X$ have an element at all?

Solution. $X \ne \emptyset$ , because $\emptyset$ is countable by Definition 4.2.1. For $x \in X$ , if $X \setminus \{x\}$ were countable, then $X = (X \setminus \{x\}) \cup \{x\}$ would be a union of two countable sets, countable by Proposition 4.2.5. So $X \setminus \{x\}$ is uncountable.

6.1.9. Infinite sets are the same size as a proper part

Section 4.1 proved that a finite set is never equinumerous with a proper subset (Theorem 4.1.9), and Example (Hilbert’s Hotel) showed $\mathbb{N}$ doing exactly that. With Theorem 6.1.5, the hotel can be built inside any infinite set: run it on the copy of $\mathbb{N}$ , and leave everything else alone.

Theorem 6.1.6 (Infinite Sets and Proper Subsets)

A set $X$ is infinite if and only if $\left| X \right| = \left| Y \right|$ for some proper subset $Y \subsetneq X$ .

Idea. One direction is already done: Section 4.1 showed that finite sets have no proper subset of their own size. For the other, take the copy $x_0, x_1, x_2, \dots$ of $\mathbb{N}$ inside $X$ and move every guest one room up, $x_n \mapsto x_{n+1}$ , as $n \mapsto n + 1$ does in the Quick check after Example (Hilbert’s Hotel). Room $x_0$ is vacated, and every point outside the copy stays where it is.

Proof. $(\Leftarrow)$ This is the contrapositive of Theorem 4.1.9: a finite set is not equinumerous with any proper subset, so a set that is equinumerous with one is not finite.

$(\Rightarrow)$ Let $X$ be infinite. By Theorem 6.1.5 (which uses Axiom 6.1.1) there is an injection $s \colon \mathbb{N} \to X$ . By Proposition 4.5.1 (a), $Y \mathrel{:=} X \setminus \{s(0)\}$ has $\left| Y \right| = \left| X \right|$ , and $Y$ is a proper subset, as $s(0) \in X \setminus Y$ . This proves the theorem.

Together with Section 4.1, this gives a characterization of “infinite” that never mentions $\mathbb{N}$ or counting: a set is infinite precisely when some proper part of it is as big as the whole. The finite intuition “a part is smaller than the whole” is exactly the property that separates finite sets from infinite ones. The direction $(\Rightarrow)$ used Axiom 6.1.1, through Theorem 6.1.5; the direction $(\Leftarrow)$ did not.

Quick check. Name a proper subset of $\mathbb{R}$ that is equinumerous with $\mathbb{R}$ , and give a bijection.

Solution. $(-1, 1)$ , with the bijection $x \mapsto x/(1 + \left| x \right|)$ of Example (The real line and its intervals). (Any interval with more than one point other than $\mathbb{R}$ itself works, by the same example.) No choice is needed for $\mathbb{R}$ : the bijection is a formula.

6.1.10. Exercises

A. Check your understanding

Exercise (A1)

These parts are about the proofs of Theorem 6.1.4, Theorem 6.1.5 and Theorem 6.1.6.

(a) Which line of the proof of part (a) of Theorem 6.1.4 uses Axiom 6.1.1? What are the index set $I$ and the sets $A_i$ of the axiom at that line?
(b) Why does the proof of Theorem 6.1.4 introduce the set $J$ ?
(c) Run the proof of Theorem 6.1.4 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) Is Axiom 6.1.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.
(e) Where does the proof of Theorem 6.1.5 use Axiom 6.1.1? Why is one $\mathrm{\exists E}$ per step not enough?
(f) The proof of Theorem 6.1.6 passes the copy of $\mathbb{N}$ to Proposition 4.5.1 (a), whose proof moves each $s(n)$ to $s(n + 1)$ and fixes every other point. Write down the resulting bijection $X \to X \setminus \{s(0)\}$ for $X = \mathbb{Z}$ and $s(n) = n$ for $n \in \mathbb{N}$ .

Solution.

(a) The line “By Axiom 6.1.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 2.1.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) No. The union is a subset of $\mathbb{N}$ , so it is countable by Proposition 4.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 3.1.3) is a rule that maps $\mathbb{N}$ onto any non-empty $A \subseteq \mathbb{N}$ .)
(e) At the line “By Axiom 6.1.1 there is a function $c$ with $c(S) \in S$ for every non-empty $S \subseteq X$ .” One $\mathrm{\exists E}$ names one element of one non-empty set; that would give $x_0$ , then $x_1$ , and any finite number of steps. But Theorem 3.3.1 needs the step as a function $g$ , defined once for every stage $F$ at once, before the sequence exists. Defining $g$ means picking an element of $X \setminus F$ for every such $F$ simultaneously, and that is what the axiom provides.
(f) $h(n) = n + 1$ for $n \in \mathbb{N}$ , and $h(k) = k$ for $k < 0$ . It maps $\mathbb{Z}$ onto $\mathbb{Z} \setminus \{0\}$ : a positive $m$ is $h(m - 1)$ , and a negative $k$ is $h(k)$ . No choice is needed here: the copy of $\mathbb{N}$ inside $\mathbb{Z}$ is given.

B. Practice

Exercise (B1: Which constructions need choice?)

Determine which of the following constructions need Axiom 6.1.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 3.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 6.1.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 3.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.2.3, Definition 1.3.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 4.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 6.1.4 (a) applies. This route uses Axiom 6.1.1, through the theorem.

Without choice. Fix one surjection $\sigma \colon \mathbb{N} \to \mathbb{N} \times \mathbb{N}$ (Theorem 4.2.6, Definition 4.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 3.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: Prove or disprove)

Prove each true statement, naming each use of Axiom 6.1.1 as in Example (Method: name the choice), and refute each false one with a concrete counterexample.

(a) If $A_n$ is finite for every $n \in \mathbb{N}$ , then $\bigcup_{n \in \mathbb{N}} A_n$ is countable.
(b) If $A_n$ is finite for every $n \in \mathbb{N}$ , then $\bigcup_{n \in \mathbb{N}} A_n$ is finite.
(c) Every surjection $f \colon \mathbb{N} \to Y$ has a right inverse that can be defined without Axiom 6.1.1.
(d) If $A_n$ is countable for every $n \in \mathbb{N}$ , then $\bigcup_{n \in \mathbb{N}} A_n$ is countably infinite.
(e) If $A_n \ne \emptyset$ for every $n \in \mathbb{N}$ and $\bigcup_{n \in \mathbb{N}} A_n$ is finite, then $A_m \cap A_n \ne \emptyset$ for some $m \ne n$ .
(f) Every infinite set $X$ admits a surjection $X \to \mathbb{N}$ .
(g) If a set $X$ admits a surjection $X \to \mathbb{N}$ , then $X$ is countable.

Solution.

(a) True. Finite sets are countable (Theorem 4.2.2, (iii) $\Rightarrow$ (i)), and Theorem 6.1.4 (a) applies. That theorem uses Axiom 6.1.1.
(b) False. Take $A_n \mathrel{:=} \{n\}$ : the union is $\mathbb{N}$ , which is infinite (Example (Hilbert’s Hotel)).
(c) True. For $y \in Y$ , the set $f^{-1}(\{y\}) \subseteq \mathbb{N}$ is non-empty, since $f$ is onto, so $g(y) \mathrel{:=} \min f^{-1}(\{y\})$ exists by Theorem 3.1.3. This is a rule, and $f(g(y)) = y$ .
(d) False. Take $A_n \mathrel{:=} \{0\}$ for every $n$ : the union is $\{0\}$ , which is finite, hence not countably infinite: a bijection $\mathbb{N} \to \{0\}$ would make $\mathbb{N}$ finite (Proposition 4.1.1, Definition 4.1.2), against Example (Hilbert’s Hotel).
(e) True, with no axiom. The set $U \mathrel{:=} \bigcup_{n \in \mathbb{N}} A_n$ is non-empty (it contains the elements of $A_0$ ) and finite, say with $k \ge 1$ elements via a bijection $\varphi \colon \{1, \dots, k\} \to U$ (one $\mathrm{\exists E}$ ). Define $c(n) \mathrel{:=} \varphi\bigl(\min \{ j : \varphi(j) \in A_n \}\bigr)$ (Theorem 3.1.3); the set is non-empty because $A_n \ne \emptyset$ and $\varphi$ is onto. This is a rule, and $c(n) \in A_n$ . If $c$ were injective, $\mathbb{N}$ would be equinumerous with $c(\mathbb{N}) \subseteq U$ , which is finite (Proposition 4.1.6). Then $\mathbb{N}$ would be finite (Proposition 4.1.1, Definition 4.1.2), against Example (Hilbert’s Hotel). So $c(m) = c(n)$ for some $m \ne n$ , and that element lies in $A_m \cap A_n$ . This is the pigeonhole idea of Example (Method: the pigeonhole principle), with infinitely many pigeons.
(f) True, using the axiom. By Theorem 6.1.5 (which uses Axiom 6.1.1) there is an injection $\mathbb{N} \to X$ . Since $\mathbb{N} \ne \emptyset$ , Proposition 4.4.2 gives a surjection $X \to \mathbb{N}$ ; that step uses no choice. (Concretely, with the injection written $n \mapsto x_n$ : send $x_n$ to $n$ and every other point to $0$ .)
(g) False. $x \mapsto \left\lfloor \left| x \right| \right\rfloor$ , the integer part of $\left| x \right|$ (the $m \in \mathbb{N}$ with $m \le \left| x \right| < m + 1$ , a school fact), maps $\mathbb{R}$ onto $\mathbb{N}$ (each $n \in \mathbb{N}$ is the image of $n$ ), and $\mathbb{R}$ is uncountable (Theorem 4.3.4). A surjection onto $\mathbb{N}$ says $X$ is at least as big as $\mathbb{N}$ , not at most.

Exercise (B4: Absorbing a countable set)

Let $X$ be infinite, and let $C$ be countable with $C \cap X = \emptyset$ . Prove that $\left| X \cup C \right| = \left| X \right|$ .

Hint: absorb $C$ into a countably infinite subset of $X$ .

Solution. By Theorem 6.1.5 (using Axiom 6.1.1) there is an injection $s \colon \mathbb{N} \to X$ ; its image $S \mathrel{:=} s(\mathbb{N})$ is a countably infinite subset of $X$ . Now Proposition 4.5.1 (b) gives $\left| X \cup C \right| = \left| X \right|$ . The axiom enters only through the copy $s$ ; the absorbing itself is a rule.

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 6.1.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 4.2.1). By Axiom 6.1.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.3.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 4.2.3), $J \times \mathbb{N}$ is countable (Corollary 4.2.7 (a)) and non-empty, so some $s \colon \mathbb{N} \to J \times \mathbb{N}$ is onto (Definition 4.2.1), and so is $F \circ s \colon \mathbb{N} \to U$ (Theorem 2.2.1 (b)). This is the proof of Theorem 6.1.4 (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 6.1.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 6.1.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 3.1.3); 2 for its injectivity; 2 for concluding with Theorem 4.2.6 and Theorem 4.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: Finite unions)

(a) Prove, without Axiom 6.1.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 6.1.4.

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 the image of a bijection from $\{1, \dots, 0\} = \emptyset$ (Definition 4.1.2), so it is empty and $\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. A bijection $\{1, \dots, n + 1\} \to I$ (Definition 4.1.2) has a value at $1$ , so $I \ne \emptyset$ ; pick $i_0 \in I$ . Then $I' \mathrel{:=} I \setminus \{i_0\}$ has $n$ elements (Corollary 4.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 4.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.

Marking scheme. (10 points) - 2: states $P(n)$ , quantified over all sets $I$ with $n$ elements and all families of countable sets. - 1: base case. - 2: shows $I \ne \emptyset$ , picks $i_0$ and shows that $I \setminus \{i_0\}$ has $n$ elements (Corollary 4.1.7). - 2: proves $\bigcup_{i \in I} A_i = B \cup A_{i_0}$ . - 1: applies $P(n)$ and Proposition 4.2.5 to conclude. - 2: part (b), in two sentences. Fatal error (0 for the step): an induction that “reaches” $n = \mathbb{N}$ , or that treats $\mathbb{N}$ as a finite index set.

Exercise (C3: Removing a countable set)

Let $X$ be uncountable and let $C \subseteq X$ be countable. Deduce from Exercise (B4: Absorbing a countable set) that $\left| X \setminus C \right| = \left| X \right|$ .

Solution. The set $X \setminus C$ is uncountable: otherwise $X = (X \setminus C) \cup C$ would be a union of two countable sets, countable by Proposition 4.2.5, against the choice of $X$ . An uncountable set is infinite, since finite sets are countable (Theorem 4.2.2). Now apply Exercise (B4: Absorbing a countable set) with $X \setminus C$ in the role of $X$ and $C$ as the countable set, which is disjoint from $X \setminus C$ : $\left| (X \setminus C) \cup C \right| = \left| X \setminus C \right|$ , and the left side is $\left| X \right|$ because $C \subseteq X$ . Here $X \setminus C$ is given by no formula, so no explicit copy of $\mathbb{N}$ in it is available; the copy comes from Theorem 6.1.5, which uses Axiom 6.1.1. For $X = \mathbb{R}$ and $C = \mathbb{Q}$ (Theorem 4.2.8, Theorem 4.3.4) this is $\left| \mathbb{R} \setminus \mathbb{Q} \right| = \left| \mathbb{R} \right|$ , which Section 4.5, Exercise B5 (a) proves without the axiom, using the explicit copy $n \mapsto \sqrt2 + n$ .