The Cantor–Schröder–Bernstein Theorem

This appendix proves Theorem 7.72 of Logic, Sets, and Maps: two sets that inject into each other are equipotent. It is what makes the comparison of cardinals a genuine order relation rather than a pair of unrelated inequalities, and it is used immediately in Corollary A3.3 to identify the cardinal of the continuum with that of the power set of \(\N\). The proof is elementary but not obvious — neither injection need be surjective anywhere, and the bijection must be manufactured out of the two of them.

Theorem A3.1 (Cantor–Schröder–Bernstein).

Let \(X\) and \(Y\) be sets and let \(f:X\longrightarrow Y\) and \(g:Y\longrightarrow X\) be injective. Then there exists a bijection \(h:X\longrightarrow Y\). Rests on Definition 7.45 and Proposition 7.48.

Proof.

Derives Theorem A3.1. The obstruction to using \(g^{-1}\) as the bijection is the set of points of \(X\) outside the image of \(g\), where \(g^{-1}\) is undefined. Track where those points propagate under repeated application of \(g\circ f\), and use \(f\) there instead.

Define a sequence of subsets of \(X\) by

\begin{equation} \tag{A3.1} C_{0}:=X\setminus g(Y)\ec\qquad C_{n+1}:=g\bigl(f(C_{n})\bigr)\quad(n\geq0)\ec \end{equation}

and let

\begin{equation} \tag{A3.2} C:=\bigcup_{n\geq0}C_{n}\ep \end{equation}

Now define \(h:X\longrightarrow Y\) by

\begin{equation} \tag{A3.3} h(x):=\begin{cases} f(x) & \text{if } x\in C\ec\\ g^{-1}(x) & \text{if } x\notin C\ep \end{cases} \end{equation}

\(h\) is well defined. The only question is the second branch. If \(x\notin C\) then in particular \(x\notin C_{0}=X\setminus g(Y)\), so \(x\in g(Y)\); and since \(g\) is injective there is exactly one \(y\in Y\) with \(g(y)=x\). Write \(g^{-1}(x)\) for it.

\(h\) is injective. Each branch is injective on its own domain: \(f\) by hypothesis, and \(g^{-1}\) because \(g\) is a map. It remains to check that the two branches never collide, i.e. that

\begin{equation} \tag{A3.4} f(C)\cap g^{-1}(X\setminus C)=\varnothing\ep \end{equation}

Suppose not, and let \(f(c)=g^{-1}(x)\) with \(c\in C\) and \(x\notin C\). Applying \(g\) to both sides gives \(x=g(f(c))\). Since \(c\in C\), there is an \(n\) with \(c\in C_{n}\), whence

\[ x=g(f(c))\in g\bigl(f(C_{n})\bigr)=C_{n+1}\subset C\ec \]

contradicting \(x\notin C\). This proves Equation (A3.4), and with it the injectivity of \(h\).

\(h\) is surjective. Let \(y\in Y\) and consider the point \(g(y)\in X\). There are two cases, and they are exhaustive by Equation (7.25).

If \(g(y)\notin C\), then by the second branch of Equation (A3.3),

\[ h(g(y))=g^{-1}(g(y))=y\ec \]

so \(y\) is attained.

If \(g(y)\in C\), then \(g(y)\in C_{n}\) for some \(n\). That \(n\) cannot be \(0\), because \(g(y)\) lies in \(g(Y)\) while \(C_{0}=X\setminus g(Y)\) does not meet \(g(Y)\). So \(n=m+1\) for some \(m\geq0\) and \(g(y)\in C_{m+1}=g(f(C_{m}))\), i.e. \(g(y)=g(f(c))\) for some \(c\in C_{m}\). Injectivity of \(g\) gives \(y=f(c)\), and since \(c\in C_{m}\subset C\) the first branch of Equation (A3.3) yields \(h(c)=f(c)=y\). Again \(y\) is attained.

Being injective and surjective, \(h\) is a bijection by Proposition 7.48.

∎

Remark A3.2 (No choice is used).

The construction Equations (A3.1), (A3.2) and (A3.3) is explicit: given \(f\) and \(g\), the bijection \(h\) is determined, with no appeal to Axiom 7.78. This matters, because the companion statement that any two cardinals are comparable — that at least one of the two injections always exists — is equivalent to the axiom of choice. CSB says that comparability, where it holds, is antisymmetric; it does not say that any two sets are comparable.

Corollary A3.3 (The continuum is the power set of the naturals).

\(\abs{\R}=\abs{\mathcal{P}(\N)}\), that is \(\mathfrak{c}=2^{\aleph_{0}}\). Rests on Theorem A3.1 and Corollary 7.68.

Proof.

Derives Corollary A3.3. We exhibit injections in both directions and invoke Theorem A3.1.

An injection \(\mathcal{P}(\N)\longrightarrow\R\). Send \(A\subset\N\) to the real number whose base-\(3\) expansion has digit \(1\) at place \(n\) when \(n\in A\) and digit \(0\) otherwise,

\begin{equation} \tag{A3.5} \Phi(A):=\sum_{n\in A}3^{-n}\ep \end{equation}

If \(A\neq B\), let \(k\) be the least element of their symmetric difference, say \(k\in A\setminus B\). Then

\[ \Phi(A)-\Phi(B)\geq3^{-k}-\sum_{n>k}3^{-n} =3^{-k}-\frac{3^{-k}}{2}=\frac{3^{-k}}{2}>0\ec \]

since the digits omitted from \(B\) beyond place \(k\) contribute at most the full geometric tail. Hence \(\Phi(A)\neq\Phi(B)\) and \(\Phi\) is injective. Using digits \(0\) and \(1\) in base \(3\) — rather than base \(2\) — is exactly what makes the tail strictly smaller than the leading term, so that the two expansions cannot coincide.

An injection \(\R\longrightarrow\mathcal{P}(\N)\). Send \(x\in\R\) to its Dedekind cut \(\Psi(x):=\set{q\in\Q\mid q<x}\), injective because \(\Q\) is dense in \(\R\): if \(x<y\) there is a rational strictly between them, lying in \(\Psi(y)\) but not in \(\Psi(x)\). This lands in \(\mathcal{P}(\Q)\) rather than \(\mathcal{P}(\N)\), but \(\abs{\Q}=\aleph_{0}\) by Corollary 7.68, and a bijection \(\N\longrightarrow\Q\) induces a bijection \(\mathcal{P}(\Q)\longrightarrow\mathcal{P}(\N)\) by taking preimages. Composing gives the required injection.

∎

The Cantor–Schröder–Bernstein Theorem discharges the proof obligation of Theorem 7.72, and Corollary A3.3 supplies the identification \(\mathfrak{c}=2^{\aleph_{0}}\) used in Section 7.5.3 when the continuum hypothesis is stated. The next appendix treats the other half of the foundational material of that chapter.