## December 7, 2014

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

Posted at December 7, 2014 10:45 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2788

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

Posted by: Gejza Jenča on December 10, 2014 8:08 AM | Permalink | Reply to this

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

Gejza,

Thanks for weighing in. This is very interesting.

I’m traveling at the moment so will have to respond slowly, when I find myself graced with a sporadic wifi connection.

Could you explain this:

instead of dealing with injections in $Set$ we are dealing with intervals $[0,a]$ in $A_1$

Here I’m guessing $0$ is the initial object and $a$ is a generic interval in the boolean algebra $A_1$ and the interval is the set of elements $0 \leq x \leq a$. I guess if we identify an injection in $Set$ with the subset of its image $X$, that corresponds to an element $a \in P(X)$. Is that the idea?

Posted by: Emily Riehl on December 10, 2014 4:56 PM | Permalink | Reply to this

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

Yes, that is the idea. It is really that simple.

I think that the CSBT is about coproducts in $Set$ rather than about monos in $Set$. And that the proper generalization of CSBT is some form of Tarski’s theorem for monoidal categories.

Posted by: Gejza Jenča on December 11, 2014 9:12 AM | Permalink | Reply to this

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

As you may know, your last question (together with a commented link to the SB seminar post) appeared a while ago on MO.

Posted by: L Spice on December 10, 2014 11:41 PM | Permalink | Reply to this

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

Small correction: I think your definition of $h$ should be $h(X) = A\setminus g(B\setminus f(X))$. Note that this also can be written as $g_\ast(f_!(X))$, where $f_!$ is the left adjoint to $f^{-1}$ and $g_\ast$ is the right adjoint to $g^{-1}$. This version at least makes sense in a non-Boolean topos (or more generally a Heyting category), and perhaps we can still find its terminal coalgebra, but I guess we won’t then be able to define a bijection by cases on the fixed point and its complement.

Posted by: Mike Shulman on December 20, 2014 7:02 PM | Permalink | Reply to this

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

Thanks Mike. I’ve corrected the typo.

Curiously this is the second time that Heyting categories have come up today (a term I hadn’t heard before this afternoon).

Posted by: Emily Riehl on December 20, 2014 10:57 PM | Permalink | Reply to this

Post a New Comment