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

  • $\begingroup$ Are you familiar with ordinals and well-orders? $\endgroup$ – Michael Greinecker Oct 29 '12 at 16:15
  • $\begingroup$ @MichaelGreinecker I am, yes. $\endgroup$ – Acid2 Oct 29 '12 at 16:20

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)

| cite | improve this answer | |
  • $\begingroup$ Thank you for your answer as well. Reading about how these ideas were historically developed is quite interesting. Is that what your book's going to be about? $\endgroup$ – Acid2 Oct 29 '12 at 16:46
  • $\begingroup$ It is about a few selected topics in set theory, but I've tried to pay attention to historical details when appropriate. The Schroeder-Bernstein theorem is particularly interesting from a historical point of view. $\endgroup$ – Andrés E. Caicedo Oct 29 '12 at 16:53
  • $\begingroup$ @Andres Dedekind essentially prove the theorem in 1887. The corresponding part in his Gesammelte Werke can be found here. $\endgroup$ – Michael Greinecker Oct 30 '12 at 23:50
  • $\begingroup$ Yes, Michael, thanks. I only wrote above on the part that was strictly related to Cantor, I discuss the history a bit more in the book. $\endgroup$ – Andrés E. Caicedo Oct 31 '12 at 1:39
  • 1
    $\begingroup$ How's the book coming along? Would be interested to read it. $\endgroup$ – David Roberts Jun 30 '17 at 7:33

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?

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\begingroup$ Wow that was easy - easier than I expected! Thanks for your help. $\endgroup$ – Acid2 Oct 29 '12 at 16:34
  • $\begingroup$ One question; why isn't this proof more 'popular'? There are various different proofs of this theorem and even the simplest of those (two) that I've been able to follow/understand are quite complicated and not much fun. $\endgroup$ – Acid2 Oct 29 '12 at 16:40
  • $\begingroup$ It is a fundamental result of cardinal arithmetic that works without the axiom of choice and can be used before one learns about well-orders. A way the usual proofs can be made less messy is by assuming one set is a subset of the other and the injection into the bigger set is the identity. $\endgroup$ – Michael Greinecker Oct 29 '12 at 16:43
  • $\begingroup$ Doesn't the fact that all cardinals are comparable depend on the axiom of choice? How can this proof work, as you say, without it? $\endgroup$ – Acid2 Oct 29 '12 at 16:52
  • $\begingroup$ I mean the usual Cantor-Bernstein theorem and proofs by back-and-forth or a fixed point argument. Te proof I've given depends of course on the axiom of choice. $\endgroup$ – Michael Greinecker Oct 29 '12 at 16:55

Check http://link.springer.com/book/10.1007/978-3-0348-0224-6/page/1

The details are quite different from those in the other answers here.

To complete my answer:

Cantor's original proof of the Cantor-Bernstein Theorem.

First, let me comment on some of the points mentioned above.

  1. The question assumes that Cantor's original proof relied on the axiom of choice. But the axiom of choice emerged only in 1904, well after Cantor finished his research.

  2. Cantor mentioned the well-ordering principle only in his 1883 paper (the above referenced Über unendlich… paper). So it cannot be maintained that his view on the principle "oscillated".

  3. Cantor needed the well-ordering principle in order to establish the arithmetic operations between his transfinite numbers (which he later called ordinals), and not for trichotomy, which is not mentioned in 1883. With the well-ordering principle Cantor also tacitly assumed a numbering principle which provides that for every well-ordered set there is a transfinite number similar to it, which is thus its numbering (Anzahl). With his later definition of the transfinite numbers (ordinals) by abstraction, instead of the earlier generation principles, Cantor had no further need for the well-ordering principle and its ancillary numbering principle to provide for the arithmetic operations between ordinals. So Cantor dropped the well-ordering principle after 1883.

  4. Cantor stated the Cantor-Bernstein Theorem (CBT) in 1883 as an immediate corollary to several theorems that established that the second number-class. Thus CBT was established for sets of the power $\aleph_1$, not for subsets of $\mathbb R^n$, and without assuming CH. CH is needed to apply the theorem to subsets of $\mathbb R^n$ but Cantor never did that. In fact, he didn't have to for, I believe, Cantor had a direct proof for CBT for $\mathbb R$ and thus for $\mathbb R^n$ (in view of his results in 1878). See my book referenced above.

  5. Cantor's construction of the number-classes from 1883 can be generalized. The proof is by transfinite induction which Cantor used for other proofs as well without identifying the procedure explicitly. Note that there are in fact two inductive arguments in the proof: one over the index of the number-classes and a second over the numbers in every preceding number-class. The generalized CBT is a necessary lemma in the proof establishing the construction of the scale of number-classes. Again I must reference my book.

  6. In the referenced 1895 paper three versions of CBT appear: the quoted B, the version which was mentioned in the answer above as originating from 1882, and a third version denoted there E.

  7. Cantor presented all three versions as simple corollary to the theorem referenced above as trichotomy. There Cantor postponed the proof of trichotomy to until such time when the ascending sequence of cardinal numbers will be established. The ground work for that scale, namely the scale of the number-classes was established in the 1897 paper. However, Cantor did not go back to trichotomy and this created some confusion. Zermelo interpreted the situation as implying that Cantor could not prove trichotomy and his view was adopted by almost all commentators on Cantor.

  8. Cantor intended to publish a third sequel to the 1895, 1897 papers. We know that from his correspondence with Hilbert. There he presumably intended to fill the blanks he left around the trichotomy theorem. However, Cantor was hesitant to go ahead with the third sequel until he got Dedekind's approval to the ideas contained therein, but Dedekind refused to get involved. We know this again from Cantor's correspondence. The ideas which Cantor was afraid to publish were two: First, that there are inconsistent sets in mathematics. These are the classes of today. Had Cantor published his ideas, which may have originated already in 1883, perhaps the scare of the antinomies would have been avoided. Second, that a new axiom is necessary to introduce to mathematics. It was the statement presented as corollary D to trichotomy. In fact Cantor was ready to assume both D and CBT (corollary B) but fortunately proofs for CBT began to emerge in 1897 and so there was no need to take CBT as axiom. These axioms were hinted in a letter to Schoenflies of 1899.

  9. In light of the above it seems to me that the idea that Cantor presented CBT in 1895 as an open problem cannot be maintained. Notwithstanding this remark I do recommend that you should consult besides my book also Ferreiros 1999, Birkhäuser.

| cite | improve this answer | |
  • 1
    $\begingroup$ Link only answers are not really good; could you at least give a sketch of the argument? $\endgroup$ – egreg Feb 15 '14 at 18:28
  • $\begingroup$ Nice reference, I was not aware of it. Thanks! $\endgroup$ – Andrés E. Caicedo Feb 16 '14 at 8:16
  • $\begingroup$ One thing about the fact that Cantor's proof relied on the axiom of choice; note that in fact many proofs given before the foundational crisis of the late-19th and early-20th centuries were using certain axioms before these were formulated. Because mathematicians didn't really think in terms of axioms (many still don't) and formal definitions; but when that began, the proofs were analyzed and in some of them we found use of the axiom of choice (or other axioms), and in others we didn't. If a proof uses the axiom of choice, then it uses the axiom of choice. Regardless to its temporal origins. $\endgroup$ – Asaf Karagila May 7 '14 at 17:14
  • $\begingroup$ Dear Arie, Many thanks for the expanded remarks. $\endgroup$ – Andrés E. Caicedo May 9 '14 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.