3.5 Comparing Sizes: the Schröder–Bernstein Theorem

We have $(0, 1) \subseteq [0, 1] \subseteq \mathbb{R}$ . Are the three sets the same size? Section 3.1 made “same size” mean “there is a bijection”, and for these sets a bijection is fiddly to write down: $[0, 1]$ has two endpoints that $(0, 1)$ lacks, and $\mathbb{R}$ is unbounded. An injection, on the other hand, is easy in both directions: the inclusion goes one way, and squeezing $[0, 1]$ into the middle of $(0, 1)$ goes the other. This section turns injections into a way of comparing sizes, and proves the theorem that makes the comparison useful: injections both ways give a bijection.

3.5.1. Comparing sizes with injections

An injection $A \to B$ places a copy of $A$ inside $B$ : distinct elements of $A$ go to distinct elements of $B$ , so $B$ has room for all of $A$ . For finite sets this is the pigeonhole principle read the other way round (Corollary 3.1.3). It deserves a name for all sets.

$A$ is at most as big as $B$ when $A$ fits into $B$ without collisions.

Definition 3.5.1 (Comparing Sizes)

Examples.

Subsets. If $A \subseteq B$ , the inclusion $a \mapsto a$ is an injection $A \to B$ , so $\left| A \right| \le \left| B \right|$ . In particular $\left| (0, 1) \right| \le \left| [0, 1] \right| \le \left| \mathbb{R} \right|$ .
The degenerate case. For every set $B$ , $\left| \emptyset \right| \le \left| B \right|$ : the empty function $\emptyset \to B$ (Proposition 1.4.2 (a)) is injective, vacuously, since there are no $x_1, x_2 \in \emptyset$ to test.
Finite sets. Let $A$ have $m$ elements and $B$ have $n$ elements (Definition 3.1.2). Then $\left| A \right| \le \left| B \right|$ exactly when $m \le n$ . If $m \le n$ , take bijections $\varphi \colon \{1, \dots, m\} \to A$ and $\psi \colon \{1, \dots, n\} \to B$ ; the inclusion $\iota \colon \{1, \dots, m\} \to \{1, \dots, n\}$ is injective, so $\psi \circ \iota \circ \varphi^{-1} \colon A \to B$ is injective by Theorem 1.4.4 (a), $\varphi^{-1}$ being a bijection (Theorem 1.5.4). If $m > n$ , there is no injection $A \to B$ by Corollary 3.1.3 (a). So the relation agrees with the count of elements, which is why it is allowed to borrow the symbol $\le$ .
Countable sets. By Theorem 3.2.2, (i) $\iff$ (ii), a set $A$ is countable if and only if $\left| A \right| \le \left| \mathbb{N} \right|$ . “Countable” means “at most as big as $\mathbb{N}$ ”.
Power sets. For every set $X$ , $\left| X \right| < \left| \mathcal{P}\left( X \right) \right|$ . The map $x \mapsto \{x\}$ is an injection $X \to \mathcal{P}\left( X \right)$ , since $\{x_1\} = \{x_2\}$ gives $x_1 \in \{x_2\}$ , so $x_1 = x_2$ . And there is no bijection $X \to \mathcal{P}\left( X \right)$ , because by Theorem 3.4.2 there is not even a surjection. In particular $\left| \mathbb{N} \right| < \left| \mathcal{P}\left( \mathbb{N} \right) \right|$ .

Non-example by minimal change. Replace “injection” by “function” in the definition. Then any set would be “at most as big as” any non-empty set, by a constant map: $\mathbb{R} \to \{0\}$ would put $\mathbb{R}$ below a one-element set. The clause that carries the meaning is “no two elements collide”.

Warning. $\left| A \right| < \left| B \right|$ does not mean “there is an injection $A \to B$ that is not a bijection”. The map $n \mapsto n + 1$ is an injection $\mathbb{N} \to \mathbb{N}$ that misses $0$ , and yet $\left| \mathbb{N} \right| = \left| \mathbb{N} \right|$ . For infinite sets one injection that fails to be onto proves nothing about strictness; $\left| A \right| < \left| B \right|$ needs every map $A \to B$ to fail to be a bijection, which is why Cantor’s theorem, a statement about every $f \colon X \to \mathcal{P}\left( X \right)$ , is the source of our strict inequalities.

The relation behaves like an order in two of the three ways. The third is the content of this section’s theorem.

Proposition 3.5.1 (Comparing Sizes Is Reflexive and Transitive)

For all sets $A$ , $B$ , $C$ :

(a) $\left| A \right| \le \left| A \right|$ ;
(b) if $\left| A \right| \le \left| B \right|$ and $\left| B \right| \le \left| C \right|$ , then $\left| A \right| \le \left| C \right|$ .

Proof.

(a) The identity $\operatorname{id}_A$ is injective, since $\operatorname{id}_A(x_1) = \operatorname{id}_A(x_2)$ says $x_1 = x_2$ .
(b) Let $f \colon A \to B$ and $g \colon B \to C$ be injections. Then $g \circ f \colon A \to C$ is injective by Theorem 1.4.4 (a). This proves the proposition.

As with equinumerosity (Section 3.1, after Proposition 3.1.1), we do not call this a partial order: there is no set of all sets for it to be a relation on (Theorem 1.1.4). And antisymmetry, the clause (PO2) of Definition 2.6.1, would say “if $\left| A \right| \le \left| B \right|$ and $\left| B \right| \le \left| A \right|$ , then $A = B$ ”, which is false: $\left| \mathbb{N} \right| \le \left| 2\mathbb{N} \right|$ and $\left| 2\mathbb{N} \right| \le \left| \mathbb{N} \right|$ , while $2\mathbb{N} \ne \mathbb{N}$ . The right replacement for “ $A = B$ ” is “ $\left| A \right| = \left| B \right|$ ”. That is the Schröder–Bernstein Theorem below.

Before it, one more way to read $\le$ . A countable set was defined by a surjection from $\mathbb{N}$ , and Theorem 3.2.2 turned that into an injection into $\mathbb{N}$ . The same exchange works for all sets, with one exception and one price.

Proposition 3.5.2 (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)$ Let $f \colon A \to B$ be an injection. Since $A \ne \emptyset$ , Theorem 1.5.1 (b) gives a left inverse $g \colon B \to A$ , so $g \circ f = \operatorname{id}_A$ . This says that $f$ is a right inverse of $g$ (Definition 1.5.1), so $g$ is surjective by Proposition 1.5.2.

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

The hypothesis $A \ne \emptyset$ is needed for $(\Rightarrow)$ only. For $A = \emptyset$ and $B = \{b\}$ , the empty function is an injection $\emptyset \to \{b\}$ , but there is no function $\{b\} \to \emptyset$ at all (Proposition 1.4.2 (b)), let alone a surjection. The proof shows where the hypothesis enters: a left inverse $g \colon B \to A$ must send $b$ somewhere in $A$ . 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 3.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 3.5.2.

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 1.4.1), and the map is injective. No appeal to Proposition 3.5.2 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$ ; this is the correspondence of Section 1.4, recalled after Corollary 3.4.3.)

3.5.2. The Schröder–Bernstein Theorem

Here is the replacement for antisymmetry. To show two sets are the same size, it is enough to fit each into the other.

Theorem 3.5.3 (Schröder–Bernstein Theorem)

Idea. Let $f \colon A \to B$ and $g \colon B \to A$ be the two injections. We want a bijection $h \colon A \to B$ , and at each $a \in A$ there are two candidates: go forward, $h(a) = f(a)$ , or go back along $g$ : let $h(a)$ be the unique $b$ with $g(b) = a$ . Going back is possible only for $a \in g(B)$ . So a point of $A$ not hit by $g$ must be sent forward by $f$ . Then the point $f(a) \in B$ is used up, and $g(f(a))$ must not go back to it, or $h$ would collide; so $g(f(a))$ must also be sent forward, and then $g(f(g(f(a))))$ , and so on along the chain. Everything reached this way goes forward; everything else goes back.

Step roadmap.

① Build the set $C \subseteq A$ of points that are forced forward: $C_0 \mathrel{:=} A \setminus g(B)$ , $C_{n+1} \mathrel{:=} g(f(C_n))$ , $C \mathrel{:=} \bigcup_{n \in \mathbb{N}} C_n$ .

② Define $h(a) \mathrel{:=} f(a)$ on $C$ , and let $h(a)$ be the unique $b$ with $g(b) = a$ off $C$ .

③ Show $h$ is injective; the only case with content is one point of each kind.

④ Show $h$ is onto: for $b \in B$ , look at $g(b)$ and ask whether it lies in $C$ .

Before reading on: in step ④, why is $g(b) \notin C_0$ , and what does that buy?

Proof. Let $f \colon A \to B$ and $g \colon B \to A$ be injections.

Step 1. By Theorem 2.3.1, applied with the set $\mathcal{P}\left( A \right)$ , the starting value $A \setminus g(B) \in \mathcal{P}\left( A \right)$ and the function $(n, S) \mapsto g(f(S))$ from $\mathbb{N} \times \mathcal{P}\left( A \right)$ to $\mathcal{P}\left( A \right)$ , there are sets $C_n \subseteq A$ , for $n \in \mathbb{N}$ , with $C_0 = A \setminus g(B), \qquad C_{n+1} = g\bigl(f(C_n)\bigr) \ \text{ for every } n \in \mathbb{N} .$ Here $f(C_n) \subseteq B$ and $g(f(C_n)) \subseteq A$ are images (Definition 1.6.1). Let $C \mathrel{:=} \bigcup_{n \in \mathbb{N}} C_n \subseteq A$ (Definition 1.2.4). Two facts about $C$ will be used.

(F1) If $a \in C$ , then $g(f(a)) \in C$ . Indeed $a \in C_n$ for some $n \in \mathbb{N}$ ; then $f(a) \in f(C_n)$ , so $g(f(a)) \in g(f(C_n)) = C_{n+1} \subseteq C$ .

(F2) If $a \in A \setminus C$ , there is exactly one $b \in B$ with $g(b) = a$ . It exists because $a \notin C_0 = A \setminus g(B)$ and $a \in A$ , so $a \in g(B)$ . It is unique because $g$ is injective.

Step 2. Define $h \colon A \to B$ by $h(a) \mathrel{:=} \begin{cases} f(a) & \text{if } a \in C, \\ \text{the unique } b \in B \text{ with } g(b) = a & \text{if } a \notin C . \end{cases}$ Each $a \in A$ falls under exactly one case, and in each case the value exists and is unique (in the second case by (F2)), so $h$ is a function. Note that $g(h(a)) = a$ whenever $a \notin C$ .

Step 3.

Claim. $h$ is injective.

Proof of Claim. Let $a, a' \in A$ with $h(a) = h(a')$ .

Case 1: $a, a' \in C$ . Then $f(a) = f(a')$ , and $a = a'$ because $f$ is injective.

Case 2: $a, a' \notin C$ . Then $a = g(h(a)) = g(h(a')) = a'$ .

Case 3: $a \in C$ and $a' \notin C$ . Then $h(a') = h(a) = f(a)$ , so $a' = g(h(a')) = g(f(a))$ . By (F1), $g(f(a)) \in C$ , so $a' \in C$ , a contradiction. So this case does not occur.

The case $a \notin C$ , $a' \in C$ is Case 3 with the roles of $a$ and $a'$ swapped. Hence $a = a'$ in every case that occurs.

Step 4.

Claim. $h$ is surjective.

Proof of Claim. Let $b \in B$ , and consider $g(b) \in A$ .

Case 1: $g(b) \notin C$ . Then $h(g(b))$ is the unique element of $B$ whose image under $g$ is $g(b)$ , and $b$ is such an element. So $h(g(b)) = b$ .

Case 2: $g(b) \in C$ . Then $g(b) \in C_n$ for some $n \in \mathbb{N}$ . Since $g(b) \in g(B)$ , we have $g(b) \notin A \setminus g(B) = C_0$ , so $n \ne 0$ . By Lemma 2.1.1 (c), $k \mathrel{:=} n - 1 \in \mathbb{N}$ , and $g(b) \in C_{k+1} = g(f(C_k))$ . By Definition 1.6.1 there is $b' \in f(C_k)$ with $g(b') = g(b)$ , and then $a \in C_k$ with $f(a) = b'$ . As $g$ is injective, $b = b' = f(a)$ . Since $a \in C_k \subseteq C$ , $h(a) = f(a) = b$ .

In both cases $b$ is a value of $h$ .

By the two claims, $h \colon A \to B$ is a bijection, so $\left| A \right| = \left| B \right|$ . This proves the theorem.

The answer to the prompt: $g(b)$ is a value of $g$ , and $C_0$ consists exactly of the points of $A$ that are not values of $g$ . That is what pushes the index $n$ of Case 2 up to at least $1$ , so that $g(b)$ has a predecessor $a \in C_{n-1}$ in its chain, and $b$ is reached by $f$ from that predecessor.

Every value of $h$ is given by a rule, so the proof makes no use of Axiom 3.3.1: Step 1 is a recursion with an explicit step, and Step 2 picks the unique preimage, where there is nothing to choose. The case split “ $a \in C$ or $a \notin C$ ” is an instance of excluded middle, the classical step discussed in Logic and Proof, Section 8.7; nothing in the proof decides which case holds for a given $a$ , and nothing needs to.

Each hypothesis is used. Without the injection $g$ , the conclusion fails: $\mathbb{N} \to \mathcal{P}\left( \mathbb{N} \right)$ , $n \mapsto \{n\}$ , is an injection, and $\left| \mathbb{N} \right| \ne \left| \mathcal{P}\left( \mathbb{N} \right) \right|$ by Theorem 3.4.2. In the proof, injectivity of $f$ is used once, in Case 1 of Step 3, and injectivity of $g$ twice, in (F2) and in Case 2 of Step 4.

3.5.3. Intervals of real numbers

The theorem’s first use is the question of the opening frame.

Example (The closed and the open unit interval)

Show that $\left| [0, 1] \right| = \left| (0, 1) \right|$ : first with Theorem 3.5.3, then by writing down a bijection.

Solution. With the theorem. The inclusion $(0, 1) \to [0, 1]$ is an injection. In the other direction let $u(x) \mathrel{:=} x/2 + 1/4$ for $x \in [0, 1]$ . If $0 \le x \le 1$ , then $1/4 \le u(x) \le 3/4$ , so $u(x) \in (0, 1)$ , and $u$ is a function $[0, 1] \to (0, 1)$ . It is injective: $x/2 + 1/4 = y/2 + 1/4$ gives $x = y$ . By Theorem 3.5.3, $\left| [0, 1] \right| = \left| (0, 1) \right|$ .

A bijection. The two extra points $0$ and $1$ are absorbed by a Hilbert’s hotel (Example (Hilbert’s Hotel)) run on the points $1, \frac12, \frac13, \dots$ . Define $\varphi \colon [0, 1] \to (0, 1)$ by $\varphi(x) \mathrel{:=} \begin{cases} \frac12 & \text{if } x = 0, \\ \frac{1}{n + 2} & \text{if } x = \frac1n \text{ for some } n \in \mathbb{Z}_{>0}, \\ x & \text{otherwise.} \end{cases}$ The cases do not overlap, since $\frac1n \ne 0$ , and in the second case $n = 1/x$ is determined by $x$ ; so $\varphi$ is a function, with values in $(0, 1)$ because $0 < \frac{1}{n + 2} \le \frac13$ . Let $H \mathrel{:=} \{0\} \cup \{ \frac1n : n \in \mathbb{Z}_{>0} \} = \{0, 1, \frac12, \frac13, \dots\}$ and $H' \mathrel{:=} \{ \frac1m : m \in \mathbb{Z}_{>0}, \ m \ge 2 \} = \{\frac12, \frac13, \frac14, \dots\}$ . Then $\varphi$ maps $H$ onto $H'$ : $0 \mapsto \frac12$ , and $\frac1n \mapsto \frac{1}{n + 2}$ runs through $\frac13, \frac14, \dots$ . It is injective on $H$ , since $\frac{1}{n + 2} = \frac{1}{n' + 2}$ forces $n = n'$ , and $\frac{1}{n + 2} \le \frac13 < \frac12$ . Off $H$ it is the identity of $[0, 1] \setminus H = (0, 1) \setminus H'$ . Since $[0, 1] = H \cup \bigl([0, 1] \setminus H\bigr), \qquad (0, 1) = H' \cup \bigl((0, 1) \setminus H'\bigr),$ both unions disjoint, $\varphi$ is a bijection, and $\left| [0, 1] \right| = \left| (0, 1) \right|$ . For instance $\varphi(1) = \frac13$ , $\varphi(\frac12) = \frac14$ , $\varphi(\frac34) = \frac34$ .

The first route took two lines and the second took a paragraph. That is the point of the theorem: we never had to find $\varphi$ .

The second interval computation turns an unbounded set into a bounded one.

Example (The real line and its intervals)

Show that $x \mapsto x/(1 + \left| x \right|)$ is a bijection $\mathbb{R} \to (-1, 1)$ . Deduce that every open interval $(c, d)$ with $c < d$ is equinumerous with $\mathbb{R}$ , and then that every interval with more than one point is.

Solution. The bijection. Let $s(x) \mathrel{:=} x/(1 + \left| x \right|)$ for $x \in \mathbb{R}$ ; the denominator is at least $1$ , so $s(x)$ is defined, and $\left| s(x) \right| = \left| x \right|/(1 + \left| x \right|) < 1$ , so $s(x) \in (-1, 1)$ . For $y \in (-1, 1)$ let $t(y) \mathrel{:=} y/(1 - \left| y \right|)$ ; here $1 - \left| y \right| > 0$ . We check that $t$ is a two-sided inverse. For $x \in \mathbb{R}$ , $\left| s(x) \right| = \left| x \right|/(1 + \left| x \right|)$ , so $1 - \left| s(x) \right| = \frac{1}{1 + \left| x \right|} , \qquad t(s(x)) = \frac{x}{1 + \left| x \right|} \cdot (1 + \left| x \right|) = x .$ For $y \in (-1, 1)$ , $\left| t(y) \right| = \left| y \right|/(1 - \left| y \right|)$ , so $1 + \left| t(y) \right| = \frac{1}{1 - \left| y \right|} , \qquad s(t(y)) = \frac{y}{1 - \left| y \right|} \cdot (1 - \left| y \right|) = y .$ By Theorem 1.5.4, $s$ is a bijection $\mathbb{R} \to (-1, 1)$ . For example $s(1) = \frac12$ and $s(-3) = -\frac34$ .

Open intervals. The map $y \mapsto (y + 1)/2$ is a bijection $(-1, 1) \to (0, 1)$ , with inverse $u \mapsto 2u - 1$ . For $c < d$ , the map $u \mapsto c + (d - c)u$ is a bijection $(0, 1) \to (c, d)$ , with inverse $v \mapsto (v - c)/(d - c)$ , since $d - c > 0$ . Composing the three bijections (Theorem 1.4.4 (c)) gives a bijection $\mathbb{R} \to (c, d)$ , so $\left| (c, d) \right| = \left| \mathbb{R} \right|$ .

Every interval with more than one point. Let $I$ be an interval (bounded or not, with or without its endpoints) containing two points $c < d$ . An interval contains every number between two of its points, so $(c, d) \subseteq I \subseteq \mathbb{R}$ . The inclusion is an injection $(c, d) \to I$ . In the other direction, let $\beta \colon \mathbb{R} \to (c, d)$ be the bijection just built; then $\beta$ restricted to $I$ is an injection $I \to (c, d)$ . By Theorem 3.5.3, $\left| I \right| = \left| (c, d) \right|$ , and $\left| (c, d) \right| = \left| \mathbb{R} \right|$ , so $\left| I \right| = \left| \mathbb{R} \right|$ by Proposition 3.1.1. This covers $[0, 1]$ , $[0, 1)$ , $(0, \infty)$ , $[5, \infty)$ and $\mathbb{R}$ itself at once.

In particular every interval with more than one point is uncountable: it is equinumerous with $\mathbb{R}$ , which is uncountable by Theorem 3.4.4, and a set equinumerous with a countable set is countable (compose a surjection from $\mathbb{N}$ with the bijection, Proposition 3.2.4).

Warning. Injections both ways do not make either injection a bijection. On $\mathbb{N}$ , $n \mapsto 2n$ is an injection $\mathbb{N} \to \mathbb{N}$ in both directions, and it is not onto: $1$ is never a value. Theorem 3.5.3 builds a new map $h$ out of $f$ and $g$ ; it says nothing about $f$ or $g$ themselves. In Example (The closed and the open unit interval), $u(x) = x/2 + 1/4$ misses $\frac{9}{10} \in (0, 1)$ , and the bijection is a different map.

Quick check. Give an injection $\mathbb{N} \to \mathbb{N} \times \mathbb{N}$ and an injection $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ . What does Theorem 3.5.3 conclude?

Solution. $n \mapsto (n, 1)$ is injective, by the characteristic property of pairs (Definition 1.3.1). $(m, n) \mapsto 2^m 3^n$ is injective, as shown in the proof of Theorem 3.2.6. So $\left| \mathbb{N} \right| = \left| \mathbb{N} \times \mathbb{N} \right|$ , and $\mathbb{N} \times \mathbb{N}$ is countably infinite (Definition 3.2.2). Section 3.2 showed only that $\mathbb{N} \times \mathbb{N}$ is countable; the theorem gives a bijection with $\mathbb{N}$ directly, with no listing at all.

3.5.4. Exercises

A. Check your understanding

Exercise (A1)

These parts are about the proof of Theorem 3.5.3.

(a) In Step 4, Case 2, why is $g(b) \notin C_0$ , and what would go wrong without it?
(b) Run the construction for $A = B = \mathbb{N}$ and $f(n) = g(n) = 2n$ . Compute $C_0$ , $C_1$ and $C$ , and the values $h(0), h(1), h(2), h(3), h(4)$ .
(c) Where is the injectivity of $f$ used?
(d) Give the idea of the proof in two sentences.

Solution.

(a) $C_0 = A \setminus g(B)$ consists of the points that are not values of $g$ , and $g(b)$ is a value of $g$ . Without it the index $n$ with $g(b) \in C_n$ could be $0$ , and then there would be no $C_{n-1}$ to find a predecessor $a$ in, so no $a \in C$ with $f(a) = b$ .
(b) $g(\mathbb{N}) = 2\mathbb{N}$ , so $C_0 = \mathbb{N} \setminus 2\mathbb{N}$ is the set of odd numbers. $C_1 = g(f(C_0)) = \{ 4q : q \text{ odd} \} = \{4, 12, 20, \dots\}$ . In general $C_{n+1} = \{ 4c : c \in C_n \}$ , so $C_n = \{ 4^n q : q \text{ odd} \}$ by induction on $n$ , and $C$ is the set of numbers $4^k q$ with $k \in \mathbb{N}$ and $q$ odd. Now:
- $0 \notin C$ , since $4^k q \ne 0$ for odd $q$ ( $4^k > 0$ and $q \ge 1$ ). So $h(0)$ is the $b$ with $2b = 0$ : $h(0) = 0$ , a fixed point.
- $1 \in C_0$ , so $h(1) = f(1) = 2$ .
- $2 \notin C$ : for $k = 0$ , $2$ is not odd; for $k \ge 1$ , $4^k q \ge 4 > 2$ . So $h(2)$ is the $b$ with $2b = 2$ : $h(2) = 1$ .
- $3 \in C_0$ , so $h(3) = 6$ .
- $4 = 4^1 \cdot 1 \in C_1$ , so $h(4) = f(4) = 8$ .
(c) In Step 3, Case 1: from $f(a) = f(a')$ with $a, a' \in C$ it concludes $a = a'$ .
(d) Points of $A$ that $g$ does not reach must be sent forward by $f$ , and so must everything reached from them by repeating $g \circ f$ ; this is the set $C$ . Every other point of $A$ is a value of $g$ and is sent back to its unique preimage, and the two halves fit together into a bijection.

B. Practice

Exercise (B1: Injections both ways)

Prove each of the following by giving an injection in each direction and applying Theorem 3.5.3.

(a) $\left| [0, 1] \right| = \left| \mathbb{R} \right|$ .
(b) $\left| \mathbb{N} \right| = \left| \mathbb{N} \times \mathbb{Z} \right|$ .
(c) $\left| (0, 1) \cup (2, 3) \right| = \left| (0, 1) \right|$ .

Solution.

(a) The inclusion $[0, 1] \to \mathbb{R}$ is injective. In the other direction, $x \mapsto \bigl(x/(1 + \left| x \right|) + 1\bigr)/2$ is a bijection $\mathbb{R} \to (0, 1)$ by Example (The real line and its intervals), so it is an injection $\mathbb{R} \to [0, 1]$ , as $(0, 1) \subseteq [0, 1]$ .
(b) $n \mapsto (n, 0)$ is an injection $\mathbb{N} \to \mathbb{N} \times \mathbb{Z}$ , by the characteristic property of pairs (Definition 1.3.1). In the other direction, let $j \colon \mathbb{Z} \to \mathbb{N}$ be $j(k) \mathrel{:=} 2k$ for $k \ge 0$ and $j(k) \mathrel{:=} -2k - 1$ for $k < 0$ . Its values are in $\mathbb{N}$ , even for $k \ge 0$ and odd for $k < 0$ ; since no natural number is both even and odd (Theorem 2.2.3, uniqueness), $j(k) = j(k')$ forces $k$ and $k'$ to have the same sign, and then $k = k'$ . So $j$ is injective, and so is $(m, k) \mapsto (m, j(k))$ . Following it by the injection $(m, n) \mapsto 2^m 3^n$ from the proof of Theorem 3.2.6 gives an injection $\mathbb{N} \times \mathbb{Z} \to \mathbb{N}$ (Theorem 1.4.4 (a)).
(c) The inclusion $(0, 1) \to (0, 1) \cup (2, 3)$ is injective. The map $x \mapsto x/4$ is injective and sends $(0, 1) \cup (2, 3)$ into $(0, \frac14) \cup (\frac12, \frac34) \subseteq (0, 1)$ .

Hence, by Theorem 3.5.3, the three equalities hold.

Exercise (B2: A proper subset of the same size)

Give an example of sets $A \subsetneq B \subseteq \mathbb{R}$ with $\left| A \right| = \left| B \right|$ , such that $A$ is uncountable and $B \setminus A$ is uncountable. Check each property, and list the properties any answer must have.

Solution. An answer must have: (1) $A \subseteq B \subseteq \mathbb{R}$ ; (2) $A \ne B$ ; (3) a bijection $A \to B$ , or injections both ways; (4) $A$ uncountable; (5) $B \setminus A$ uncountable. (Then $B$ is uncountable too, since it contains $A$ , by Proposition 3.2.3.)

Example: $A = (0, 1)$ , $B = (0, 3)$ . (1) and (2): $(0, 1) \subseteq (0, 3)$ and $2 \in B \setminus A$ . (3): $x \mapsto 3x$ is a bijection $(0, 1) \to (0, 3)$ , with inverse $y \mapsto y/3$ . (4) and (5): $A$ and $B \setminus A = [1, 3)$ are intervals with more than one point, hence equinumerous with $\mathbb{R}$ by Example (The real line and its intervals), hence uncountable, as shown after it.

Another correct answer: $A = (0, 1)$ , $B = \mathbb{R}$ , with $B \setminus A \supseteq (1, 2)$ uncountable. Any answer can be checked against (1)–(5).

Exercise (B3: Interleaving two sequences)

Prove that $\left| \{0, 1\}^{\mathbb{N}} \times \{0, 1\}^{\mathbb{N}} \right| = \left| \{0, 1\}^{\mathbb{N}} \right|$ by an explicit bijection.

Hint: put one sequence in the even places and the other in the odd places.

Solution. Every $m \in \mathbb{N}$ is $2n$ or $2n + 1$ for exactly one $n \in \mathbb{N}$ , and not both (Theorem 2.2.3 with divisor $2$ , the quotient in $\mathbb{N}$ , as in the proof of Proposition 3.2.5). So for $a, b \in \{0, 1\}^{\mathbb{N}}$ we may define $c = \Phi(a, b) \in \{0, 1\}^{\mathbb{N}}$ by $c(2n) \mathrel{:=} a(n), \qquad c(2n + 1) \mathrel{:=} b(n) \qquad (n \in \mathbb{N}).$ Define $\Psi \colon \{0, 1\}^{\mathbb{N}} \to \{0, 1\}^{\mathbb{N}} \times \{0, 1\}^{\mathbb{N}}$ by $\Psi(c) \mathrel{:=} (a, b)$ with $a(n) \mathrel{:=} c(2n)$ and $b(n) \mathrel{:=} c(2n + 1)$ . Then $\Psi(\Phi(a, b)) = (a, b)$ : its coordinates $n \mapsto c(2n) = a(n)$ and $n \mapsto c(2n + 1) = b(n)$ are $a$ and $b$ by Proposition 1.4.1, so the pairs are equal (Definition 1.3.1). And $\Phi(\Psi(c))$ agrees with $c$ at every even place $2n$ and every odd place $2n + 1$ , which are all the places, so $\Phi(\Psi(c)) = c$ (Proposition 1.4.1). By Theorem 1.5.4, $\Phi$ is a bijection.

C. Going deeper

Exercise (C1: The real line and the subsets of

\mathbb{N}

)

Prove that $\left| \mathbb{R} \right| = \left| \mathcal{P}\left( \mathbb{N} \right) \right|$ , using the decimal facts (D1)–(D3) of Section 3.4.

(a) For $x \in [0, 1)$ let $d_1 d_2 \ldots$ be its decimal expansion that does not end in all $9$ s, and let $E(x) \mathrel{:=} \{ 10k + d_k : k \in \mathbb{Z}_{>0} \}$ . Show that $E$ is a well-defined injection $[0, 1) \to \mathcal{P}\left( \mathbb{N} \right)$ .
(b) For $S \subseteq \mathbb{N}$ let $y_S$ be the number with decimal expansion $0.e_1 e_2 e_3 \ldots$ , where $e_{k+1} \mathrel{:=} 1$ if $k \in S$ and $e_{k+1} \mathrel{:=} 2$ if $k \notin S$ , for $k \in \mathbb{N}$ . Show that $S \mapsto y_S$ is a well-defined injection $\mathcal{P}\left( \mathbb{N} \right) \to [0, 1)$ .
(c) Conclude.

Solution (Hint 1). The tools are the decimal facts (D1)–(D3), and Theorem 2.2.3 with divisor $10$ for reading digits back out of $E(x)$ .

Solution (Hint 2). Begin (a) with: “By (D1), $x$ has an expansion that does not end in all $9$ s, and by (D3) it has only one.”

Solution.

(a) Well defined. By (D1), $x$ has an expansion not ending in all $9$ s. It has only one: if two different expansions of $x$ both failed to end in all $9$ s, (D3) would make one of them end in all $9$ s. So $d_1 d_2 \ldots$ is determined by $x$ , and $E(x) \subseteq \mathbb{N}$ because $10k + d_k \in \mathbb{N}$ .
Injective. By Theorem 2.2.3 with divisor $10$ , the number $10j + d_j$ , with $0 \le d_j \le 9$ , has quotient $j$ and remainder $d_j$ , and these are unique. So for each $k \ge 1$ , the only element of $E(x)$ with quotient $k$ is $10k + d_k$ , and $E(x)$ determines every digit $d_k$ . If $E(x) = E(x')$ , then $x$ and $x'$ have the same expansion $d_1 d_2 \ldots$ , and by the uniqueness half of (D2) a digit sequence is an expansion of exactly one number; so $x = x'$ .
(b) Well defined. By (D2), the digit sequence $e_1 e_2 \ldots$ is an expansion of exactly one $y_S \in [0, 1]$ . With $t_1 = e_1/10$ as in Definition 3.4.1, $y_S \le t_1 + \frac{1}{10} \le \frac{2}{10} + \frac{1}{10} = \frac{3}{10}$ , so $y_S \in [0, 1)$ .
Injective. Let $S \ne S'$ , say $k \in S \setminus S'$ or $k \in S' \setminus S$ . Then the two digit sequences differ at place $k + 1$ . Neither contains a $0$ or a $9$ , so neither ends in all $9$ s or in all $0$ s. If $y_S = y_{S'}$ , the number would have two different expansions, and by (D3) one would end in all $9$ s, which is false. So $y_S \ne y_{S'}$ . The index shift $e_{k+1}$ is there so that whether $0 \in S$ is recorded too, in the first digit.
(c) By (a), (b) and Theorem 3.5.3, $\left| [0, 1) \right| = \left| \mathcal{P}\left( \mathbb{N} \right) \right|$ . By Example (The real line and its intervals), $[0, 1)$ , an interval with more than one point, has $\left| [0, 1) \right| = \left| \mathbb{R} \right|$ . By Proposition 3.1.1, $\left| \mathbb{R} \right| = \left| \mathcal{P}\left( \mathbb{N} \right) \right|$ .

Marking scheme. (10 points) - 2: shows the expansion in (a) is unique, citing (D1) and (D3), so $E$ is a function. - 2: shows $E$ is injective: the set determines each digit, and one digit sequence names one number (D2). - 2: shows $y_S$ exists, is unique and lies in $[0, 1)$ . - 2: shows $S \mapsto y_S$ is injective, using that the digits avoid $0$ and $9$ and (D3). - 2: applies Theorem 3.5.3 and passes from $[0, 1)$ to $\mathbb{R}$ with a cited bijection or injections both ways. Fatal errors (0 for the step): treating “the expansion of $x$ ” as unique without (D1) and (D3); concluding $y_S \ne y_{S'}$ from different digit sequences without ruling out the $0.4999\ldots = 0.5$ case.

Exercise (C2: Find the error)

Here is a proof that $\left| [0, 1] \right| = \left| (0, 1) \right|$ .

Proof. (1) Let $u \colon [0, 1] \to (0, 1)$ , $u(x) \mathrel{:=} x/2 + 1/4$ . For $0 \le x \le 1$ we have $1/4 \le u(x) \le 3/4$ , so $u$ does map into $(0, 1)$ . (2) If $u(x) = u(y)$ , then $x/2 = y/2$ , so $x = y$ ; hence $u$ is injective. (3) The inclusion $\iota \colon (0, 1) \to [0, 1]$ is injective. (4) So there are injections in both directions between $[0, 1]$ and $(0, 1)$ . (5) Therefore $u$ is a bijection, and $\left| [0, 1] \right| = \left| (0, 1) \right|$ .

Is the conclusion true? Does the argument prove it? If not, name the line that fails, say why, and give a counterexample to the step it takes.

Solution. The conclusion is true: Example (The closed and the open unit interval) proves it twice.

The argument does not prove it. Lines (1)–(4) are correct. Line (5) fails: it infers that a particular injection is a bijection from the existence of injections both ways. The step cites a general “fact”, that injections both ways make a given injection a bijection. That fact is neither proved nor a school fact, and it is false, so the line cites nothing: entry (N9) of Logic and Proof, Example (What is not allowed). And $u$ is in fact not onto: $\frac{9}{10} \in (0, 1)$ is not a value, since every value lies in $[\frac14, \frac34]$ .

Counterexample to the step. Take $A = B = \mathbb{N}$ and $f = g = (n \mapsto 2n)$ . These are injections both ways, and the step would conclude that $n \mapsto 2n$ is a bijection $\mathbb{N} \to \mathbb{N}$ ; but $1$ is not a value.

Repair. Replace line (5) by: “By Theorem 3.5.3, $\left| [0, 1] \right| = \left| (0, 1) \right|$ .” The theorem produces a bijection, but a different one, built from both $u$ and $\iota$ .