Cantor-Bernstein Theorem (with an Explicit Bijection!)

Cantor-Bernstein 定理（给出双射！） 苏剑林 · 2014-09-19 · Mathematics infinity function set construction

Anyone who has studied set theory will know that, by definition, the most direct way to show that two sets have the same "cardinality" is to give an explicit bijection between them. However, such bijections are often far from obvious. For instance:

Give a bijection from $[0,+\infty)$ to $(0,+\infty)$.

Intuitively, these two sets should obviously have the same cardinality, and there are infinitely many bijections between them. Yet most of us find it hard to actually come up with one. When we finally see a constructed bijection, our first reaction is usually: how on earth did anyone think of this?! For example, one answer to the above question is: more

$$h(x)=\left\{\begin{aligned}&x^2+1,\quad x=0,1,2,5,26,677,\dots\\ > &x,\quad x\in[0,+\infty)\text{and}x\neq 0,1,5,26,\dots\end{aligned}\right.$$

where each term of the sequence $0,1,2,5,26,677,\dots$ is the square of the previous term plus 1. A bijection constructed like this can't help but leave us in awe!

An intuitive analysis

How can we construct such a bijection? The idea is actually quite beautiful. First, suppose the sets $A$ and $B$ have the same cardinality. Although it's hard to directly write down a bijection $A\mapsto B$, it is usually easy to give an injection $f$ from $A\mapsto B$ — that is, a bijection from $A$ to some subset of $B$. Likewise, we can easily give an injection $g$ from $B\mapsto A$. A very "economical" idea then arises: can we "patch together" a bijection of $A\mapsto B$ using $f$ and $g^{-1}$?

The answer is yes, and this is exactly the content of what we call the "Cantor-Bernstein theorem"! Below we give a brief sketch of the idea behind it.

Step One: First consider the bijection $g$ of $B\mapsto A$; the range of $g$ is $g(B)$, which means that the domain of $g^{-1}$ can be at most $g(B)$. Thus, in the bijection $A\mapsto B$ we are constructing, the part corresponding to $A-g(B)$ can only be defined by $f$. Denote this as $C_0=A-g(B)$.

Step Two: If $C_0=\emptyset$, then the bijection can be defined by $g^{-1}$ alone. If $C_0\neq\emptyset$, then the part $C_0$ must be defined by $f$. But this does not mean the remaining part can simply be defined by $g^{-1}$. Because the remaining part (namely $g(B)$) can be mapped by $g^{-1}$ onto the whole of $B$, and $f$ in turn maps $C_0$ to only part of $B$ — so what we'd construct this way would not be a bijection.

Step Three: To resolve the difficulty in Step Two, the only option is to slightly enlarge the domain of $f$ and correspondingly shrink the domain of $g^{-1}$. Since the part $C_0$ must already be defined by $f$, the only thing we can change is to enlarge the domain of $f$. The image (range) of $C_0$ under $B$ is $f(C_0)$, and we must not let the image of $g^{-1}$ overlap with it (the image of $g^{-1}$ is the domain of $g$, and the domain of $g^{-1}$ is the image of $g$). So we need to remove the part $g(f(C_0))=C_1$ from the domain of $g^{-1}$ (i.e., from the image $g(B)$ of $g$). Once this is removed, $g^{-1}(x)$ can no longer belong to $f(C_0)$;

Step Four: But now, having removed the influence of $C_0$, we've introduced a new issue with $C_1$, and we must use the same trick to remove the influence of $C_1$ — which will inevitably introduce the influence of $C_2=g(f(C_1))$... and so on, ad infinitum. Once we've removed all of these infinitely many effects, what remains is a proper bijection.

Expressed in mathematical language:

$$h(x)=\left\{\begin{aligned}&f(x),\quad x\in C\\ &g^{-1}(x),\quad x\in A-C\end{aligned}\right.$$

where $C=\bigcup\limits_{n=0}^{\infty} C_n,\quad C_{n+1}=g(f(C_n))$.

It can be proved that this is indeed a bijection of $A\mapsto B$. We won't reproduce the full proof here — readers can consult the Wikipedia entry "Cantor–Bernstein–Schröder theorem".

A worked example

Let's now see how to construct a bijection from $[0,+\infty)$ to $(0,+\infty)$. Let

$$\left\{\begin{aligned}&f(x)=x^2+1,\quad x\in [0,+\infty)\\ &g(x)=x,\quad x\in (0,+\infty) \end{aligned}\right.$$

where $f,g$ are injections from $[0,+\infty)\mapsto (0,+\infty)$ and $(0,+\infty)\mapsto [0,+\infty)$ respectively, and $g^{-1}(x)=x$. We can then compute:

$$\begin{aligned}&C_0=[0,+\infty)-(0,+\infty)=\{0\}\\ &C_1=g(f(C_0))=\{1\}\\ &C_2=g(g(C_1))=\{2\}\\ &\dots \end{aligned}$$

so that

$$C=\bigcup\limits_{n=0}^{\infty} C_n=\{0,1,2,5,26,677,\dots\}$$

and hence we obtain the bijection

$$h(x)=\left\{\begin{aligned}&x^2+1,\quad x=0,1,2,5,26,677,\dots\\ &x,\quad x\in[0,+\infty)\text{and}x\neq 0,1,5,26,\dots\end{aligned}\right.$$