Cantor-Schröder-Bernstein theorem

Written by Patrick Stevens last updated

Summaries

Recall that we say a set is smaller than or equal to a set if there is an injection from to . The set has the same size as if there is a bijection between and .

The Cantor-Schröder-Bernstein theorem states that if is smaller than or equal to , and is smaller than or equal to , then and have the same size. This tells us that the arithmetic of cardinals is well-behaved in that it behaves like a total order. It is similar to the arithmetic of the natural numbers in that it can never be the case that simultaneously and .

Proofs

There are several proofs, some concrete and some less so.

Concrete proof

A clear explanation of the intuition of this proof has been written by Richard Evan Schwartz; see page 61 of the linked PDF, or search on the word "dog" (which appears in the first page of the explanation).

Let and be injections; we will define a bijective function .

Because is injective, if ever hits (that is, if there is such that ) then it is possible to define to be the unique such that ; similarly with . The slogan is "if exists, then it is well-defined: there is no leeway about which element we might choose to be ".

Fix some , and consider the sequence Now, this sequence might not extend infinitely to the left; it may not even get past to the left (if doesn't exist, for instance). [1] Also, the sequence might duplicate elements: it might be the case that , for instance. [2]

Similarly, we can fix some , and consider

Every element of , and every element of , appears in one of these chains. Moreover, if appears in two different chains, then in fact the two chains are the same [3], because each element of the chain specifies and is specified by the previous element in the chain (if it exists) and each element of the chain specifies and is specified by the next element of the chain.

So every element of and every element of is in exactly one chain. Now, it turns out that there are exactly four distinct "types" of chain.

  • It could extend infinitely in both directions without repeats. In this case, we define for each element of in the chain. (Basically assigning to each element of the element of which is next in the chain.)
  • It could extend infinitely off to the right, but it has a hard barrier at the left, and has no repeats: the chain stops at an element of . In this case, again we define for each element of in the chain. (Again, basically assigning to each element of the element of which is next in the chain.)
  • It could extend infinitely off to the right, but it has a hard barrier at the left, and has no repeats: the chain stops at an element of . In this case, we define for each element of in the chain. (Basically assigning to each element of the element of which is previous in the chain.)
  • It could have repeats. Then it must actually be a cycle of even length (unrolled into an infinite line), because each element of the chain only depends on the one before it, and because we can't have two successive elements of (since the elements are alternating between and ). In this case, we define for each element of in the chain. (Basically assigning to each element of the element of which is next in the chain.)

Have we actually made a bijection? Certainly our function is well-defined: every element of appears in exactly one chain, and we've specified where every element of in any chain goes, so we've specified where every element of goes.

Our function is surjective, because every element of is in a chain; if has an element of before it in its chain, then we specified that takes to , while if is at the leftmost end of its chain, we specified that takes (that is, the following element in the chain) to .

Our function is injective. Since the chains don't overlap, and the first three cases of "what a chain might look like" have no repeats at all, the only possible way an element of can be hit twice by is if that element lies in one of the cyclical chains. But then to elements of in that chain, assigns the following element of ; so is hit only by the preceding element of , which is the same in all cases because the chain is a cycle. [4]

Proof from the Knaster-Tarski theorem

This proof is very quick, but almost completely opaque. It relies on the Knaster-Tarski fixed point theorem, which states that if is a complete poset and is order-preserving, then has a fixed_point (i.e. such that ).

Let and be injective.

We are looking for a partition of , and a partition of , such that is injective from to , and is injective from to . (Then we can just define our bijection by "do on , and do on ".)

Now, the function is order-preserving from the power_set to (ordered by inclusion), because there is an even number of complements.

But is complete as a poset (proof), so by Knaster-Tarski there is a set such that .

This yields our partition as required.

  1. ^︎

    On the other hand, perhaps the sequence does extend infinitely to the left.

  2. ^︎

    And maybe there is a repeat somewhere to the left, too.

  3. ^︎

    Though maybe we're looking at a different place on the same chain. If we compare the -chain with the -chain, we see they're the same chain viewed two different ways: one viewing is two places offset from the other viewing.

  4. ^︎

    The picture in the linked intuitive document makes this much clearer.

Parents:
Parents
1.
^︎

On the other hand, perhaps the sequence does extend infinitely to the left.

2.
^︎

And maybe there is a repeat somewhere to the left, too.

3.
^︎

Though maybe we're looking at a different place on the same chain. If we compare the -chain with the -chain, we see they're the same chain viewed two different ways: one viewing is two places offset from the other viewing.

4.
^︎

The picture in the linked intuitive document makes this much clearer.