nLab
Cantor-Schroeder-Bernstein theorem

Contents

Statement

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 XYX \leq Y if there exists a monomorphism f:XYf\colon X \to Y. Then, if both XYX \leq Y and YXY \leq X, there exists an isomorphism of sets XYX \cong Y.

The result is really only interesting in the absence of the axiom of choice (ACAC). With ACAC, 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.

Proof

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 Set Set^{\bullet \to \bullet} (the arrow category of SetSet); see Example 2 below.

Throughout we use ordinary set-theoretic reasoning which can be translated into the formal theory of toposes. (This can be formalized via the Mitchell–Benabou language, for instance.)

Lemma (Knaster–Tarski fixed-point theorem)

Let f:PXPXf\colon P X \to P X be an order-preserving map. Then there exists SS in PXP X for which f(S)=Sf(S) = S.

Proof

Let SS be the (internal) intersection of U={TPX:f(T)T}U = \{T \in P X : f(T) \leq T\}. Since STS \leq T for every TT in UU, we have f(S)f(T)Tf(S) \leq f(T) \leq T for every TT in UU. Hence f(S)Sf(S) \leq S by definition of SS. Applying ff again, we get ff(S)f(S)f f(S) \leq f(S). Hence f(S)f(S) belongs to UU. But then Sf(S)S \leq f(S) by definition of SS.

Remark

The preceding proof is valid in any topos (and so holds for SetSet even intuitionistically). It can be seen as a special case of a result of Lambek on the initial algebra of an endofunctor.

Proof of Cantor–Schroeder–Bernstein

Suppose given two monos f:XYf\colon X \to Y, g:YXg\colon Y \to X. Let f:PXPY\exists_f\colon P X \to P Y denote existential quantification along ff, and let ¬ X:PXPX\neg_X\colon P X \to P X denote negation. Then the composite

¬ X g¬ Y f:PXPX\neg_X \exists_g \neg_Y \exists_f\colon P X \to P X

is order-preserving, and so has a fixed point SS by the lemma. Now define h:XYh\colon X \to Y by the rule

h(x) = f(x) ifxS h(x) = g 1(x) ifxS\array{ h(x) & = & f(x) & if x \in S \\ h(x) & = & g^{-1}(x) & if x \notin S }

(the multi-line definition is where we use the Boolean condition). The second line makes sense because ¬S\neg S is in the image of gg. The inverse of hh is

j(y) = f 1(y) ify f(S) j(y) = g(y) ify f(S)\array{ j(y) & = & f^{-1}(y) & if y \in \exists_f(S) \\ j(y) & = & g(y) & if y \notin \exists_f(S) }

That jj is inverse to h uses the fact that ¬S= g¬ f(S)\neg S = \exists_g \neg \exists_f(S). 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 (EMEM) 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

FinSet CFinSet^C

where CC is any nontrivial finite category. But EMEM is certainly the most natural supposition to make.

Failure in toposes

Example

Counterexample 4 below shows that the CSB theorem fails in Brouwer's intuitionistic mathematics even for SetSet (since every function between the sets [0,1][0, 1] and \mathbb{R} 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.

Example

As mentioned above, the Cantor-Schroeder-Bernstein theorem fails in the arrow category Set Set^\to, whose objects are functions X 0X 1X_0 \to X_1 between sets and whose morphisms are commutative squares. For example, let XX be the object f:f: \mathbb{N} \to \mathbb{N} that takes nn \in \mathbb{N} to int(n/2)\mathrm{int}(n/2), where int(x)\mathrm{int}(x) is the greatest integer less than or equal to xx; let YY be the object g:g: \mathbb{N} \to \mathbb{N} that takes nn to Int((n+1)/2)\mathrm{Int}((n+1)/2), where Int(x)\mathrm{Int}(x) is the least integer greater than or equal to xx. Pretty clearly XX and YY are non-isomorphic, because g 1(0)g^{-1}(0) has cardinality 11 whereas all fibers of ff have cardinality 22. But, just by drawing pictures of these objects, it is easy to construct monomophisms i:XYi: X \to Y and j:YXj: Y \to X (e.g., define i 0(n)=n+1i_0(n) = n+1 and i 1(n)=n+1i_1(n) = n+1 for all nn, and define j 0(n)=n+1j_0(n) = n+1 for n>0n \gt 0, j 0(0)=0j_0(0) = 0, and j 1(n)=nj_1(n) = n for all nn).

Nor can one have internal existence of an isomorphism between XX and YY in this last example, since internal existence implies external existence as soon as the terminal object is (externally) projective.

In other categories

The CSB property holds in many other categories of interest. For example:

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

Counterexample

On the other hand, the CSB property fails in Top, since we have embeddings (0,1)[0,1]\mathbb{R} \cong (0,1) \to [0,1] \to \mathbb{R}, yet [0,1][0,1] \ncong \mathbb{R}.

More examples and discussion can be found at this Secret Blogging Seminar post.

In a celebrated work, Timothy Gowers gave a negative solution in the case of Banach spaces.

Name

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.

Wikipedia reports that Richard Dedekind had an (unpublished) proof in 1887, well before any announced proofs by Cantor, Schroeder, or Bernstein in 1895, 1896, 1897 respectively.

References

Revised on October 20, 2014 00:51:28 by Toby Bartels (98.19.46.50)