3.6 Infinite Sets

Section 3.5 compared sizes with injections. Here we ask where $\mathbb{N}$ sits in that comparison. Every infinite set we have met contains a copy of $\mathbb{N}$ , and it is tempting to say that this must always happen by picking new elements one at a time; this section makes that picking exact. It turns out to need Axiom 3.3.1 again, this time applied to a family with one set for each non-empty subset of the given set, 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.

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

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 3.2.2). Equivalently, we want an injection $\mathbb{N} \to X$ : its image is then such a subset.

Theorem 3.6.1 (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 2.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 3.3.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 3.3.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 2.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 3.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 3.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 2.1.1 (e)), so $k \mathrel{:=} n - (m + 1) \in \mathbb{N}$ (Lemma 2.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 2.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.

3.6.2. Consequences: the smallest infinite size

The theorem says $\left| \mathbb{N} \right| \le \left| X \right|$ for every infinite $X$ (Definition 3.5.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 3.5.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 3.2.2, (i) $\iff$ (ii). Combining with the first point: a countable set is finite or equinumerous with $\mathbb{N}$ , which Theorem 3.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 3.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 3.4.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 3.1.6) and countable (Theorem 3.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 3.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 3.2.5. So $X \setminus \{x\}$ is uncountable.

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

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

Theorem 3.6.2 (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 3.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 3.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 3.6.1 there is an injection $n \mapsto x_n$ from $\mathbb{N}$ to $X$ ; let $S \mathrel{:=} \{ x_n : n \in \mathbb{N} \}$ . Each element of $S$ is $x_n$ for exactly one $n \in \mathbb{N}$ , by injectivity. Define $h \colon X \to X \setminus \{x_0\}$ by $h(x) \mathrel{:=} \begin{cases} x_{n+1} & \text{if } x = x_n \text{ with } n \in \mathbb{N}, \\ x & \text{if } x \notin S . \end{cases}$ This is a function into $X \setminus \{x_0\}$ : $x_{n+1} \ne x_0$ because $n + 1 \ne 0$ , and an $x \notin S$ is not $x_0$ .

$h$ is injective. Two points of $S$ : $x_{m+1} = x_{n+1}$ gives $m + 1 = n + 1$ , so $m = n$ . Two points outside $S$ : $h$ is the identity there. One of each: $h(x_n) = x_{n+1} \in S$ , while $h(x) = x \notin S$ , so the values differ.

$h$ is onto $X \setminus \{x_0\}$ . Let $y \in X \setminus \{x_0\}$ . If $y \notin S$ , then $y = h(y)$ . If $y \in S$ , then $y = x_m$ with $m \ne 0$ , so $n \mathrel{:=} m - 1 \in \mathbb{N}$ (Lemma 2.1.1 (c)) and $y = x_{n+1} = h(x_n)$ .

So $h$ is a bijection, and $Y \mathrel{:=} X \setminus \{x_0\}$ is a proper subset of $X$ , as $x_0 \in X \setminus Y$ , with $\left| X \right| = \left| Y \right|$ . This proves the theorem.

Together with Section 3.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 3.3.1, through Theorem 3.6.1; 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.

3.6.4. Exercises

A. Check your understanding

Exercise (A1)

(a) Where does the proof of Theorem 3.6.1 use Axiom 3.3.1? Why is one $\mathrm{\exists E}$ per step not enough?
(b) True or false, with a reason: every infinite subset of $\mathbb{R}$ contains a countably infinite subset; every uncountable set contains an uncountable proper subset.
(c) Write down the bijection $X \to X \setminus \{x_0\}$ of the proof of Theorem 3.6.2 for $X = \mathbb{Z}$ and $x_n = n$ for $n \in \mathbb{N}$ .
(d) For $X = \mathbb{N}$ , is choice needed to find a countably infinite subset?

Solution.

(a) At the line “By Axiom 3.3.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 2.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.
(b) Both are true. The first is Theorem 3.6.1 applied to the infinite subset. For the second, let $X$ be uncountable; then $X \ne \emptyset$ , and for $x \in X$ , $X \setminus \{x\}$ is an uncountable proper subset, by the Quick check after the warning above.
(c) $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)$ .
(d) No. $\mathbb{N}$ itself is countably infinite, via $\operatorname{id}_{\mathbb{N}}$ . (More generally, an infinite $X \subseteq \mathbb{N}$ can be listed in increasing order by Lemma 3.2.1, a rule.)

B. Practice

Exercise (B1: Removing finitely many points)

Let $X$ be infinite and let $F \subseteq X$ be finite. Prove that $\left| X \setminus F \right| = \left| X \right|$ .

Solution. First, $X \setminus F$ is infinite: otherwise $X = (X \setminus F) \cup F$ would be a union of two disjoint finite sets, finite by Proposition 3.1.5.

By Theorem 3.6.1 applied to $X \setminus F$ (this uses Axiom 3.3.1), there is an injection $n \mapsto s_n$ from $\mathbb{N}$ to $X \setminus F$ ; let $S \mathrel{:=} \{ s_n : n \in \mathbb{N} \}$ . Let $F$ have $k$ elements, and let $\varphi \colon \{1, \dots, k\} \to F$ be a bijection (Definition 3.1.2). No two of $X \setminus (F \cup S)$ , $F$ and $S$ meet, and together they make up $X$ ; and $X \setminus F$ is the union of the disjoint sets $X \setminus (F \cup S)$ and $S$ . Define $h \colon X \to X \setminus F$ by $h(x) \mathrel{:=} \begin{cases} x & \text{if } x \notin F \cup S, \\ s_{i-1} & \text{if } x = \varphi(i), \ i \in \{1, \dots, k\}, \\ s_{n+k} & \text{if } x = s_n, \ n \in \mathbb{N} . \end{cases}$ Each $x$ falls under one case, with one $i$ or one $n$ , since $\varphi$ and $n \mapsto s_n$ are injective. The second case sends $F$ bijectively onto $\{s_0, \dots, s_{k-1}\}$ , and the third sends $S$ bijectively onto $\{ s_m : m \ge k \}$ ; these two image sets are disjoint and together make up $S$ . The first case is the identity on $X \setminus (F \cup S)$ . So $h$ is a bijection, and $\left| X \setminus F \right| = \left| X \right|$ . (For $k = 0$ , $F = \emptyset$ and $h$ is the identity.)

Exercise (B2: 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 3.6.1 (using Axiom 3.3.1) there is a countably infinite $S \subseteq X$ . The set $S \cup C$ is countable by Proposition 3.2.5, and infinite, because it contains $S$ (a subset of a finite set is finite, Proposition 3.1.6), which is infinite: if $\varphi \colon \{1, \dots, k\} \to S$ were a bijection and $\beta \colon \mathbb{N} \to S$ is a bijection given by the theorem, then $\beta^{-1} \circ \varphi$ would be a bijection $\{1, \dots, k\} \to \mathbb{N}$ (Proposition 3.1.1, Theorem 1.4.4), against Example (Hilbert’s Hotel). By Theorem 3.2.2 (iii), $S \cup C$ is countably infinite. So $\left| S \cup C \right| = \left| \mathbb{N} \right| = \left| S \right|$ , and Proposition 3.1.1 gives a bijection $\psi \colon S \cup C \to S$ .

Now $X \cup C$ is the union of the disjoint sets $X \setminus S$ and $S \cup C$ (disjoint because $C \cap X = \emptyset$ ), and $X$ is the union of the disjoint sets $X \setminus S$ and $S$ . Define $h \colon X \cup C \to X$ by $h(x) \mathrel{:=} x$ for $x \in X \setminus S$ and $h(x) \mathrel{:=} \psi(x)$ for $x \in S \cup C$ . It is a bijection on each piece, onto the corresponding piece, so it is a bijection, and $\left| X \cup C \right| = \left| X \right|$ .

Exercise (B3: A big hole)

Give an example of an infinite set $X$ and a proper subset $Y \subsetneq X$ with $\left| Y \right| = \left| X \right|$ and $X \setminus Y$ infinite. Check each property, and list the properties any answer must have.

Solution. An answer must have: (1) $Y \subseteq X$ ; (2) $Y \ne X$ ; (3) a bijection $X \to Y$ , or injections both ways; (4) $X$ infinite; (5) $X \setminus Y$ infinite. (The hole $X \setminus Y$ in the proof of Theorem 3.6.2 was the single point $x_0$ ; this asks for more.)

Example: $X = \mathbb{N}$ , $Y = 2\mathbb{N}$ . (1), (2): $2\mathbb{N} \subseteq \mathbb{N}$ and $1 \notin 2\mathbb{N}$ . (3): $n \mapsto 2n$ is a bijection $\mathbb{N} \to 2\mathbb{N}$ (Example (Hilbert’s Hotel)). (4): $\mathbb{N}$ is infinite (Example (Hilbert’s Hotel)). (5): $X \setminus Y$ is the set of odd numbers (every $m \in \mathbb{N}$ is even or odd, not both, by Theorem 2.2.3), and $n \mapsto 2n + 1$ is a bijection from $\mathbb{N}$ onto it; if it were finite, $\mathbb{N}$ would be finite too (compose with a bijection from $\{1, \dots, k\}$ , Theorem 1.4.4), which it is not.

Another correct answer: $X = \mathbb{R}$ , $Y = (0, \infty)$ . (1), (2): $(0, \infty) \subseteq \mathbb{R}$ and $0 \notin (0, \infty)$ . (3): Example (The real line and its intervals). (4), (5): $n \mapsto -n$ is a bijection from $\mathbb{N}$ onto $\{ -n : n \in \mathbb{N} \}$ , so this set is infinite, as in (5) above. It lies inside $X \setminus Y = (-\infty, 0] \subseteq \mathbb{R}$ , so by Proposition 3.1.6 neither $(-\infty, 0]$ nor $\mathbb{R}$ is finite.

C. Going deeper

Exercise (C1: Increasing functions)

A function $f \colon \mathbb{N} \to \mathbb{N}$ is strictly increasing if $f(m) < f(n)$ whenever $m < n$ . Let $I$ be the set of strictly increasing functions $\mathbb{N} \to \mathbb{N}$ . Prove that $I$ is uncountable.

Below, the proof is started; the second half is blank. Name the move, then complete it.

Let $n \mapsto f_n$ be any function from $\mathbb{N}$ to $I$ . By Theorem 2.3.1, applied with the set $\mathbb{N}$ , the starting value $f_0(0) + 1$ and the function $(n, x) \mapsto \max\{ x, f_{n+1}(n + 1) \} + 1$ from $\mathbb{N} \times \mathbb{N}$ to $\mathbb{N}$ (a step that depends on $n$ ), there is a function $g \colon \mathbb{N} \to \mathbb{N}$ with $g(0) = f_0(0) + 1, \qquad g(n + 1) = \max\{ g(n), f_{n+1}(n + 1) \} + 1 .$ $\underline{\hspace{8em}}$

Solution (Hint 1). Two things must be shown about $g$ : that it lies in $I$ , and that it differs from each $f_n$ somewhere. Where?

Solution (Hint 2). The second half begins: “For every $n \in \mathbb{N}$ , $g(n + 1) \ge g(n) + 1 > g(n)$ .”

Solution. The move is the diagonal: given any list, build an object that differs from the $n$ -th entry at the $n$ -th place. Here the object must also stay inside $I$ , which is why $g(n + 1)$ is pushed above $g(n)$ as well as above $f_{n+1}(n + 1)$ .

Completion. For every $n \in \mathbb{N}$ , $g(n + 1) = \max\{ g(n), f_{n+1}(n + 1) \} + 1 \ge g(n) + 1 > g(n)$ . From this, $g(m) < g(n)$ whenever $m < n$ , by induction on $n$ (Theorem 2.2.1 with base $m + 1$ ): $g(m) < g(m + 1)$ , and $g(m) < g(n) < g(n + 1)$ . So $g \in I$ .

Next, $g(n) > f_n(n)$ for every $n \in \mathbb{N}$ : for $n = 0$ , $g(0) = f_0(0) + 1$ ; for $n = k + 1$ , $g(k + 1) \ge f_{k+1}(k + 1) + 1$ . So $g(n) \ne f_n(n)$ , and hence $g \ne f_n$ , for every $n \in \mathbb{N}$ . So $g \in I$ is not a value of $n \mapsto f_n$ , and no function $\mathbb{N} \to I$ is onto. Since $I \ne \emptyset$ (it contains $\operatorname{id}_{\mathbb{N}}$ ), $I$ is not countable.

Marking scheme. (10 points) - 1: names the diagonal move. - 4: shows $g$ is strictly increasing: 2 for the step $g(n) < g(n + 1)$ for every $n$ , and 2 for the passage to all $m < n$ . - 3: shows $g(n) > f_n(n)$ for every $n$ , treating $n = 0$ and $n = k + 1$ separately, and concludes $g \ne f_n$ . - 2: concludes that no function $\mathbb{N} \to I$ is onto and, noting $I \ne \emptyset$ ( $\operatorname{id}_{\mathbb{N}} \in I$ ), that $I$ is not countable. Fatal errors (0 for the part concerned): taking $g(n) < g(n + 1)$ alone as strict increase, with no passage to all $m < n$ ; inferring $g \ne f_n$ without exhibiting a point where they differ, or exhibiting one only for $n \ge 1$ .

The max in $g$ is needed: the plain diagonal $g(n) \mathrel{:=} f_n(n) + 1$ need not be strictly increasing (for $f_0(n) = 5 + n$ and $f_1(n) = n$ , it gives $g(0) = 6 > g(1) = 2$ ).

Exercise (C2: The irrationals)

Deduce from Exercise (B2: Absorbing a countable set) that $\left| \mathbb{R} \setminus \mathbb{Q} \right| = \left| \mathbb{R} \right|$ .

Solution. The set $\mathbb{R} \setminus \mathbb{Q}$ is uncountable: otherwise $\mathbb{R} = (\mathbb{R} \setminus \mathbb{Q}) \cup \mathbb{Q}$ would be a union of two countable sets (Theorem 3.2.8), countable by Proposition 3.2.5, against Theorem 3.4.4. An uncountable set is infinite, since finite sets are countable (Theorem 3.2.2). Now apply Exercise (B2: Absorbing a countable set) with $X \mathrel{:=} \mathbb{R} \setminus \mathbb{Q}$ and $C \mathrel{:=} \mathbb{Q}$ , which is countable and disjoint from $X$ : $\left| (\mathbb{R} \setminus \mathbb{Q}) \cup \mathbb{Q} \right| = \left| \mathbb{R} \setminus \mathbb{Q} \right|$ , and the left side is $\left| \mathbb{R} \right|$ .

R. Review

Exercise (R1)

Prove that every integer $n \ge 1$ is a sum of distinct powers of $2$ : there are an integer $r \ge 1$ and natural numbers $k_1 > k_2 > \dots > k_r$ with $n = 2^{k_1} + 2^{k_2} + \dots + 2^{k_r}$ .

Solution. We use Theorem 2.2.2 with $n_0 = 1$ . Let $n \ge 1$ , and suppose every integer $m$ with $1 \le m < n$ is such a sum.

The largest power of $2$ not above $n$ . The set $T \mathrel{:=} \{ k \in \mathbb{N} : 2^k > n \}$ is non-empty, since $2^n \ge 1 + n > n$ by Theorem 2.3.7 with $x = 1$ . By Theorem 2.1.3 it has a least element $m$ . Since $2^0 = 1 \le n$ , $0 \notin T$ , so $m \ge 1$ , and $K \mathrel{:=} m - 1 \in \mathbb{N}$ (Lemma 2.1.1 (c)). As $K < m$ , $K \notin T$ ; so $2^K \le n < 2^{K+1} .$ The step. Let $s \mathrel{:=} n - 2^K$ , so $0 \le s < 2^{K+1} - 2^K = 2^K$ . If $s = 0$ , then $n = 2^K$ , a sum with $r = 1$ . If $s \ge 1$ , then $s < n$ , because $2^K \ge 1$ . By the hypothesis, $s = 2^{k_1} + \dots + 2^{k_r}$ with $k_1 > \dots > k_r$ . Each $2^{k_i} \le s < 2^K$ , so $k_i < K$ (if $k_i \ge K$ , then $2^{k_i} \ge 2^K$ by Proposition 2.3.4 (e)). Hence $n = 2^K + 2^{k_1} + \dots + 2^{k_r}, \qquad K > k_1 > \dots > k_r ,$ a sum of distinct powers of $2$ . By Theorem 2.2.2, every $n \ge 1$ is such a sum. For example $13 = 2^3 + 2^2 + 2^0$ .

The base $1$ is the right one: $0$ is not a sum of one or more powers of $2$ , since each power is positive.

Exercise (R2)

Show that $\forall x\, \exists y\, R(x, y) \nvdash \exists y\, \forall x\, R(x, y)$ by a counter-model whose domain is $\mathbb{N}$ . Say in words what the two sentences say when $R(x, y)$ is read as “ $x < y$ ”.

Solution. Let $\mathfrak{M}$ have domain $\mathbb{N}$ and $R^{\mathfrak{M}} \mathrel{:=} \{ (d, e) \in \mathbb{N} \times \mathbb{N} : d < e \}$ . Both formulas are sentences, so no assignment matters.

The premise is true. $\forall x\, \exists y\, (x < y)$ says “every natural number has a larger one”. For each $d \in \mathbb{N}$ , $e \mathrel{:=} d + 1 \in \mathbb{N}$ has $d < e$ .

The conclusion is false. $\exists y\, \forall x\, (x < y)$ says “some natural number is larger than every natural number”. For any $e \in \mathbb{N}$ , the choice $d \mathrel{:=} e$ gives $d < e$ false, so no $e$ works.

So $\mathfrak{M}$ is a counter-model, and $\forall x\, \exists y\, R(x, y) \not\models \exists y\, \forall x\, R(x, y)$ . By the soundness statement of Logic and Proof, Section 7.2 (the subsection “From counter-models to non-derivability”), a counter-model shows non-derivability: $\forall x\, \exists y\, R(x, y) \nvdash \exists y\, \forall x\, R(x, y)$ .

This is the converse of Logic and Proof, Proposition 5.6.2 with the variables renamed and the two places of $R$ exchanged (read $R(x, y)$ as $R(y, x)$ ), and the counter-model is the one of Logic and Proof, Example (The swap of $\exists$ and $\forall$ ): there the domain was $\mathbb{Z}$ and $R$ was read as $>$ ; with the roles of the variables exchanged, $R$ read as $<$ and the domain cut down to $\mathbb{N}$ , the same witnesses work, as checked above. In the premise the larger number $y$ is chosen after $x$ and depends on it; the conclusion asks for one $y$ in advance.

Exercise (R3)

For an integer $n \ge 1$ , how many truth functions with $n$ inputs are there? Prove your answer.

Solution. There are $2^{2^n}$ . A truth function with $n$ inputs (Logic and Proof, Definition 4.4.4) assigns a truth value to each row $(a_1, \dots, a_n)$ ; read a row as the function $i \mapsto a_i$ on $\{1, \dots, n\}$ , and let $L$ be the set of rows.

There are $2^n$ rows. The map sending a row to $\{ i \in \{1, \dots, n\} : a_i = \mathrm{T} \}$ is a bijection $L \to \mathcal{P}\left( \{1, \dots, n\} \right)$ : a row is determined by the places where it is $\mathrm{T}$ , and every set of places arises. Since $\{1, \dots, n\}$ has $n$ elements, Proposition 3.1.8 gives $2^n$ subsets, so $L$ has $2^n$ elements (compose the bijections).

There are $2^{2^n}$ truth functions. In the same way, a truth function $f$ is determined by the set $\{ \rho \in L : f(\rho) = \mathrm{T} \} \subseteq L$ , and every subset of $L$ arises; so the truth functions are in bijection with $\mathcal{P}\left( L \right)$ , which has $2^{2^n}$ elements by Proposition 3.1.8 again. For $n = 1, 2, 3$ this gives $4, 16, 256$ .

Exercise (R4)

A function $f \colon \mathbb{N} \to \mathbb{N}$ is eventually zero if there is $N \in \mathbb{N}$ with $f(n) = 0$ for every $n \ge N$ . Is the set of eventually zero functions countable?

Solution. Yes. The tool is a countable union of countable sets. For $N \in \mathbb{N}$ let $Z_N$ be the set of $f \colon \mathbb{N} \to \mathbb{N}$ with $f(n) = 0$ for every $n \ge N$ ; the set of eventually zero functions is $Z \mathrel{:=} \bigcup_{N \in \mathbb{N}} Z_N$ . Each $Z_N$ is countable:

$Z_0$ has one element, the zero function, so it is countable.
For $N = 1$ , $f \mapsto f(0)$ is a bijection $Z_1 \to \mathbb{N}$ : a function in $Z_1$ is determined by its value at $0$ , and every value occurs.
For $N \ge 2$ , $f \mapsto (f(0), \dots, f(N - 1))$ is a bijection $Z_N \to \mathbb{N}^N$ , by the same reasoning and the characteristic property of tuples; $\mathbb{N}^N$ is countable by Corollary 3.2.7, and so is $Z_N$ (compose a surjection $\mathbb{N} \to \mathbb{N}^N$ with the inverse bijection, Proposition 3.2.4).

By Theorem 3.3.3, $Z$ is countable. (That theorem uses Axiom 3.3.1; here it could be avoided, since each $Z_N$ comes with an explicit listing, but the question did not ask for that.)

Why the look-alike fails. A diagonal argument, as in Theorem 3.4.1, builds from a list $f_0, f_1, \dots$ of eventually zero functions the function $g(n) \mathrel{:=} f_n(n) + 1$ . It differs from every $f_n$ , but $g(n) \ge 1$ for every $n$ , so $g$ is not eventually zero: it is not in $Z$ , and nothing is contradicted. A diagonal argument proves uncountability only when the diagonal object stays inside the set.