Subsection 12.5.1 The Cantor-Schröder-Bernstein theorem
Theorem 12.5.1. Cantor-Schröder-Bernstein (and also Dedekind).
Let
\(A,B\) be sets. If there is an injection
\(f:A \to B\) and an injection
\(g:B \to A\text{,}\) then there is a bijection
\(h: A \to B\text{.}\) Equivalently, if
\(|A|\leq |B|\) and
\(|B| \leq |A|\) then
\(|A| = |B|\text{.}\)
The proof is by no means trivial; we have some work to do. First up — let us assume that we have those injections
\(f:A \to B\) and
\(g:B \to A\text{.}\)
We can think of \(f\) injecting a copy of \(A\) into \(B\) — namely \(f(A)\text{.}\) It is not hard to show that by restricting the codomain we can build a function
\begin{align*}
\hat{f}:A \to f(A) && \text{defined by } \hat{f}(a) = f(a)
\end{align*}
is a bijection. So that looks like a good place to start making our bijection from \(A\) to \(B\text{.}\) We can similarly restrict the codomain of \(g\) to construct
\begin{align*}
\hat{g}:B \to g(B) && \text{defined by } \hat{g}(b) = g(b)
\end{align*}
Since this is also a bijection, its inverse is a bijection — giving us another bijection
\begin{gather*}
\hat{g}^{-1}: g(B) \to B
\end{gather*}
This should give us some hope because by restricting codomains we have
-
a bijection, \(\hat{f}\text{,}\) from all of \(A\) to some (but not all) of \(B\text{,}\) and
-
a bijection, \(\hat{g}^{-1}\) from some (but not all) of \(A\) to all of \(B\text{.}\)
So perhaps we can build a bijection from all of \(A\) to all of \(B\) by carefully choosing between these two depending on our input.
To investigate things a bit further, we should think about what happens when we compose \(f\) and \(g\text{.}\) Let \(x \in A\) and consider the image of \(x\) under \(f\) — we get some element \(f(x) \in B\text{.}\) We cannot do much with this, but we can apply \(g\) to it, giving us \(g(f(x))\text{.}\) This, in turn, is some element of \(A\text{,}\) so we can apply \(f\) to it, etc etc. In this way, we can think of the trajectory of \(x\) under these two injections.
\begin{gather*}
x \mapsto f(x) \mapsto g(f(x)) \mapsto f(g(f(x))) \mapsto \cdots
\end{gather*}
What we have here is the forward trajectory of \(x\) under \(f\) and \(g\text{.}\)
But we could also go backwards. For any
\(x \in A\text{,}\) we can compute the preimage of
\(g^{-1}(\set{x})\text{.}\) Since
\(g\) is injective, we know that that this set is either empty or contains precisely 1 element (otherwise
\(g\) would fail to be injective). We can make a similar argument about any
\(y \in B\text{,}\) its preimage
\(f^{-1}(\set{y})\) is either empty or contains exactly 1 element. Hence we can extend this trajectory backwards via unique preimages — unless we get stuck at an element whose preimage is empty.
Each element has a unique forward step along its path by applying
\(f\) or
\(g\) as appropriate. Similarly, when we step back along the trajectory, we move to a unique element (due to injectivity) by application of
\(f^{-1}\) or
\(g^{-1}\text{,}\) or the preimage is empty and cannot move any further back. So two trajectories cannot merge, nor can a trajectory branch:
Because of this, the trajectory of any point \(x\) can be of 4 types:
-
the trajectory forms an infinite line
-
the trajectory is a loop
-
the trajectory goes forward forever, but going backwards we get stuck at an element of \(A\text{,}\) or
-
the trajectory goes forward forever, but going backwards we get stuck at an element of \(B\text{.}\)
We cannot have more complicated shapes. Let us call the first three types “good” and the last type — that gets stuck at
\(B\) — “bad”.
Now, define a function \(h: A \to B\) by
\begin{align*}
h(x) &=
\begin{cases}
f(x) & \text{ if the trajectory of \(x\) is good, and}\\
g^{-1}(x) & \text{ if the trajectory of \(x\) is bad.}
\end{cases}
\end{align*}
To see that this is actually function — take any element of \(a \in A\text{.}\) We can always form \(f(a)\text{,}\) since \(f\) is a function. If \(a\) lies on a bad trajectory, then we know we can go backwards until we get stuck at some element of \(B\) — thus the preimage of \(g^{-1}(a)\) must contain exactly 1 element — which we take to be \(h(a)\text{.}\)
Oof. Now we “just” have to prove this is a bijection.
\(h\) is a surjection.
Let \(b \in B\text{.}\) Examine the trajectory on which \(b\) lies — it is either “good” or “bad”.
-
If \(b\) lies on a good trajectory, then (by moving back one step along the trajectory) there is some \(x \in A\) so that \(f(x)=y\text{.}\) This \(x\) must also lie on a good trajectory and so \(h(x) = f(x) = y\text{.}\)
-
If \(b\) lies on a bad trajectory, then (by moving forward one step along the trajectory) we set \(x=g(b)\text{.}\) We know that \(x\) also lies on a bad trajectory, so \(h(x)= g^{-1}(x) = g^{-1}(g(y))= y\text{.}\)
In either case, by moving forward or backward one step along the trajectory of \(y\) we find an \(x \in A\) so that \(h(x)=y\text{.}\)
\(h\) is an injection.
Let \(a,c \in A\text{,}\) and assume that \(h(a)=h(c)\text{.}\) Notice that by construction, \(h(x)\) lies on the same trajectory as \(x\text{.}\) Thus \(a,c,h(a)\) and \(h(c)\) must all lie on the same trajectory. That trajectory is either good or bad.
-
If the trajectory is good, then \(h(a)=f(a)\) and \(h(c)=f(c)\) and so \(f(a)=f(c)\text{.}\) Since \(f\) is an injection, we know that \(a=c\text{.}\)
-
If the trajectory is bad then \(h(a)=g^{-1}(a)\) and \(h(c)=g^{-1}(c)\text{.}\) So \(g^{-1}(a)=g^{-1}(c)\) — since \(g\) is an injection, that preimage contains exactly one element, so we must have \(a=c\text{.}\)
In either case, we have that \(a=c\text{.}\)
