### A Categorical Understanding of the Proof of Cantor-Schröder-Bernstein?

#### Posted by Emily Riehl

Over the past year I have become increasingly fascinated by set theory and logic. So this morning when I was meant to be preparing a talk, I instead found myself thinking about the Cantor–Schröder–Bernstein theorem.

**Theorem** (Cantor–Schröder–Bernstein). Let $A$ and $B$ be sets. If there exist injections $f \colon A \to B$ and $g \colon B \to A$, then $|A|=|B|$.

This is an incredibly powerful tool for proving that two sets have the same cardinality. (Exercise: use CSB to prove that $|\mathbb{N}|=|\mathbb{Q}|$ and that $|P(\mathbb{N})|=|\mathbb{R}|$.) Earlier this fall, I taught a proof of this result that I learned from Peter Johnstone’s Notes on logic and set theory. The question that’s distracting me is this: how categorical is this argument?

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

## Re: A categorical understanding of the proof of Cantor-Schröder-Bernstein?

No comments so far, so let me start.

First of all, I do not think that the original Cantor-Schröder-Bernstein theorem is about sets. It is, secretly, about Boolean algebras. In fact, it is about direct products of $\aleph_0$-complete Boolean algebras:

Theorem(Tarski) Let $A_1,A_2,B,C$ be $\aleph_0$-complete Boolean algebras such that $A_1\simeq A_2\times B$ and $A_2\simeq A_1\times C$. Then $A_1\simeq A_2$.To see that Tarski’s theorem implies CSBT observe that the existence of a monomorphism $X_1\to X_2$ in $Set$ is the same thing as existence of a set $Y$ such that $X_1\simeq X_2\oplus Y$ and this is the same thing as $P(X_1)\simeq P(X_2)\times P(Y)$ in the category of $\aleph_0$-complete Boolean algebras.

The proof of the more general theorem is, basically, the same as the original one. However, the surroundings are different now: instead of dealing with injections in $Set$ we are dealing with intervals $[0,a]$ in $A_1$ and instead of the “same cardinality” equivalence we are dealing with isomorphism of $\aleph_0$-complete Boolean algebras.

Let me say that Tarski’s theorem is

nottrue if we drop “$\aleph_0$-complete” from the assumptions. The counterexample is a little bit complicated, as far as I remember. It can be found in the “Handbook of Boolean Algebras”, the proof is based on the theorem that every countable commutative semigroup embeds into the semigroup of isomorphism classes of countable Boolean algebras, equipped with the operation arising from product. It is somewhere in the Volume 3, I think.However, looking at the proof of Tarski’s theorem carefully, one realizes that we do not use all properties of the Boolean algebras. In fact, we use only disjoint unions. Moreover, we do not use all properties of the isomorphism of intervals $[0,a]$, only some of them. Years ago, as an unexperienced pup, I have tried to distill out as general version of the proof as I could. I replaced Boolean algebras with effect algebras and isomorphism of intervals with an equivalence $\sim$ satisfying countable additivity and the axiom

If $a\sim b+c$, then there are $a_1,a_2$ such that $a=a_1+a_2$, $a_1\sim b$ and $a_2\sim c$.

The paper appeared in Algebra Universalis here, the preprint (in an obscure *.ps.zip form) can be found here . The paper reflects the priorities I have had at that time. From todays perspective, the main result should probably be Proposition 3.

Finally, let me mention that there are non-Boolean examples of dimensional equivalences like this appearing in the wild: for example Murray-von Neumann equivalence of projections in a von Neumann algebra.