# 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.