Cantor–Bernstein–Schroeder theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions f : AB and g : BA between the sets A and B, then there exists a bijective function h : AB. 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 Schroeder–Bernstein theorem, the Cantor–Bernstein theorem, or the Cantor–Schroeder–Bernstein theorem.

An important feature of this theorem is that it 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 therefore rejected by intuitionists.[1]

König's definition of a bijection h:AB from given example injections f:AB and g:BA. 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-1(5)=d, …. The sequence …→a→1→c→4→… is doubly infinite, leading to h(1)=f(1)=a, h(4)=f(4)=c, …. The sequence b→2→b is cyclic, leading to h(2)=f(2)=b.

Proof[edit]

This proof is attributed to Julius König.[2]

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.

Call such a sequence (and all its elements) 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.

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, (as if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by definition). 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:

  • 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 (f is used in the picture).

Another proof[edit]

Below follows an alternative proof.[citation needed]

Idea of the proof: Redefine f in certain points to make it surjective. At first, redefine it on the image of g for it to be the inverse function of g. However, this might destroy injectivity, so correct this problem iteratively, by making the amount of points redefined smaller, up to a minimum possible, shifting the problem "to infinity" and therefore out of sight.

More precisely, this means to leave f unchanged initially on C0 := A \ g[B]. However, then every element of f[C0] has two preimages, one under f and one under g –1. Therefore, leave f unchanged on the union of C0 and C1 := g[f[C0]]. However, then every element of f[C1] has two preimages, correct this by leaving f unchanged on the union of C0, C1, and C2 := g[f[C1]] and so on. Leaving f unchanged on the countable union C of C0 and all these Cn+1 = g[f[Cn]] solves the problem, because g[f[C]] is a subset of C and no additional union is necessary.

In the alternate proof, Cn can be interpreted as the set of n-th elements of A-stoppers (starting from 0).

Indeed, C0 is the set of elements for which g−1 is not defined, which is the set of starting elements of A-stoppers, C1 is the set of elements for which f^{-1}\circ g^{-1} is defined but g^{-1}\circ f^{-1}\circ g^{-1} is not, i.e. the set of second elements of A-stoppers, and so on.

The bijection h is defined as f on C and g−1 everywhere else, which means f on A-stoppers and g−1 everywhere else, consistently with the proof below.

Proof: Define

C_0=A\setminus g[B],\qquad C_{n+1}=g[f[C_n]]\quad \mbox{ for all }n\ge 0,

and

C=\bigcup_{n=0}^\infty C_n.

Then, for every a ∈ A define


h(a)=
\begin{cases}
f(a) & \mbox{if }a\in C, \\
g^{-1}(a) & \mbox{if }a\notin C.
\end{cases}

If a is not in C, then, in particular, a is not in C0. Hence a ∈ g[B] by the definition of C0. Since g is injective, its preimage g –1(a) is therefore well defined.

It remains to check the following properties of the map h : A → B to verify that it is the desired bijection:

  • Surjectivity: Consider any b ∈ B. If b ∈ f[C], then there is an a ∈ C with b = f(a). Hence b = h(a) by the definition of h. If b ∉ f[C], define a = g(b). By definition of C0, this a cannot be in C0. Since f[Cn] is a subset of f[C], it follows that b is not in any f[Cn], hence a = g(b) is not in any Cn+1 = g[f[Cn]] by the recursive definition of these sets. Therefore, a is not in C. Then b = g –1(a) = h(a) by the definition of h.
  • Injectivity: Since f is injective on A, which comprises C, and g –1 is injective on g[B], which comprises the complement of C, it suffices to show that the assumption f(c) = g –1(a) for c ∈ C and a ∈ A \ C leads to a contradiction (this means the original problem, the lack of injectivity mentioned in the idea of the proof above, is solved by the clever definition of h). Since c ∈ C, there exists an integer n ≥ 0 such that c ∈ Cn. Hence g(f(c)) is in Cn+1 and therefore in C, too. However, g(f(c)) = g(g –1(a)) = a is not in C — contradiction.

Note that the above definition of h is nonconstructive, in the sense that there exists no general method to decide in a finite number of steps, for any given sets A and B and injections f and g, whether an element a of A does not lie in C. For special sets and maps this might, of course, be possible.

Original proof[edit]

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.[3] The argument given above[clarification needed] shows that the result can be proved without using the axiom of choice.

Furthermore, there is a simple proof which uses Tarski's fixed point theorem.[4]

History[edit]

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).[5]

Cantor's first statement of the theorem (1887)[6]
  • 1887 Cantor publishes the theorem, however without proof.[6][5]
  • 1887 On July 11, Dedekind proves the theorem (not relying on the axiom of choice)[7] but does neither publish it nor tell it to Cantor. Ernst Zermelo discovered Dedekind's proof and published in 1908[8] a proof based on the chain theory from Dedekind's paper Was sind und was sollen die Zahlen?[9][5]
  • 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.[10][11] 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.[12][5]
  • 1896 Schröder announces a proof (as a corollary of a more general statement).
  • 1896 Schröder publishes a proof sketch[13] which, however, is shown to be faulty by Alwin Reinhold Korselt in 1911[14] (confirmed by Schröder).[15][5]
  • 1897 Bernstein, a 19 years old student in Cantor's Seminar, presents his proof.[16][17]
  • 1897 Almost simultaneously, but independently, Schröder finds a proof.[16][17]
  • 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.[18] (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.[19][5]

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,[10] which reads ABC 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[edit]

Notes[edit]

  1. ^ Ettore Carruccio (2006). Mathematics and Logic in History and in Contemporary Thought. Transaction Publishers. p. 354. ISBN 978-0-202-30850-0. 
  2. ^ J. König (1906). "Sur la théorie des ensembles". Comptes rendus hebdomadaires des séances de l'Académie des sciences 143: 110–112. 
  3. ^ Georg Cantor (1895). "Beiträge zur Begründung der transfiniten Mengenlehre (1)". Mathematische Annalen 46: 481-512. 
    Georg Cantor (1897). "Beiträge zur Begründung der transfiniten Mengenlehre (2)". Mathematische Annalen 49: 207-246. 
  4. ^ R. Uhl, "Tarski's Fixed Point Theorem", from MathWorld–a Wolfram Web Resource, created by Eric W. Weisstein. (Example 3)
  5. ^ a b c d e f Felix Hausdorff (2002), Egbert Brieskorn, Srishti D. Chatterji et.al., ed., Grundzüge der Mengenlehre (1. ed.), Berlin/Heidelberg: Springer, p. 587, ISBN 3-540-42224-2  - Original edition (1914)
  6. ^ a b Georg Cantor (1887), "Mitteilungen zur Lehre vom Transfiniten", Zeitschrift für Philosophie und philosophische Kritik 91: 81–125 
    Reprinted in: Georg Cantor (1932), Adolf Fraenkel (Lebenslauf); Ernst Zermelo, ed., Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Berlin: Springer, pp. 378–439  Here: p.413 bottom
  7. ^ Richard Dedekind (1932), Robert Fricke, Emmy Noether, Øystein Ore, ed., Gesammelte mathematische Werke 3, Braunschweig: Friedr. Vieweg & Sohn, pp. 447–449 (Ch.62) 
  8. ^ Ernst Zermelo (1908), "Untersuchungen über die Grundlagen der Mengenlehre I", in Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal, Mathematische Annalen (Leipzig: B. G. Teubner) 65 (2): 261–281; here: p.271–272, ISSN 0025-5831 
  9. ^ Richard Dedekind (1888), Was sind und was sollen die Zahlen? (2., unchanged (1893) ed.), Braunschweig: Friedr. Vieweg & Sohn 
  10. ^ a b Georg Cantor (1932), Adolf Fraenkel (Lebenslauf); Ernst Zermelo, ed., Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Berlin: Springer, pp. 285 ("Satz B") 
  11. ^ Georg Cantor (1895). "Beiträge zur Begründung der transfiniten Mengenlehre (1)". Mathematische Annalen 46: 481-512 (Theorem see "Satz B", p.484). 
    (Georg Cantor (1897). "Beiträge zur Begründung der transfiniten Mengenlehre (2)". Mathematische Annalen 49: 207-246. )
  12. ^ Friedrich M. Hartogs (1915), "Über das Problem der Wohlordnung", in Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal, Mathematische Annalen (Leipzig: B. G. Teubner) 76 (4): 438–443, ISSN 0025-5831 
  13. ^ Ernst Schröder (1898), "Ueber zwei Definitionen der Endlichkeit und G. Cantor’sche Sätze", in Kaiserliche Leopoldino-Carolinische Deutsche Akademie der Naturforscher, Nova Acta (Halle a. S.: Johann Ambrosius Barth Verlag) 71 (6): 303–376 (proof: p.336) 
  14. ^ Alwin R. Korselt (1911), "Über einen Beweis des Äquivalenzsatzes", in Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal, Mathematische Annalen (Leipzig: B. G. Teubner) 70 (2): 294–296, ISSN 0025-5831 
  15. ^ p.295
  16. ^ a b Oliver Deiser (2010), Einführung in die Mengenlehre - Die Mengenlehre Georg Cantors und ihre Axiomatisierung durch Ernst Zermelo (3rd, corrected ed.), Berlin/Heidelberg: Springer, pp. 71, 501, doi:10.1007/978-3-642-01445-1, ISBN 3-540-20401-6 
  17. ^ a b Patrick Suppes (1972), Axiomatic Set Theory (1. ed.), New York: Dover Publications, pp. 95 f., ISBN 0-486-61630-4 
  18. ^ Émile Borel (1898), Leçons sur la théorie des fonctions, Paris: Gauthier-Villars et fils, pp. 103 ff. 
  19. ^ Felix Bernstein (1901), Untersuchungen aus der Mengenlehre, Halle a. S.: Buchdruckerei des Waisenhauses 
    Reprinted in: Felix Bernstein (1905), "Untersuchungen aus der Mengenlehre", in Felix Klein, Walther von Dyck, David Hilbert, Mathematische Annalen (Leipzig: B. G. Teubner) 61 (1): 117–155, (Theorem see "Satz 1" on p.121), ISSN 0025-5831 

References[edit]

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. Peter Schmitt contributed the History section to Citizendium which TakuyaMurata copied into this article.

External links[edit]