Cantor-Schröder-Bernstein theorem

Re­call that we say a set \(A\) is smaller than or equal to a set \(B\) if there is an in­jec­tion from \(A\) to \(B\). The set \(A\) has the same size as \(B\) if there is a bi­jec­tion be­tween \(A\) and \(B\).

The Can­tor-Schröder-Bern­stein the­o­rem states that if \(A\) is smaller than or equal to \(B\), and \(B\) is smaller than or equal to \(A\), then \(A\) and \(B\) have the same size. This tells us that the ar­ith­metic of car­di­nals is well-be­haved in that it be­haves like a to­tal or­der. It is similar to the ar­ith­metic of the nat­u­ral num­bers in that it can never be the case that si­mul­ta­neously \(a < b\) and \(b < a\).

Proofs

There are sev­eral proofs, some con­crete and some less so.

Con­crete proof

A clear ex­pla­na­tion of the in­tu­ition of this proof has been writ­ten by Richard Evan Schwartz; see page 61 of the linked PDF, or search on the word “dog” (which ap­pears in the first page of the ex­pla­na­tion). The in­tu­ition is Math0 suit­able.

Let \(f: A \to B\) and \(g: B \to A\) be in­jec­tions; we will define a bi­jec­tive func­tion \(h: A \to B\).

Be­cause \(f\) is in­jec­tive, if \(f\) ever hits \(b\) (that is, if there is \(a \in A\) such that \(f(a) = b\)) then it is pos­si­ble to define \(f^{-1}(b)\) to be the unique \(a \in A\) such that \(f(a) = b\); similarly with \(g\). The slo­gan is “if \(f^{-1}(a)\) ex­ists, then it is well-defined: there is no lee­way about which el­e­ment we might choose to be \(f^{-1}(a)\)”.

Fix some \(a \in A\), and con­sider the se­quence

$$\dots, f^{-1}(g^{-1}(a)), g^{-1}(a), a, f(a), g(f(a)), \dots$$
Now, this se­quence might not ex­tend in­finitely to the left; it may not even get past \(a\) to the left (if \(g^{-1}(a)\) doesn’t ex­ist, for in­stance). noteOn the other hand, per­haps the se­quence does ex­tend in­finitely to the left. Also, the se­quence might du­pli­cate el­e­ments: it might be the case that \(gfgf(a) = a\), for in­stance. noteAnd maybe there is a re­peat some­where to the left, too.

Similarly, we can fix some \(b \in B\), and con­sider

$$\dots g^{-1} f^{-1}(b), f^{-1}(b), b, g(b), f(g(b)), \dots$$

Every el­e­ment of \(A\), and ev­ery el­e­ment of \(B\), ap­pears in one of these chains. More­over, if \(a \in A\) ap­pears in two differ­ent chains, then in fact the two chains are the same noteThough maybe we’re look­ing at a differ­ent place on the same chain. If we com­pare the \(g^{-1} f^{-1}(b)\)-chain with the \(b\)-chain, we see they’re the same chain viewed two differ­ent ways: one view­ing is two places offset from the other view­ing., be­cause each el­e­ment of the chain speci­fies and is speci­fied by the pre­vi­ous el­e­ment in the chain (if it ex­ists) and each el­e­ment of the chain speci­fies and is speci­fied by the next el­e­ment of the chain.

So ev­ery el­e­ment of \(A\) and ev­ery el­e­ment of \(B\) is in ex­actly one chain. Now, it turns out that there are ex­actly four dis­tinct “types” of chain.

  • It could ex­tend in­finitely in both di­rec­tions with­out re­peats. In this case, we define \(h(a) = f(a)\) for each el­e­ment of \(A\) in the chain. (Ba­si­cally as­sign­ing to each el­e­ment of \(A\) the el­e­ment of \(B\) which is next in the chain.)

  • It could ex­tend in­finitely off to the right, but it has a hard bar­rier at the left, and has no re­peats: the chain stops at an el­e­ment of \(A\). In this case, again we define \(h(a) = f(a)\) for each el­e­ment of \(A\) in the chain. (Again, ba­si­cally as­sign­ing to each el­e­ment of \(A\) the el­e­ment of \(B\) which is next in the chain.)

  • It could ex­tend in­finitely off to the right, but it has a hard bar­rier at the left, and has no re­peats: the chain stops at an el­e­ment of \(B\). In this case, we define \(h(a) = g^{-1}(a)\) for each el­e­ment of \(A\) in the chain. (Ba­si­cally as­sign­ing to each el­e­ment of \(A\) the el­e­ment of \(B\) which is pre­vi­ous in the chain.)

  • It could have re­peats. Then it must ac­tu­ally be a cy­cle of even length (un­rol­led into an in­finite line), be­cause each el­e­ment of the chain only de­pends on the one be­fore it, and be­cause we can’t have two suc­ces­sive el­e­ments of \(A\) (since the el­e­ments are al­ter­nat­ing be­tween \(A\) and \(B\)). In this case, we define \(h(a) = f(a)\) for each el­e­ment of \(A\) in the chain. (Ba­si­cally as­sign­ing to each el­e­ment of \(A\) the el­e­ment of \(B\) which is next in the chain.)

Have we ac­tu­ally made a bi­jec­tion? Cer­tainly our func­tion is well-defined: ev­ery el­e­ment of \(A\) ap­pears in ex­actly one chain, and we’ve speci­fied where ev­ery el­e­ment of \(A\) in any chain goes, so we’ve speci­fied where ev­ery el­e­ment of \(A\) goes.

Our func­tion is sur­jec­tive, be­cause ev­ery el­e­ment of \(B\) is in a chain; if \(b \in B\) has an el­e­ment \(a\) of \(A\) be­fore it in its chain, then we speci­fied that \(h\) takes \(a\) to \(b\), while if \(b \in B\) is at the left­most end of its chain, we speci­fied that \(h\) takes \(g(b)\) (that is, the fol­low­ing el­e­ment in the chain) to \(b\).

Our func­tion is in­jec­tive. Since the chains don’t over­lap, and the first three cases of “what a chain might look like” have no re­peats at all, the only pos­si­ble way an el­e­ment of \(B\) can be hit twice by \(h\) is if that el­e­ment lies in one of the cycli­cal chains. But then to el­e­ments of \(A\) in that chain, \(h\) as­signs the fol­low­ing el­e­ment of \(B\); so \(b \in B\) is hit only by the pre­ced­ing el­e­ment of \(A\), which is the same in all cases be­cause the chain is a cy­cle. noteThe pic­ture in the linked in­tu­itive doc­u­ment makes this much clearer.

Proof from the Knaster-Tarski theorem

This proof is very quick, but al­most com­pletely opaque. It re­lies on the Knaster-Tarski fixed point the­o­rem, which states that if \(X\) is a com­plete poset and \(f: X \to X\) is or­der-pre­serv­ing, then \(f\) has a fixed point (i.e.\(x\) such that \(f(x) = x\)).

Let \(f: A \to B\) and \(g: B \to A\) be in­jec­tive.

We are look­ing for a par­ti­tion \(P \cup Q\) of \(A\), and a par­ti­tion \(R \cup S\) of \(B\), such that \(f\) is in­jec­tive from \(P\) to \(R\), and \(g\) is in­jec­tive from \(S\) to \(Q\). (Then we can just define our bi­jec­tion \(A \to B\) by “do \(f\) on \(P\), and do \(g^{-1}\) on \(Q\)”.)

Now, the func­tion \(P \mapsto A \setminus g(B \setminus f(P))\) is or­der-pre­serv­ing from the power set \(\mathcal{P}(A)\) to \(\mathcal{P}(A)\) (or­dered by in­clu­sion), be­cause there is an even num­ber of com­ple­ments.

But \(\mathcal{P}(A)\) is com­plete as a poset (proof), so by Knaster-Tarski there is a set \(P\) such that \(P = A \setminus g(B \setminus f(P))\).

This yields our par­ti­tion as re­quired. spell this out

Parents:

  • Set

    An un­ordered col­lec­tion of dis­tinct ob­jects.