A pictorial proof of the Schroeder-Bernstein Theorem

Today we shall look at an interesting pictorial proof of the Schroeder-Bernstein Theorem which states that if $A$ and $B$ are sets and $f:A \to B$ and $g:B \to A$ are injections then there exists a bijection $h:A\to B$ .

Note that this is roughly saying $\text{card} A \le \text{card} B$ and $\text{card} B \le \text{card} A$ , so the two sets must have the same cardinality (and indeed this would be a complete proof for the case where sets $A$ and $B$ are both finite).

The intuitive way to think about this proof is to picture the two sets $A$ and $B$ and imagine mapping parts of each set until they are completely matched up. Our key idea will be to split the sets $A$ and $B$ into a series of ‘rings’.

First, separate the disk $gfA$ from $A$ , which is the image of $A$ under the map $g \circ f$ . Now, the area inside $A$ but outside this disc splits into two regions — the set of points in $A$ that do not lie in the image of $g$ (call it $A_0$ ) and the points that do lie in the image of $g$ but do not lie in $fgA$ (call it $A_1$ ). Do the same for $B$ , as shown in the diagram below.

To see why this separation is helpful, look at the image of $A_0$ under $f$ . They lie in the image of $f$ but outside the disc $fgB$ since $A_0$ is disjoint from the image of $g$ . Hence, $f$ is a natural bijection from $A_0$ to $B_1$ . Similarly, $g$ is a natural bijection from $B_0$ to $A_1$ .

So what the separation is really doing is pairing up two pairs of regions in each of the sets $A$ and $B$ which are mapped to each other under a bijection, just as we planned.

Moreover, the image of $gfA$ under $f$ must clearly lie within the disc $fgB$ and vice versa because the codomain of $f$ is $B$ , and similarly for the other set. Hence, we can apply the same argument for these smaller discs.

To be precise, we look at $gfA$ instead of $A$ and look at $fgB$ instead of $B$ . Then, the next two rings in $A$ and $B$ are,

$A_2 = gfA \setminus gfgB \ \ \ \ \ \ \ A_3 = gfgB \setminus gfgfA$

and

$B_2 = fgB\setminus fgfA \ \ \ \ \ \ \ B_3 = fgfA \setminus fgfgB$ .

As before, $f$ maps $A_2$ to $B_3$ and $g$ maps $B_2$ to $A_3$ .

Moreover, the rings $A_i$ and $B_i$ are disjoint and we have a bijection $\phi: \bigcup A_i \to \bigcup B_i$ defined by

But the issue is that this itself is not enough. To see why, consider the degenerate case where $A\equiv B \equiv \mathbb Z$ and $f \equiv g \equiv \text{id}$ . Clearly $A$ and $B$ are non-empty, but none of their elements lie in either of the rings $A_i$ (why?) — they appear to exist in an infinitely deep ‘core’.

To deal with these elements, let $A_* = A \setminus (\bigcup A_i)$ and $B_* = B \setminus (\bigcup B_i)$ . Observe that $f$ bijects $A_*$ to $B_*$ precisely since these elements do not lie in any of the rings. Hence, we can extend $\phi$ to a bijection $h:A \to B$ defined by