Fdtxjr

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

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 $Asubseteq Bsubseteq C$ and $Asim C$, then $Asim B$,

where $Asim B$ means that there is a bijection between $A$ and $B$. Originally, this was stated only for subsets of $mathbb R^n$, and assuming $mathsfCH$, 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 $Asim 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)

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

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.

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

If $Aleq B$, namely there is an injection from $A$ into $B$; and $Bleq 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 $leqgamma$. 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 $alphaleqbeta$ as well $betaleqalpha$. 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 $fcolon Ato B$ is injection and $gcolon Ato B$ is surjective, can we prove there is a bijection as well?