Looking for Cantor's original proof of the Cantor-Bernstein theorem that relies on the axiom of choice?

Question

Even a sketch of it would be good enough. Thanks.

Answer 1

The proof relies on the well-ordering principle: Any set is well-orderable. Since any two well-orderings are comparable, this gives the result.

Cantor was not sure for many years whether this principle was self-evidently true, needed a proof, or needed to be postulated, so his writings oscillate between claiming the result as true, or as needing a proof.

Cantor first considered the statement (that he called the equivalence theorem) around 1882, in the form:

If $A\subseteq B\subseteq C$ and $A\sim C$, then $A\sim B$,

where $A\sim B$ means that there is a bijection between $A$ and $B$. Originally, this was stated only for subsets of $\mathbb R^n$, and assuming $\mathsf{CH}$, the continuum hypothesis. A proof in this setting appeared in 1883, see page 574 of

• Georg Cantor. Über unendliche, lineare Punktmannichfaltigkeiten. V, Math. Ann. 21 (4), (1883), 545–590. MR1510215

In full generality, the theorem is explicitly stated in the first half of a two-part paper published in Mathematische Annalen in 1895 and 1897, the English translation is

• Contributions to the founding of the theory of transfinite numbers, translated, and provided with an introduction and notes, by Philip E. B. Jourdain. Dover Publications, Inc., New York, N. Y., 1952. MR0045635 (13,612d)

It appears as Theorem B, page 91, (Satze B, page 484, in the 1895 paper):

B. If two aggregates $M$ and $N$ are such that $M$ is equivalent to a part $N_1$ of $N$ and $N$ to a part $M_1$ of $M$, then $M$ and $N$ are equivalent.

B. Sind zwei Mengen $M$ und $N$ so beschaffen, dass $M$ mit einem Theil $N_1$ von $N$ und $N$ mit einem Theil $M_1$ von $M$ äquivalent ist, so sind auch $M$ und $N$ äquivalent.

As I mentioned above, he intended to derive the result from trichotomy (any two cardinals are comparable), which renders the statement trivial by modern standards. In more detail: Cantor expected all sets to be well-orderable. Any two well-orders are comparable, in fact, if $\alpha$ and $\beta$ are well-orders, then exactly one of the following holds:

1. $\alpha$ and $\beta$ are order isomorphic, and the isomorphism is unique.
2. $\alpha$ is order isomorphic to a unique proper initial segment of $\beta$, and the isomorphism is unique.
3. $\beta$ is order isomorphic to a unique proper initial segment of $\alpha$, and the isomorphism is unique.

Given $A$, there is a well-order of smallest possible length that is in bijection with $A$ (assuming that $A$ is well-orderable). Similarly for $B$. If $A$ and $B$ inject into each other, the trichotomy above easily gives us that the corresponding ordinals are order isomorphic, so that $A\sim B$.

Details were postponed to the second part of his paper, where the theory of ordinals is developed, and were not presented in full. Whether he actually had a complete proof is questioned by some authors, see for example De Araujo. As pointed out above, the issue is that at that time, it was not clear whether Cantor considered trichotomy and other versions of choice as statements that ought to be proved from earlier principles, or as additional assumptions. This may explain why Cantor's early mentions of the theorem regard it as an open question, both in papers (1884) and in his correspondence with Dedekind (1883).

---

All this comes from a book I am writing. A nice alternative source is

Gregory H. Moore. Zermelo’s axiom of choice. Its origins, development, and influence, Studies in the History of Mathematics and Physical Sciences 8, Springer-Verlag, New York, 1982. MR0679315 (85b:01036)

Answer 2

Using the axiom of choice, every set can be well ordered. For each set $X$, let $|X|$ be the smallest ordinal order-isomorphic to some well-ordering of $X$. If there is an injection $f:Y\to X$, then $Y$ can be identified with a subset of $X$ and hence with a subset of $|X|$. The order type of this set is smaller or equal to $|X|$, hence $|Y|\leq |X|$. If there is also an injection from $X$ to $Y$, we can conclude that $|X|\leq|Y|$. Since the class of ordinals is well-ordered it satisfies anti-symmetry and we can conclude that $|X|=|Y|$. So there are bijections from both $X$ and $Y$ to the ordinal $|X|=|Y|$, and combining these bijections gives us a bijection between $X$ and $Y$.

Answer 3

Cantor's original proof relies on the well-ordering principle, stating that every set can be well-ordered.

If $A\leq B$, namely there is an injection from $A$ into $B$; and $B\leq A$, so there is also an injection from $B$ into $A$, using the well-ordering principle let $\alpha$ be the least ordinal such that $\alpha$ has a bijection with $A$; and let $\beta$ be the least ordinal which has a bijection with $B$.

Now note that a subset of an ordinal can be "collapsed" and be put in bijection with an ordinal, not necessarily a smaller one though. If $\gamma<\alpha$ was such that there was an injection from $A$ into $\gamma$ then by collapsing the range of this injection we would get a bijection of $A$ with an ordinal $\leq\gamma$. Therefore $A$ cannot be injected into any smaller ordinal than $\alpha$ or we would contradict the minimality of $\alpha$, and the same argument shows that $B$ cannot be injected into any ordinal smaller than $\beta$.

By composing the injections between $A$ and $B$, and the bijections with $\alpha$ and $\beta$ we have an injection from $A$ into $\beta$ and from $B$ into $\alpha$. The above argument shows that we have $\alpha\leq\beta$ as well $\beta\leq\alpha$. Therefore we must have $\alpha=\beta$.

By composing the bijections from $A$ to $\alpha$ and from $\alpha$ to $B$ we have a bijection between $A$ and $B$ as wanted.

See also: Cantor-Bernstein-like theorem: If $f\colon A\to B$ is injection and $g\colon A\to B$ is surjective, can we prove there is a bijection as well?