The n-Category Café

Proof of Cantor–Schröder–Bernstein

Let me start by describing the proof I have in mind. The hope is that $f$ and $g$ might be used to construct a bijection $A \cong B$ in the following manner: by finding subsets $A^\ast \subset A$ and $B^\ast \subset B$ so that $f$ defines a bijection between $A^\ast$ and its image, the complement of $B^\ast$, and $g$ defines a bijection between $B^\ast$ and its image, the complement of $A^\ast$.

The first trick — and this is the part that I do not understood categorically — is that a pair of subsets with the above property is encoded by a fixed point to the function

$h \colon P(A) \to P(A)$ defined by $h(X) = A \backslash g(B \backslash f(X)).$

Here I’m thinking of the powerset $P(A)$ as a poset, ordered by inclusion, and indeed $h$ is a functor: $X \subset Y \subset A$ implies that $h(X) \subset h(Y)$. Now the second trick is to remember that a terminal coalgebra for an endofunctor, if it exists, defines a fixed point.

Here the coalgebras are just those subsets $X$ with the property that $X \subset h(X)$. Let $\mathcal{C} \subset P(A)$ be the subposet of coalgebras (if you will, defined by the forming the inserter of the identity and $h$). I don’t know whether it is a priori clear that $\mathcal{C}$ has a terminal object, but if it does, then it is given by forming the union

$$C = \cup \{X \subset A \mid X \subset h(X)\}.$$

And indeed this works: it’s easy to check that $C \subset h(C)$ and moreover that this inclusion is an equality. The bijection $A \cong B$ is defined by $f$ applied to $C$ and $g$ applied to the complement of $f(C)$.

Alternatively, we could apply a theorem of Adámek to form the terminal coalgebra: it is the limit of the inverse sequence

$$ \cdots \subset h^3(A) \subset h^2(A) \subset h(A) \subset A]

defined by repeatedly applying the endofunctor $h$ to the terminal object $A \in P(A)$. Because $P(A)$ is complete, this limit must exist.

This construction seems to be related to the other standard proof of Cantor–Schröder–Bernstein, which Wikipedia tells me is due to Julius König. The injections $f$ and $g$ and their partially-defined inverses define a partition of $A \sqcup B$ into disjoint infinite (possibly repeating) chains of elements contained alternately in $A$ and in $B$

$$\cdots a , f(a), g(f(a)), f(g(f(a)), \ldots$$

that terminate at the left whenever there is an element that is not in the image of $f$ or $g$. For those elements in chains that terminate at the left at an element of $A$ (resp. $B$), $f$ (resp. $g$) is used to define the bijection. For the remaining chains, either $f$ or $g$ may be used.

Arguing inductively by cases, you can see that the limit of the inverse sequence, i.e., the terminal coalgebra of $h$ is the union of those elements $a \in A$ that appear in chains that either terminate at an element of $A$ or continue forever (possibly repeating) in both directions. (Side question: is there a slick way to demonstrate this?) This argument tells us that the terminal coalgebra is the maximal fixed point of $h$, but in general it isn’t the only one. The minimal fixed point consists only of those elements in chains that terminate at an element of $A$ on the left.

So, how categorical is this argument? Am I seeing terminal coalgebras just because I learned this proof from a category theorist? Or is this interpretation less superficial than the way I am presenting it?

Concluding remarks:

• The $n$Lab explains that a dual version of this proof holds in any boolean topos, but not in all toposes, because the argument given above requires the law of the excluded middle.

• A category theorist might ask whether Cantor–Schröder–Bernstein holds in other categories. For those wishing to dive into that rabbit hole, I recommend starting here.