Talk:Cantor–Bernstein–Schroeder theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Mid Importance
 Field: Foundations, logic, and set theory
WikiProject Citizendium Porting (Last updated: Never)
WikiProject icon This article is within the scope of WikiProject Citizendium Porting, a collaborative effort to improve Wikipedia articles by working in any useful content from their Citizendium counterparts. If you would like to participate, you can visit the project page, where you can join the project and see a list of open tasks.
 
Note icon
This article is out of date with its Citizendium counterpart and needs to be updated.
Current with its Citizendium counterpart article as of: Never

Translation of parts from german article[edit]

In the german article de:Cantor-Bernstein-Schröder-Theorem, which I translated from the english version, I added a visualization of the map h.

Someone might want to translate the image displayed at that article into english and look over this trial of a translation, and then integrate it into the english article.

Here comes my translation of the section "Veranschaulichung" in the german article.


(Before that, I added a little remark on the map h.)

Note, that this definition of h is nonconstructive, in the sense that there exists no general method to decide in finitely many steps for any given sets A, B and injections f, g, if an element x of A lies in C or not. For special sets and maps this might of course be possible.

Visualization

The definition of h can be visualized with the following diagram.

(Then the diagram) [1]

Displayed are parts of the (disjoint) sets A and B together with parts of the mappings f and g. If you interpret the set A union B together with the two maps as a directed graph, then this bipartite graph has several connected components.

These can be divided into four types: pathes extending infinitely to both directions, finite cycles of even length, infinite paths starting in the set A, and infinite paths starting in the set B (the path passing through the element a in the diagram is infinitely long into both directions, so the diagram contains one path of every type). In general it is not possible to decide in finitely many steps, what type of path a given element of A or B belongs to.

The set C defined above contains precisely the elements of A which are part of an infinite path starting in A. The map h is then defined in such a way, that for every path it yields a bijection of the elements of A onto the elements of B direct before or after it in the path. For the both-side infinite path and for the finite cycles, we choose to map every element to its predecessor in the path.


Hope this will be of use. --SirJective 10:54, 29 Oct 2003 (UTC)

Still hope someone might take a look at it... :-( --SirJective 19:36, 13 Jun 2004 (UTC)
I now copied this section into the article (and corrected some minor mistakes). The image still needs to be translated, and I will do it as soon as someone tells me the correct english words in the context of graph theory. --SirJective 15:45, 1 Aug 2004 (UTC)

imho, "One can then check that h : A → B is the desired bijection." is not really clear. Don't you think that more details may be necessary to understand this proof ? What do you think about the french article ?

Alternative presentation[edit]

The Cantor-Berstein-Schröder theorem is one that many people find difficult to understand intuitively. At present, I think the sketch proof is not quite as clear as it could be, and the helpful diagram is not used as effectively as it could be. How about this presentation, formalising the intuitive approach which provides a more complete proof that is well illustrated by the diagram?

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 alternatively 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.
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).
By the above observation, the sequences form a partition of the whole 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.
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. (unsigned post from User:Elroch circa Feb 2006).
Great presentation! Finally I understood this proof. 88.152.251.205 16:34, 18 March 2006 (UTC)
In the "definition" of the sequence we might in fact (be able to) go right applying f or g^{-1}; and go left via f^{-1} or g: no uniqueness so far. Martin Ziegler (talk) —Preceding undated comment added 07:44, 27 September 2013 (UTC)
I've used your proof in the Hebrew Wikipedia. 88.152.251.205 12:29, 25 March 2006 (UTC)
I am very pleased that you found this of use, and appreciate your feedback. Elroch 01:22, 27 March 2006 (UTC)
this argument is actually from Julius König.Kope 16:06, 2 September 2006 (UTC)
I would be surprised indeed if no-one had taken this route before! Thanks for identifying to whom credit is due for discovering it. Elroch (talk) 20:34, 4 April 2010 (UTC)
I am now pretty sure that my proof is based on what I was taught in 1979, but more complete. It's been rather a long time since I took or looked at the lecture notes though! Elroch (talk) 09:41, 13 April 2010 (UTC)
Why can we assume the sets are disjoint? What if they aren't? - Sikon (talk) 12:55, 25 May 2011 (UTC)
If A and B were identical, then the identity map on A would be a bijection between them. Thus we may assume they are distinct. Clearly
\{ \langle a, \langle a, A \rangle  \rangle \vert a \in A \}
is a bijection between A and A×{A}. Similarly, there is a bijection between B and B×{B}. Notice that the sets A×{A} and B×{B} are disjoint because
 \langle a, A \rangle \neq \langle b, B \rangle
follows from AB. f and g can be modified to go between these disjoint sets and then one proceeds as above. Finally, the resulting bijection h can be modified to go between the initial sets A and B. JRSpriggs (talk) 18:28, 25 May 2011 (UTC)

A supershort proof hiding infinite steps[edit]

There is a supershort proof that goes like this:

Let A and B be sets and f:A->B and g:B->A be functions. Then there is a subset A0 of B such that g(B-f[A0])=A-A0. If f and g are injective, it follows immediatly that h(x)=f(x) for x in A0 and else h(x)=g−1(x) is a bijection.

This proof has the virtue of avoiding infinite steps. The infinite steps are needed though in proving the first assertion. (Sry bout my mathematical syntax. I have only notepad ;) —The preceding unsigned comment was added by YohanN7 (talkcontribs) 18:59, 30 March 2007 (UTC).

alternative proof[edit]

I have an alternative proof which does not involve the use of inverse functions. I don't know whether it is worth adding to the article. I'd also need some help attributing the proof to the right source. I think it is from Boolos and Jeffrey's Computability and Logic... —Preceding unsigned comment added by 137.205.8.2 (talkcontribs)

Variants with surjectivity[edit]

What about variants of the theorem with injectivity replaced by surjectivity? There are two such variants: one with an injection and a surjection in the same direction, and one with surjections in opposite direction. Can they proved without AC as well? —Preceding unsigned comment added by 131.174.22.39 (talk) 17:28, 19 February 2009 (UTC)

I do not know, but I suspect that AC is necessary in the case where both are surjections. JRSpriggs (talk) 13:25, 20 February 2009 (UTC)
Indeed, you need to "invert" functions, so that mere surjectivity entails choices for the inverse : you have to choose one element in the inverse image of the element you're interested in, hence you need to do infinite choices, hence you need AC.
I don't know if one can easily prove that AC is needed, given that this form of "Cantor-Bernstein" doesn't seem to be equivalent to AC (I don't see how to build surjections without using AC), therefore one would need to exhibit a model of ZF where it is not satisfied, which can be hard, since it is not trivial for AC. Samuel Bach

Lead with the König proof?[edit]

I tried to follow the first proof and my head started to spin, but I found the second proof very straightforward and pleasing. Is there any reason not to lead with the simpler proof, and move the harder one into a subsection? ciphergoth (talk) 22:08, 28 April 2009 (UTC)

Title of theorem[edit]

Is it really true that most sources use Cantor's name in the title? Most of the sources I've seen personally (and most of the first few Google hits for "Schroeder Bernstein") and most of the math people with whom I've spoken have actually just said Schroeder-Bernstein. I don't have any source that proclaims one to be more common than the other, though. But maybe the title should be changed to reflect what appears to me to be common practice. 207.207.126.206 (talk) 00:06, 5 August 2009 (UTC)

General idea[edit]

I've tried to make the proof "natural", which happens to repeat the second proof, and shows the link with the first (although perhaps not clearly in what I've written). The difficulty is that it is quite clear on a picture (there are chains going to infinity, starting from "lonely" points, which are points with no arrow ending at them, and chains infinite on both sides, for which one can choose any orientation of arrows), but less so in English. Also, my English might be slightly unsatisfactory... If someone could draw a picture, or/and make the explanations clearer, I think it could help visualize the proof quite easily. --Samuel Bach (talk) 16:28, 23 April 2010 (UTC)

I agree my first attempted contribution was quite unnecessary and poorly written. However, I think it could be useful to point out the link between the two proofs of the article : elements of C_n are the nth elements of A-stoppers. What do you think? Furthermore, I would like to know how to write "A" the same way as in the article. Thank you.--Samuel Bach (talk) 16:10, 24 April 2010 (UTC)

Generally, I use the editor to look at the source in order to see how to generate a particular symbol or version of a letter (then use the back-up button to exit). Find an example of what you want to write and look at the source for it. If you are talking about how to italicize a letter, it is done by putting doubled single-quotes around the letter. Tripled single-quotes generate bold-face. See Help:Displaying a formula for additional information. JRSpriggs (talk) 23:45, 24 April 2010 (UTC)

Thank you. That is what I tried, but I saw double quotation marks instead of two single quotation marks, hence my mistake. What do you think of my proposal to explain why the two proofs of the article are the same (simply with a sentence like that above)?--Samuel Bach (talk) 16:20, 25 April 2010 (UTC)

I think it might be useful for you to show how the two proofs are related.
To maximize the chance of your changes being accepted (without an edit-war), I would suggest that: (1) you make small (minimal) changes; and (2) you wait a day or two after each change for it to be accepted (or modified or rejected) before making another change. JRSpriggs (talk) 18:41, 25 April 2010 (UTC)

Set-based proof?[edit]

This is from Willard (General Topology, problem 1J, 1970).

Let A be a set, P(A) the power set of A.

If F:P(A) → P(A) is a function such that whenever C ⊆ D ⇒ F(C) ⊆ F(D), then there exists E such that E = F(E). Proof: Let E = ∪{ C ⊆ A : C ⊆ F(C) }. Claim: E = F(E). Let x ∈ E. Then x ∈ C for some C such that C ⊆ F(C) ⊆ F(E). Hence, E ⊆ F(E). E ⊆ F(E) ⇒ F(E) ⊆ F(F(E)) ⇒ F(E) = C such that C ⊆ F(C) for some C ⇒ F(E) ⊆ E.


Cantor-Bernstein: If A and B are sets and f:A → B and g:B → A are injective functions, then there exists h:A → B such that h is bijective. Proof: Define F:P(A) → P(A) as F(C) = A - g(B - f(C)). F preserves subsets from above, so there exists E such that E = F(E). Define h:A → B by h(x) = f(x) for x ∈ E and h(x) = g-1(x) for x ∉ E —Preceding unsigned comment added by Quagmirede (talkcontribs) 07:31, 30 April 2011 (UTC)

Article name[edit]

OK, here's something that has bothered me about this article for years, and I finally decided, why not bring it up? Not making it a formal requested move, yet; just sounding people out.

I've always known this result as the Schröder–Bernstein theorem, no Cantor. I honestly think that's the more common usage; I don't ever recall coming across this three-part name, other than on Wikipedia.

First, let me say that I yield to no one in my admiration for Cantor, one of my great mathematical heroes. Nor do I have any problem with the axiom of choice; I'm perfectly willing to say that AC is just plain true.

But. The Cantor version of the proof (using the wellordering principle, from Cantor's viewpoint, or the axiom of choice as we see it post-Zermelo) is completely different in character from the piecing-together-a-bijection proof that I've always associated with the name Schröder–Bernstein theorem. The Cantor version is really just the "law of trichotomy" for cardinal numbers. The importance of the Schröder–Bernstein proof is that the result holds even in contexts where trichotomy does not.

So really, I would prefer to move this to Schröder–Bernstein theorem (not being too picky about the umlaut-o versus oe), both on the grounds above and on WP:COMMONNAME grounds, with a mention of Cantor and a link to law of trichotomy to explain that, arguably somewhat distinct, result. --Trovatore (talk) 08:42, 13 December 2013 (UTC)

I have never heard it called by any other name than Schröder–Bernstein theorem, and would prefer that as the article title. —Kusma (t·c) 10:13, 13 December 2013 (UTC)
+1 — Arthur Rubin (talk) 14:05, 13 December 2013 (UTC)
It will always be Schroder-Bernstein for me, but I am a bit of a traditionalist in these matters. Bill Cherowitzo (talk) 14:34, 13 December 2013 (UTC)
I did a few Google searches and found Cantor–Bernstein–Schroeder, Cantor–Bernstein and Schroeder–Bernstein all appearing fairly often. Schroeder–Bernstein was used in what I thought were the more authoritative sources, e.g. Halmos' Naive Set Theory (book). The root problem is that there are really two theorems: AC → (m≤n≤m iff m=n) which would be Cantor's theorem if the name weren't taken already, and (m≤n≤m iff m=n) independent of AC which (so I gather) would be the Schroeder–Bernstein theorem. But based on the common usage criterion it appears that Schroeder–Bernstein would be the best name for the article. --RDBury (talk) 20:06, 13 December 2013 (UTC)
By the way, some information on the history of this theorem is available here (collected by Peter Schmitt). Boris Tsirelson (talk) 18:50, 14 December 2013 (UTC)
So it should really be the Dedekind-Cantor-Schröder-Bernstein-Dedekind-(Borel) theorem :) --RDBury (talk) 19:59, 14 December 2013 (UTC)
Indeed! It reminds me Talk:Carathéodory's_extension_theorem#Attribution:_Carath.C3.A9odory_or_not.3F Likewise, windows (on the display) are invented not by Microsoft, nor by Apple. :-) Boris Tsirelson (talk) 20:15, 14 December 2013 (UTC)

84308389072347345 trillion aeons ago in infancy I learned that this is called the Schröder–Bernstein theorem. I think around that time I also encountered the phrase "Cantor–Bernstein theorem". Michael Hardy (talk) 00:17, 15 December 2013 (UTC)

I too learned it as Schröder–Bernstein. I had a suspicion this might have come about through some remixing of the theorem statement, and it looks like RDBury's research confirmed that above. Considering that most people only expect the Schröder–Bernstein version, it seems like the best outcome would be to retitle this page to Schröder–Bernstein and mention the alternative names in the lead. Rschwieb (talk) 14:59, 16 December 2013 (UTC)
I agree with this. I checked a few other well-known textbooks beyond Halmos (namely, Lang, Algebra; Munkres, Topology). All call it the Schröder–Bernstein theorem, sometimes with oe instead of ö, and this is also what I learned to call it. I would prefer the umlaut version, assuming that that is how Schröder wrote his own name. Ebony Jackson (talk) 04:47, 17 December 2013 (UTC)

Merging History section with de.wikipedia[edit]

I have merged the section Cantor–Bernstein–Schroeder theorem#History with the german article de:Satz von Cantor-Bernstein-Schröder#Geschichte, including as much open-access URLs and providing as much particular page numbers as I could find out. I suggest to replace the current version of section "History" by the merge result, or by a further improved version of it. - Jochen Burghardt (talk) 16:30, 2 February 2014 (UTC)

***** START OF MERGING RESULT *********************************************************************************************

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

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

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,[6] 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.

References

  1. ^ 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)
  2. ^ 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
  3. ^ Richard Dedekind (1932), Robert Fricke, Emmy Noether, Øystein Ore, ed., Gesammelte mathematische Werke 3, Braunschweig: Friedr. Vieweg & Sohn, pp. 447–449 (Ch.62) 
  4. ^ 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 
  5. ^ Richard Dedekind (1888), Was sind und was sollen die Zahlen? (2., unchanged (1893) ed.), Braunschweig: Friedr. Vieweg & Sohn 
  6. ^ a b Georg Cantor (1932), Adolf Fraenkel (Lebenslauf); Ernst Zermelo, ed., Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Berlin: Springer, pp. 285 ("Satz B") 
  7. ^ 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. )
  8. ^ 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 
  9. ^ 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) 
  10. ^ 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 
  11. ^ p.295
  12. ^ 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 
  13. ^ a b Patrick Suppes (1972), Axiomatic Set Theory (1. ed.), New York: Dover Publications, pp. 95 f., ISBN 0-486-61630-4 
  14. ^ Émile Borel (1898), Leçons sur la théorie des fonctions, Paris: Gauthier-Villars et fils, pp. 103 ff. 
  15. ^ 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 


***** END OF MERGING RESULT *********************************************************************************************

Looks good! Boris Tsirelson (talk) 17:20, 2 February 2014 (UTC)
Moved to the article's section today. - Jochen Burghardt (talk) 16:48, 12 March 2014 (UTC)