Schröder–Bernstein theorem

In set theory, the Schröder–Bernstein theorem, named after Felix Bernstein and Ernst Schröder, states that, if there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B. In terms of the cardinality of the two sets, this means that if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|; that is, A and B are equipollent. This is a useful feature in the ordering of cardinal numbers.

The theorem is also known as the Cantor–Bernstein theorem, or the Cantor–Schroeder–Bernstein theorem (named after Georg Cantor).

This theorem does not rely on the axiom of choice. However, its various proofs are non-constructive, as they depend on the law of excluded middle, and are therefore rejected by intuitionists.

Proof

File:Cantor-Bernstein.png

König's definition of a bijection h:A→B from given example injections f:A→B and g:B→A. An element in A and B is denoted by a number and a letter, respectively. The sequence 3→e→6→... is an A-stopper, leading to the defintitions h(3)=f(3)=e, h(6)=f(6), .... The sequence d→5→f→... is a B-stopper, leading to h(5)=g⁻¹(5)=d, .... The sequence ...→a→1→c→4→... is doubly infinite, leading to h(1)=g⁻¹(1)=a, h(4)=g⁻¹(4)=c, .... The sequence b→2→b is cyclic, leading to h(2)=g⁻¹(2)=b.

The following proof is attributed to Julius König.

Assume without loss of generality that A and B are disjoint. For any a in A or b in B we can form a unique two-sided sequence of elements that are alternately in A and B, by repeatedly applying $f$ and $g$ to go right and $g^{-1}$ and $f^{-1}$ to go left (where defined).

$\cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots$

For any particular a, this sequence may terminate to the left or not, at a point where $f^{-1}$ or $g^{-1}$ is not defined.

By the fact that $f$ and $g$ are injective functions, each a in A and b in B is in exactly one such sequence to within identity: if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by the definition of the sequences. Therefore, the sequences form a partition of the (disjoint) union of A and B. Hence it suffices to produce a bijection between the elements of A and B in each of the sequences separately, as follows:

Call a sequence an A-stopper if it stops at an element of A, or a B-stopper if it stops at an element of B. Otherwise, call it doubly infinite if all the elements are distinct or cyclic if it repeats. See the picture for examples.

• For an A-stopper, the function $f$ is a bijection between its elements in A and its elements in B.
• For a B-stopper, the function $g$ is a bijection between its elements in B and its elements in A.
• For a doubly infinite sequence or a cyclic sequence, either $f$ or $g$ will do ($g$ is used in the picture).

Original proof

An earlier proof by Cantor relied, in effect, on the axiom of choice by inferring the result as a corollary of the well-ordering theorem. The argument given above shows that the result can be proved without using the axiom of choice.

Furthermore, there is a proof which uses Tarski's fixed point theorem.

History

The traditional name "Schröder-Bernstein" is based on two proofs published independently in 1898. Cantor is often added because he first stated the theorem in 1895, while Schröder's name is often omitted because his proof turned out to be flawed while the name of Richard Dedekind, who first proved it, is not connected with the theorem. According to Bernstein, Cantor had suggested the name equivalence theorem (Äquivalenzsatz).

File:CantorEquivalenceTheorem1887b.gif

Cantor's first statement of the theorem (1887)

• 1887 Cantor publishes the theorem, however without proof.
• 1887 On July 11, Dedekind proves the theorem (not relying on the axiom of choice) but neither publishes his proof nor tells Cantor about it. Ernst Zermelo discovered Dedekind's proof and in 1908 he publishes his own proof based on the chain theory from Dedekind's paper Was sind und was sollen die Zahlen?
• 1895 Cantor states the theorem in his first paper on set theory and transfinite numbers. He obtains it as an easy consequence of the linear order of cardinal numbers. However, he couldn't prove the latter theorem, which is shown in 1915 to be equivalent to the axiom of choice by Friedrich Moritz Hartogs.
• 1896 Schröder announces a proof (as a corollary of a theorem by Jevons).
• 1896 Schröder publishes a proof sketch which, however, is shown to be faulty by Alwin Reinhold Korselt in 1911 (confirmed by Schröder).
• 1897 Bernstein, a 19 years old student in Cantor's Seminar, presents his proof.
• 1897 Almost simultaneously, but independently, Schröder finds a proof.
• 1897 After a visit by Bernstein, Dedekind independently proves the theorem a second time.
• 1898 Bernstein's proof (not relying on the axiom of choice) is published by Émile Borel in his book on functions. (Communicated by Cantor at the 1897 International Congress of Mathematicians in Zürich.) In the same year, the proof also appears in Bernstein's dissertation.

Both proofs of Dedekind are based on his famous memoir Was sind und was sollen die Zahlen? and derive it as a corollary of a proposition equivalent to statement C in Cantor's paper, which reads A ⊆ B ⊆ C and |A|=|C| implies |A|=|B|=|C|. Cantor observed this property as early as 1882/83 during his studies in set theory and transfinite numbers and therefore (implicitly) relying on the Axiom of Choice.

See also

• Myhill isomorphism theorem
• Schröder–Bernstein theorem for measurable spaces
• Schröder–Bernstein theorems for operator algebras
• Schröder–Bernstein property

References

• Proofs from THE BOOK, p. 90. ISBN 3-540-40460-0

External links

• Weisstein, Eric W., "Schröder-Bernstein Theorem", MathWorld.
• Cantor-Schroeder-Bernstein theorem in nLab

This article incorporates material from the Citizendium article "Schröder-Bernstein_theorem", which is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License but not under the GFDL.