Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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 AA and BB be sets. If there exist injections f:ABf \colon A \to B and g:BAg \colon B \to A, then |A|=|B||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()|=|||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 ff and gg might be used to construct a bijection ABA \cong B in the following manner: by finding subsets A *AA^\ast \subset A and B *BB^\ast \subset B so that ff defines a bijection between A *A^\ast and its image, the complement of B *B^\ast, and gg defines a bijection between B *B^\ast and its image, the complement of A *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:P(A)P(A)h \colon P(A) \to P(A) defined by h(X)=A\g(B\f(X)).h(X) = A \backslash g(B \backslash f(X)).

Here I’m thinking of the powerset P(A)P(A) as a poset, ordered by inclusion, and indeed hh is a functor: XYAX \subset Y \subset A implies that h(X)h(Y)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 XX with the property that Xh(X)X \subset h(X). Let 𝒞P(A)\mathcal{C} \subset P(A) be the subposet of coalgebras (if you will, defined by the forming the inserter of the identity and hh). 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={XAXh(X)}. C = \cup \{X \subset A \mid X \subset h(X)\}.

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

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

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

defined by repeatedly applying the endofunctor hh to the terminal object AP(A)A \in P(A). Because P(A)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 ff and gg and their partially-defined inverses define a partition of ABA \sqcup B into disjoint infinite (possibly repeating) chains of elements contained alternately in AA and in BB

a,f(a),g(f(a)),f(g(f(a)), \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 ff or gg. For those elements in chains that terminate at the left at an element of AA (resp. BB), ff (resp. gg) is used to define the bijection. For the remaining chains, either ff or gg may be used.

Arguing inductively by cases, you can see that the limit of the inverse sequence, i.e., the terminal coalgebra of hh is the union of those elements aAa \in A that appear in chains that either terminate at an element of AA 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 hh, 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 AA 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 nnLab 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:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2788

6 Comments & 0 Trackbacks

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 0\aleph_0-complete Boolean algebras:

Theorem (Tarski) Let A 1,A 2,B,CA_1,A_2,B,C be 0\aleph_0-complete Boolean algebras such that A 1A 2×BA_1\simeq A_2\times B and A 2A 1×CA_2\simeq A_1\times C. Then A 1A 2A_1\simeq A_2.

To see that Tarski’s theorem implies CSBT observe that the existence of a monomorphism X 1X 2X_1\to X_2 in SetSet is the same thing as existence of a set YY such that X 1X 2YX_1\simeq X_2\oplus Y and this is the same thing as P(X 1)P(X 2)×P(Y)P(X_1)\simeq P(X_2)\times P(Y) in the category of 0\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 SetSet we are dealing with intervals [0,a][0,a] in A 1A_1 and instead of the “same cardinality” equivalence we are dealing with isomorphism of 0\aleph_0-complete Boolean algebras.

Let me say that Tarski’s theorem is not true if we drop “ 0\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][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 ab+ca\sim b+c, then there are a 1,a 2a_1,a_2 such that a=a 1+a 2a=a_1+a_2, a 1ba_1\sim b and a 2ca_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 SetSet we are dealing with intervals [0,a][0,a] in A 1A_1

Here I’m guessing 00 is the initial object and aa is a generic interval in the boolean algebra A 1A_1 and the interval is the set of elements 0xa0 \leq x \leq a. I guess if we identify an injection in SetSet with the subset of its image XX, that corresponds to an element aP(X)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 SetSet rather than about monos in SetSet. 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 hh should be h(X)=Ag(Bf(X))h(X) = A\setminus g(B\setminus f(X)). Note that this also can be written as g *(f !(X))g_\ast(f_!(X)), where f !f_! is the left adjoint to f 1f^{-1} and g *g_\ast is the right adjoint to g 1g^{-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