Sets, topology and continuity

Part 2, from an injection to a surjection. Let $f : X \to Y$ be injective. Since $X$ is nonempty, fix some $x_* \in X$ and define $g : Y \to X$ by: $g(y)$ is the unique $x$ with $f(x) = y$ when $y \in f(X)$, and $g(y) = x_*$ otherwise. The first clause is unambiguous precisely because $f$ is injective. Given any $x \in X$, the element $y = f(x)$ has $g(y) = x$, so $g$ is surjective.

Part 2, from a surjection to an injection. Let $g : Y \to X$ be surjective. For each $x \in X$ the fibre $g^{-1}(\{x\})$ is nonempty, by surjectivity, and distinct fibres are disjoint. Choose one element $f(x) \in g^{-1}(\{x\})$ for every $x \in X$ at once; this is an appeal to the axiom of choice (see the remark). Then $g(f(x)) = x$ for all $x$, so $f(x_1) = f(x_2)$ gives $x_1 = g(f(x_1)) = g(f(x_2)) = x_2$ and $f$ is injective. The two halves together say $\operatorname{card}(X) \le \operatorname{card}(Y)$ if and only if $\operatorname{card}(Y) \ge \operatorname{card}(X)$.

Part 1 (Schröder-Bernstein). Let $f : X \to Y$ and $g : Y \to X$ be injections.

Step 1 (backward chains). Call $y$ the predecessor of $x \in X$ if $x = g(y)$, and $x$ the predecessor of $y \in Y$ if $y = f(x)$. A point of $X$ has a predecessor exactly when it lies in $g(Y)$, a point of $Y$ exactly when it lies in $f(X)$, and in both cases the predecessor is unique because $g$ and $f$ are injective. Starting from any point and passing to predecessors as long as they exist therefore produces one well-defined chain, alternating between the two sets.

Step 2 (three types). The chain of a point does exactly one of three things: it continues for ever; it halts at a point of $X \setminus g(Y)$; it halts at a point of $Y \setminus f(X)$. Let $X_\infty$, $X_X$, $X_Y$ be the sets of $x \in X$ of the three types, and $Y_\infty$, $Y_X$, $Y_Y$ likewise for $Y$. Since every point has one chain with one behaviour, $X$ is the disjoint union of $X_\infty$, $X_X$, $X_Y$, and $Y$ of $Y_\infty$, $Y_X$, $Y_Y$; some pieces may be empty.

Step 3 (both maps preserve the type). Let $x \in X$. Then $f(x) \in f(X)$, so $f(x)$ has a predecessor, and that predecessor is $x$; the chain of $f(x)$ is thus $f(x)$ followed by the chain of $x$. Prefixing one term changes neither whether a chain halts nor where, so $f(x)$ has the same type as $x$:

and by the identical argument $g(y)$ has the same type as $y$ for every $y \in Y$.

Step 4 ($f$ exhausts the first two pieces of $Y$). Let $y \in Y_\infty \cup Y_X$. Its chain does not halt at $y$ itself: halting at $y$ would mean $y \notin f(X)$, which puts $y$ in $Y_Y$. So $y \in f(X)$, and $x = f^{-1}(y)$ has the same type as $y$ by Step 3. Hence $f$ maps $X_\infty$ onto $Y_\infty$ and $X_X$ onto $Y_X$, and being injective it is a bijection in each case.

Step 5 ($g$ exhausts the third piece of $X$). Let $x \in X_Y$. Its chain does not halt at $x$ itself, since that would mean $x \notin g(Y)$ and put $x$ in $X_X$. So $x \in g(Y)$, and $y = g^{-1}(x)$ has the same type as $x$, namely type $Y_Y$. Conversely $g(Y_Y) \subseteq X_Y$ by Step 3. So $g$ restricts to a bijection $Y_Y \to X_Y$, and $g^{-1}$ to a bijection $X_Y \to Y_Y$.

Step 6 (glue). Define $h : X \to Y$ by $h = f$ on $X_\infty \cup X_X$ and $h = g^{-1}$ on $X_Y$. The three pieces partition $X$, the three sets $Y_\infty$, $Y_X$, $Y_Y$ partition $Y$, and $h$ is a bijection from each piece onto the corresponding one by Steps 4 and 5. A map that carries each block of one partition bijectively onto a block of another, with distinct blocks going to distinct blocks, is itself a bijection. Hence $\operatorname{card}(X) = \operatorname{card}(Y)$. $\square$

Step 1 ($Y$ is not a value of $g$). Suppose $Y = g(x_0)$ for some $x_0 \in X$, and ask whether $x_0 \in Y$. Exactly one of the two answers must hold, and both are impossible:

• if $x_0 \in Y$, then by the definition of $Y$ we have $x_0 \notin g(x_0)$, and $g(x_0) = Y$, so $x_0 \notin Y$;
• if $x_0 \notin Y = g(x_0)$, then $x_0$ satisfies the condition defining $Y$, so $x_0 \in Y$.

Hence no such $x_0$ exists: $Y \notin g(X)$, and $g$ is not surjective. No hypothesis on $X$ or on $g$ entered this step.

Step 2 (the injection). The map $x \mapsto \{x\}$ from $X$ to $\mathcal{P}(X)$ is injective, since $\{x_1\} = \{x_2\}$ forces $x_1 = x_2$. So $\operatorname{card}(X) \le \operatorname{card}(\mathcal{P}(X))$ for nonempty $X$; note $\mathcal{P}(X)$ is never empty, containing $\emptyset$.

Step 3 (no bijection). A bijection $X \to \mathcal{P}(X)$ would in particular be a surjection, which Step 1 forbids. An injection exists and no bijection does, which is the definition of $\operatorname{card}(X) < \operatorname{card}(\mathcal{P}(X))$. $\square$

Item 1 (products).

Step 1 ($\mathbb{N}^2$ is countable). Group the pairs by the value of $n = j+k$, which runs over the integers $n \ge 2$, and inside the $n$-th group list the $n-1$ pairs with $j+k = n$ in order of increasing $j$:

Each pair appears exactly once, namely in the group $n = j+k$ at position $j$ within it, so the listing is a bijection $\mathbb{N} \to \mathbb{N}^2$ and its inverse a bijection $\mathbb{N}^2 \to \mathbb{N}$. In closed form the inverse sends $(j,k)$ to $\tfrac12(j+k-1)(j+k-2) + j$, the first term being $1 + 2 + \dots + (j+k-2)$, the number of pairs in all earlier groups.

Step 2 (general $X$, $Y$). If $X$ or $Y$ is empty then $X \times Y = \emptyset$, which is countable. Otherwise choose injections $u : X \to \mathbb{N}$ and $v : Y \to \mathbb{N}$, which exist because $X$ and $Y$ are countable. Then $(x,y) \mapsto (u(x), v(y))$ is an injection $X \times Y \to \mathbb{N}^2$, being injective in each slot, and composing it with the bijection of Step 1 gives an injection $X \times Y \to \mathbb{N}$.

Item 2 (indexed unions). Write $U = \bigcup_{\alpha \in A}X_\alpha$. Deleting the indices $\alpha$ with $X_\alpha = \emptyset$ changes neither $U$ nor the countability of the index set, a subset of a countable set being countable because the restriction of an injection is an injection. If every $X_\alpha$ was empty then $U = \emptyset$ is countable; so assume the remaining index set, still called $A$, is nonempty and every $X_\alpha$ is nonempty.

Step 1 (one enumeration per piece). Each $X_\alpha$ is nonempty and countable, so by part 2 of the previous statement there is a surjection $\mathbb{N} \to X_\alpha$. Choose one, $f_\alpha$, for every $\alpha \in A$ simultaneously; this is the axiom of choice again (see the remark).

Step 2 (one surjection onto the union). Define $F : \mathbb{N}\times A \to U$ by $F(n,\alpha) = f_\alpha(n)$. It is surjective: any $u \in U$ lies in some $X_\alpha$, and $f_\alpha$ is onto $X_\alpha$, so $u = f_\alpha(n)$ for some $n$.

Step 3 (transfer). $\mathbb{N} \times A$ is countable by item 1. By part 2 of the previous statement the surjection $F$ yields an injection $U \to \mathbb{N}\times A$, and composing it with an injection $\mathbb{N}\times A \to \mathbb{N}$ gives an injection $U \to \mathbb{N}$. So $U$ is countable.

Item 3 (countable and infinite means in bijection with $\mathbb{N}$).

Step 1 (reduce to a subset of $\mathbb{N}$). Let $X$ be countable and infinite and let $u : X \to \mathbb{N}$ be an injection. Then $u$ is a bijection of $X$ onto $S = u(X) \subseteq \mathbb{N}$, and $S$ is infinite because $X$ is. If $\varphi : \mathbb{N} \to S$ is a bijection then $\varphi^{-1}\circ u : X \to \mathbb{N}$ is one, so it is enough to enumerate $S$.

Step 2 (take least elements). Set $\varphi(1) = \min S$ and recursively $\varphi(n) = \min\bigl(S \setminus \{\varphi(1),\dots,\varphi(n-1)\}\bigr)$. Each set whose minimum is taken is a nonempty subset of $\mathbb{N}$ — nonempty because $S$ is infinite while the removed set is finite — and every nonempty subset of $\mathbb{N}$ has a least element, so $\varphi$ is well defined.

Step 3 ($\varphi$ is strictly increasing). By construction $\varphi(n)$ differs from $\varphi(1),\dots,\varphi(n-1)$. Moreover $\varphi(n) > \varphi(n-1)$: both belong to $S \setminus \{\varphi(1),\dots,\varphi(n-2)\}$, of which $\varphi(n-1)$ is the least element and from which $\varphi(n)$ differs. An induction now shows that $\varphi(n)$ is the $n$-th smallest element of $S$.

Step 4 ($\varphi$ is onto). Let $s \in S$ and let $m$ be the number of elements of $S$ that are $\le s$; this is finite, there being at most $s$ positive integers $\le s$. Then $s$ is the $m$-th smallest element of $S$, hence $s = \varphi(m)$ by Step 3. So $\varphi$ is a bijection and $\operatorname{card}(X) = \operatorname{card}(\mathbb{N})$. Steps 2 to 4 alone are the special case of an infinite $S \subseteq \mathbb{N}$.

Item 4 (the usual number systems). $\mathbb{Z} = \mathbb{N}\cup\{-n : n \in \mathbb{N}\}\cup\{0\}$ is a union of three countable sets over the index set $\{1,2,3\}$, which is finite and hence countable, so $\mathbb{Z}$ is countable by item 2. Then $\mathbb{Z}\times\mathbb{Z}$ is countable by item 1, and

is a surjection $\mathbb{Z}^2 \to \mathbb{Q}$, because every rational is a quotient of two integers with nonzero denominator. Step 3 of item 2 transfers countability along a surjection, so $\mathbb{Q}$ is countable. Both are infinite, containing $\mathbb{N}$, so by item 3 both are in bijection with $\mathbb{N}$.

Item 5 ($\operatorname{card}(\mathcal{P}(\mathbb{N})) = \mathfrak{c}$).

Step 1 (an injection $\mathcal{P}(\mathbb{N}) \to \mathbb{R}$). For $A \subseteq \mathbb{N}$ put $s(A) = \sum_{n \in A}2^{-n}$, a subseries of $\sum_{n\ge 1}2^{-n} = 1$ and so convergent with $0 \le s(A) \le 1$. Following Folland (p. 8), define

Values of the first kind lie in $[0,1]$ and values of the second in $(1,2]$, since a set with finite complement is nonempty and so has $s(A) > 0$. So two sets falling under different cases get different values.

Step 2 (injectivity within a case). Let $A \neq B$ fall under the same case and let $m$ be the least element of $A \triangle B$, say $m \in A \setminus B$. Then $A$ and $B$ agree on $\{1,\dots,m-1\}$, so

using $\sum_{n>m}2^{-n} = 2^{-m}$. Equality would force the subtracted sum to be all of $\sum_{n>m}2^{-n}$ and the added one to vanish, that is, every $n > m$ to lie in $B$ and none in $A$. Then $A \subseteq \{1,\dots,m\}$ has infinite complement while $\mathbb{N}\setminus B \subseteq \{1,\dots,m\}$ is finite, putting $A$ and $B$ under different cases, against the assumption. So $s(A) \neq s(B)$, hence $\Phi(A) \neq \Phi(B)$, and with Step 1, $\Phi$ is injective: $\operatorname{card}(\mathcal{P}(\mathbb{N})) \le \operatorname{card}(\mathbb{R})$.

Step 3 (an injection $\mathbb{R} \to \mathcal{P}(\mathbb{Q})$). Send $x$ to $C_x = \{q \in \mathbb{Q} : q < x\}$. If $x < y$, some rational lies strictly between them and belongs to $C_y$ but not to $C_x$, so $C_x \neq C_y$: the map is injective.

Step 4 (powers sets of countably infinite sets). $\mathbb{Q}$ is countable and infinite, so item 3 gives a bijection $\psi : \mathbb{Q}\to\mathbb{N}$. Then $A \mapsto \psi(A)$ is a bijection $\mathcal{P}(\mathbb{Q}) \to \mathcal{P}(\mathbb{N})$, its inverse being $B \mapsto \psi^{-1}(B)$. With Step 3 this gives $\operatorname{card}(\mathbb{R}) \le \operatorname{card}(\mathcal{P}(\mathbb{N}))$.

Step 5 (conclude). Injections run both ways between $\mathcal{P}(\mathbb{N})$ and $\mathbb{R}$, so Schröder-Bernstein gives $\operatorname{card}(\mathcal{P}(\mathbb{N})) = \operatorname{card}(\mathbb{R}) = \mathfrak{c}$. Cantor's theorem then supplies $\operatorname{card}(\mathbb{N}) < \operatorname{card}(\mathcal{P}(\mathbb{N})) = \mathfrak{c}$. Were $\mathbb{R}$ countable we would have $\operatorname{card}(\mathbb{R}) \le \operatorname{card}(\mathbb{N})$, and with $\operatorname{card}(\mathbb{N})\le\operatorname{card}(\mathbb{R})$ from the inclusion $\mathbb{N}\subseteq\mathbb{R}$, Schröder-Bernstein would make $\operatorname{card}(\mathcal{P}(\mathbb{N})) = \operatorname{card}(\mathbb{N})$, which Cantor's theorem forbids. So $\mathbb{R}$ is uncountable. For the second injection Folland instead builds a surjection $\mathcal{P}(\mathbb{Z}) \to \mathbb{R}$ out of binary expansions; Steps 3 and 4 replace that by an injection, which spares us having to decide which expansions occur.

Item 6 (beyond the continuum). Assume $\operatorname{card}(X) > \mathfrak{c}$, so some surjection $X \to \mathbb{R}$ exists. Suppose $X$ were countable, that is, an injection $X \to \mathbb{N}$ exists. Part 2 of the earlier statement converts the surjection $X \to \mathbb{R}$ into an injection $\mathbb{R}\to X$, which composed with the injection $X \to \mathbb{N}$ gives $\operatorname{card}(\mathbb{R}) \le \operatorname{card}(\mathbb{N})$. Together with $\operatorname{card}(\mathbb{N})\le\operatorname{card}(\mathbb{R})$ and Schröder-Bernstein that makes $\operatorname{card}(\mathbb{R}) = \operatorname{card}(\mathbb{N})$, contradicting item 5 and Cantor's theorem. So $X$ is uncountable. $\square$