The Cantor–Schroeder–Bernstein theorem says that the usual order relation on cardinalities of sets is antisymmetric. In other words, define an order on sets by if there exists a monomorphism . Then, if both and , there exists an isomorphism of sets .
The result is really only interesting in the absence of the axiom of choice (). With , it is a trivial corollary of the well-ordering theorem. However, the theorem actually requires only excluded middle, although it does not hold in constructive mathematics.
We prove that the Cantor–Schroeder–Bernstein theorem holds in a Boolean topos. The theorem is not however intuitionistically valid, in that it fails in some toposes, such as the topos (the arrow category of ); see Example 2 below.
Let be an order-preserving map. Then there exists in for which .
Let be the (internal) intersection of . Since for every in , we have for every in . Hence by definition of . Applying again, we get . Hence belongs to . But then by definition of .
is order-preserving, and so has a fixed point by the lemma. Now define by the rule
(the multi-line definition is where we use the Boolean condition). The second line makes sense because is in the image of . The inverse of is
That is inverse to h uses the fact that . The rest is obvious.
This classic proof is substantially the proof given in Johnstone’s Elephant, D4.1.11. The Boolean condition is not strictly speaking necessary, i.e., the principle of excluded middle () does not logically follow from the Cantor–Schroeder–Bernstein statement since, for example, the latter holds vacuously (every mono is an iso) in the non-Boolean topos
where is any nontrivial finite category. But is certainly the most natural supposition to make.
Counterexample 4 below shows that the CSB theorem fails in Brouwer's intuitionistic mathematics even for (since every function between the sets and must be continuous by Brouwer's continuity principle!). See also the discussion in Mac Lane-Moerdijk, VI.9, on toposes that realize Brouwer’s theorem.
As mentioned above, the Cantor-Schroeder-Bernstein theorem fails in the arrow category , whose objects are functions between sets and whose morphisms are commutative squares. For example, let be the object that takes to , where is the greatest integer less than or equal to ; let be the object that takes to , where is the least integer greater than or equal to . Pretty clearly and are non-isomorphic, because has cardinality whereas all fibers of have cardinality . But, just by drawing pictures of these objects, it is easy to construct monomophisms and (e.g., define and for all , and define for , , and for all ).
Nor can one have internal existence of an isomorphism between and in this last example, since internal existence implies external existence as soon as the terminal object is (externally) projective.
The CSB property holds in many other categories of interest. For example:
The CSB property holds in the category of vector spaces and in the category of algebraically closed fields. See also this MO post, where model-theoretic criteria come into play, sometimes under strengthenings of the notion of monomorphism (e.g., elementary embedding, split monomorphism).
More examples and discussion can be found at this Secret Blogging Seminar post.
The CSB theorem was first stated by Georg Cantor, but his proof relied on the well-ordering theorem. The modern (choice-free) theorem was proved (independently) by Felix Bernstein? and Ernst Schröder?. It has been variously named after two or three of these in almost every possible combination, although Cantor (when mentioned at all) seems always to be mentioned first.