nLab
Cantor-Schroeder-Bernstein theorem

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

The result is really only interesting in the absence of the axiom of choice ($\mathrm{AC}$). With $\mathrm{AC}$, 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 ${\mathrm{Set}}^{•\to •}$ (the arrow category of $\mathrm{Set}$); 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:PX\to PX$ be an order-preserving map. Then there exists $S$ in $PX$ for which $f(S)=S$.

Proof

Let $S$ be the (internal) intersection of $U=\{T\in PX:f(T)\le T\}$. Since $S\le T$ for every $T$ in $U$, we have $f(S)\le f(T)\le T$ for every $T$ in $U$. Hence $f(S)\le S$ by definition of $S$. Applying $f$ again, we get $ff(S)\le f(S)$. Hence $f(S)$ belongs to $U$. But then $S\le f(S)$ by definition of $S$.

Remark

The preceding proof is valid in any topos (and so holds for $\mathrm{Set}$ 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:X\to Y$, $g:Y\to X$. Let ${\exists }_f:PX\to PY$ denote existential quantification along $f$, and let ${\neg }_X:PX\to PX$ denote negation. Then the composite

$${\neg }_X{\exists }_g{\neg }_Y{\exists }_f:PX\to PX$$\neg_X \exists_g \neg_Y \exists_f\colon P X \to P X

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

$$\begin{array}{cccc}h(x)& =& f(x)& \mathrm{if}x\in S\\ h(x)& =& g^{-1}(x)& \mathrm{if}x\notin S\end{array}$$\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 $\neg S$ is in the image of $g$. The inverse of $h$ is

$$\begin{array}{cccc}j(y)& =& f^{-1}(y)& \mathrm{if}y\in {\exists }_f(S)\\ j(y)& =& g(y)& \mathrm{if}y\notin {\exists }_f(S)\end{array}$$\array{ j(y) & = & f^{-1}(y) & if y \in \exists_f(S) \\ j(y) & = & g(y) & if y \notin \exists_f(S) }

That $j$ is inverse to h uses the fact that $\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 ($\mathrm{EM}$) 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

$${\mathrm{FinSet}}^C$$FinSet^C

where $C$ is any nontrivial finite category. But $\mathrm{EM}$ 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 $\mathrm{Set}$ (since every function between the sets $[0,1]$ 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.

Example

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

Nor can one have internal existence of an isomorphism between $X$ and $Y$ 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 $ℝ\cong (0,1)\to [0,1]\to ℝ$, yet $[0,1]\ncong ℝ$.

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

• Peter Johnstone, Sketches of an Elephant: A Topos Theory Conpendium, Vol. I, Clarendon Press, Oxford (2002)

• Timothy Gowers, A Solution to the Schroeder-Bernstein Problem for Banach Spaces, Bulletin of the London Mathematical Society, Volume 28, Issue 3 (1996), 297-304 (abstract)

• Saunders Mac Lane and Ieke Moerdijk, Sheaves in Geometry and Logic, Springer-Verlag 1992.