View source for Talk:Schröder–Bernstein theorem

{{WikiProject banner shell|class=C|
{{WikiProject Citizendium Porting|cztitle=Schröder-Bernstein theorem|date=Never|outdated=yes}}
{{WikiProject Mathematics|importance=mid}}
}}

==Translation of parts from german article==

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)''
[http://de.wikipedia.org/wiki/Bild:Cantor-Bernstein.png]

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. --[[User:SirJective|SirJective]] 10:54, 29 Oct 2003 (UTC)

:Still hope someone might take a look at it... :-( --[[User:SirJective|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. --[[User:SirJective|SirJective]] 15:45, 1 Aug 2004 (UTC)
----
imho, "One can then check that h : A &#8594; 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 ==
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 ''<math>f</math>'' and ''<math>g</math>'' to go right and ''<math>g^{-1}</math>'' and ''<math>f^{-1}</math>'' to go left (where defined). 

::''<math> \cdots \rightarrow  f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow   a  \rightarrow  f(a) \rightarrow  g(f(a)) \rightarrow \cdots </math>''

:For any particular ''a'', this sequence may terminate to the left or not, at a point where ''<math>f^{-1}</math>'' or ''<math>g^{-1}</math>'' 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 ''<math>f</math>'' and ''<math>g</math>'' 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 a set|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 ''<math>f</math>'' is a bijection between its elements in ''A'' and its elements in ''B''.

:For a ''B-stopper'', the function ''<math>g</math>'' is a bijection between its elements in ''B'' and its elements in ''A''.

:For a ''doubly infinite'' sequence or a ''cyclic'' sequence, either ''<math>f</math>'' or ''<math>g</math>'' will do. (unsigned post from [[User:Elroch]] circa Feb 2006).

::Great presentation! Finally I understood this proof. [[User:88.152.251.205|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 ''<math>f</math>'' or ''<math>g^{-1}</math>''; and go left via ''<math>f^{-1}</math>'' or ''<math>g</math>'': no uniqueness so far. [[User:Martin Ziegler|Martin Ziegler]] ([[User talk:Martin Ziegler|talk]])  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|undated]] comment added 07:44, 27 September 2013 (UTC)</span><!--Template:Undated--> <!--Autosigned by SineBot-->
::I've used your proof in the [[he:משפט קנטור שרדר ברנשטיין|Hebrew Wikipedia]]. [[User:88.152.251.205|88.152.251.205]] 12:29, 25 March 2006 (UTC)
:::I am very pleased that you found this of use, and appreciate your feedback. [[User:Elroch|Elroch]] 01:22, 27 March 2006 (UTC)
:: this argument is actually from [[Julius König]].[[User:Kope|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. [[User:Elroch|Elroch]] ([[User talk: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! [[User:Elroch|Elroch]] ([[User talk:Elroch|talk]]) 09:41, 13 April 2010 (UTC)
: Why can we assume the sets are disjoint? What if they aren't? - [[User:Sikon|Sikon]] ([[User talk: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
:::<math>\{ \langle a, \langle a, A \rangle  \rangle \vert a \in A \} </math>
::is a bijection between ''A'' and ''A''&times;{''A''}. Similarly, there is a bijection between ''B'' and ''B''&times;{''B''}. Notice that the sets ''A''&times;{''A''} and ''B''&times;{''B''} are disjoint because
:::<math> \langle a, A \rangle \neq \langle b, B \rangle </math>
::follows from ''A''≠''B''. ''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''. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 18:28, 25 May 2011 (UTC)

== A supershort proof hiding infinite steps ==

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 ;) <small>—The preceding [[Wikipedia:Sign your posts on talk pages|unsigned]] comment was added by [[User:YohanN7|YohanN7]] ([[User talk:YohanN7|talk]] • [[Special:Contributions/YohanN7|contribs]]) 18:59, 30 March 2007 (UTC).</small><!-- HagermanBot Auto-Unsigned -->

== alternative proof ==

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... <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:137.205.8.2|137.205.8.2]] ([[User talk:137.205.8.2|talk]] • [[Special:Contributions/137.205.8.2|contribs]]) </span></small><!-- Template:Unsigned -->

== Variants with surjectivity ==

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?  <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/131.174.22.39|131.174.22.39]] ([[User talk:131.174.22.39|talk]]) 17:28, 19 February 2009 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:I do not know, but I suspect that AC is necessary in the case where both are surjections.  [[User:JRSpriggs|JRSpriggs]] ([[User talk: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. [[User:Samuel Bach|Samuel Bach]]

: Exercise 8.6 in PT Johnstone's Notes On Logic And Set Theory walks you through a demonstration that if every well-orderable set of reals is countable, then there are sets M, N such that M can be injected into N, surjected onto N, but not bijected with N. [[User:Bat020|Bat020]] ([[User talk:Bat020|talk]]) 12:30, 28 December 2014 (UTC)

: If there is an injection and a surjection but no bijection X->Y, then it gives a counterexample to the Generalized Continuum Hypothesis (GCH), as Y cannot be in bijection with the power set of X by Cantor's theorem. [[User:GeoffreyT2000|GeoffreyT2000]] ([[User talk:GeoffreyT2000|talk]]) 04:37, 26 February 2015 (UTC)

== Lead with the König proof? ==

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? [[User:Ciphergoth|ciphergoth]] ([[User talk:Ciphergoth|talk]]) 22:08, 28 April 2009 (UTC)

== Title of theorem ==

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. [[Special:Contributions/207.207.126.206|207.207.126.206]] ([[User talk:207.207.126.206|talk]]) 00:06, 5 August 2009 (UTC)

==General idea==
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. --[[User:Samuel Bach|Samuel Bach]] ([[User talk: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.--[[User:Samuel Bach|Samuel Bach]] ([[User talk: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. [[User:JRSpriggs|JRSpriggs]] ([[User talk: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)?--[[User:Samuel Bach|Samuel Bach]] ([[User talk: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. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 18:41, 25 April 2010 (UTC)

== Set-based proof? ==

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<sup>-1</sup>(x) for x ∉ E  <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Quagmirede|Quagmirede]] ([[User talk:Quagmirede|talk]] • [[Special:Contributions/Quagmirede|contribs]]) 07:31, 30 April 2011 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

== Article name ==

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. --[[User:Trovatore|Trovatore]] ([[User talk: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. —'''[[User:Kusma|Kusma]]''' ([[User talk:Kusma|t]]·[[Special:Contributions/Kusma|c]]) 10:13, 13 December 2013 (UTC)
::+1 — [[User:Arthur Rubin|Arthur Rubin]]  [[User talk: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. [[User:Wcherowi|Bill Cherowitzo ]] ([[User talk:Wcherowi|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. --[[User:RDBury|RDBury]] ([[User talk:RDBury|talk]]) 20:06, 13 December 2013 (UTC)

:::::By the way, some information on the history of this theorem is available [http://en.citizendium.org/wiki/Schroeder-Bernstein_theorem#History here] (collected by Peter Schmitt). [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 18:50, 14 December 2013 (UTC)
::::::So it should really be the Dedekind-Cantor-Schröder-<s>Bernstein</s>-Dedekind-(Borel) theorem :) --[[User:RDBury|RDBury]] ([[User talk: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. :-) [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|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". [[User:Michael Hardy|Michael Hardy]] ([[User talk: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. [[User:Rschwieb|Rschwieb]] ([[User talk: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. [[User:Ebony Jackson|Ebony Jackson]] ([[User talk:Ebony Jackson|talk]]) 04:47, 17 December 2013 (UTC)
:::OK, let's move it, already.  We aren't interested in the name reflecting the history, but only in the name reflecting what it's really called.  (I prefer the umlaut, also, even though I may not type it.)  The only problem I see is that we have a disambiguation page at [[Schroeder–Bernstein theorem]], not all of which are related to this theorem.  — [[User:Arthur Rubin|Arthur Rubin]]  [[User talk:Arthur Rubin|(talk)]] 01:54, 4 May 2014 (UTC)
::::{{done}} - page moved. That has left a lot of double redirects, but a bot should fix them within a few hours. i will check tomorrow that it has. [[User:JohnCD|JohnCD]] ([[User talk:JohnCD|talk]]) 17:57, 26 October 2014 (UTC)

== Merging History section with de.wikipedia ==


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. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk: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'' (&Auml;quivalenzsatz).<ref name="Brieskorn.Chatterji.2002">{{cite | author=[[Felix Hausdorff]] | editor=[[Egbert Brieskorn]], Srishti D. Chatterji et.al. | title=Grundzüge der Mengenlehre | edition=1. | publisher=Springer | location=Berlin/Heidelberg | year=2002 | pages=587 | ISBN=3-540-42224-2| url=http://books.google.de/books?id=3nth_p-6DpcC}} - [https://jscholarship.library.jhu.edu/handle/1774.2/34091 Original edition (1914)]</ref>

[[File:CantorEquivalenceTheorem1887b.gif|thumb|right|Cantor's first statement of the theorem (1887)<ref name="Cantor.1932"/>]]

* '''1887''' '''Cantor''' publishes the theorem, however without proof.<ref name="Cantor.1932">{{cite | author=Georg Cantor | title=Mitteilungen zur Lehre vom Transfiniten |journal=[[Zeitschrift für Philosophie und philosophische Kritik]]| volume=91 |pages=81-125 |year=1887 }}<BR>Reprinted in: {{cite | author=Georg Cantor | editor=Adolf Fraenkel (Lebenslauf); Ernst Zermelo | title=Gesammelte Abhandlungen mathematischen und philosophischen Inhalts| publisher= Springer | location=Berlin | year=1932 | pages=378–439 | url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN237853094&DMDID=DMDLOG_0060}} Here: p.413 bottom</ref><ref name="Brieskorn.Chatterji.2002"/>
* '''1887''' On July 11, '''Dedekind''' proves the theorem (not relying on the [[axiom of choice]])<ref>{{cite | author=Richard Dedekind | editor=Robert Fricke, Emmy Noether, Øystein Ore | title=Gesammelte mathematische Werke | volume=3 | publisher=Friedr. Vieweg & Sohn | location=Braunschweig | year=1932 | pages=447–449 (Ch.62) | url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN23569441X}}</ref> but does neither publish it nor tell it to Cantor. [[Ernst Zermelo]] discovered Dedekind's proof and published in 1908<ref>{{cite | author=Ernst Zermelo | editor=Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal | title=Untersuchungen über die Grundlagen der Mengenlehre I | journal=[[Mathematische Annalen]] | volume=65 | number=2 | publisher=B.&nbsp;G. Teubner | location=Leipzig | year=1908 | pages=261–281; here: p.271-272 | ISSN=0025-5831 | url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235181684_0065&DMDID=DMDLOG_0018 }}</ref> a proof based on the ''chain theory'' from Dedekind's paper ''Was sind und was sollen die Zahlen?''<ref>{{cite | author=Richard Dedekind | title=Was sind und was sollen die Zahlen? | publisher=Friedr. Vieweg & Sohn | location=Braunschweig | year=1888 | url=http://echo.mpiwg-berlin.mpg.de/MPIWG:01MGQHHN |edition=2., unchanged (1893)}}</ref><ref name="Brieskorn.Chatterji.2002"/>
* '''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.<ref name="Cantor.1895">{{cite | author=Georg Cantor | editor=Adolf Fraenkel (Lebenslauf); Ernst Zermelo | title=Gesammelte Abhandlungen mathematischen und philosophischen Inhalts | publisher= Springer | location=Berlin | year=1932 | pages=285 ("Satz B")| url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN237853094}}</ref><ref>{{cite journal |author=Georg Cantor |title=Beiträge zur Begründung der transfiniten Mengenlehre (1) |url=http://gdz.sub.uni-goettingen.de/index.php?id=img&no_cache=1&IDDOC=36218&IDDOC=36218&branch=&L=1|journal=[[Mathematische Annalen]] |volume=46 | |page=481-512 (Theorem see "Satz B", p.484) |year=1895}}<BR>({{cite journal |author=Georg Cantor |title=Beiträge zur Begründung der transfiniten Mengenlehre (2) |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0049&DMDID=DMDLOG_0024&L=1 |journal=[[Mathematische Annalen]] |volume=49 |page=207-246 |year= 1897}})</ref> 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]].<ref>{{cite | author=Friedrich M. Hartogs | editor=Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal | title=Über das Problem der Wohlordnung | journal=[[Mathematische Annalen]] | volume=76 | number=4 | publisher=B.&nbsp;G. Teubner | location=Leipzig | year=1915 | pages=438–443 | ISSN=0025-5831 |url=http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0076&DMDID=DMDLOG_0037&L=1}}</ref><ref name="Brieskorn.Chatterji.2002"/>
* '''1896''' '''Schröder''' announces a proof (as a corollary of a more general statement).<!---taken from 31 Jan 2014 version of [[:en:Cantor–Bernstein–Schroeder theorem#History]], without further sources--->
* '''1896''' '''Schröder''' publishes a proof sketch<ref>{{cite | author=Ernst Schröder | editor=Kaiserliche Leopoldino-Carolinische Deutsche Akademie der Naturforscher | title=Ueber zwei Definitionen der Endlichkeit und G. Cantor’sche Sätze | journal=Nova Acta | volume=71 | number=6 | publisher=Johann Ambrosius Barth Verlag | location=Halle a.&nbsp;S. | year=1898 | pages=303–376 (proof: p.336) | url=http://www.biodiversitylibrary.org/item/45265#page/331/mode/1up}}</ref> which, however, is shown to be faulty by [[Alwin Reinhold Korselt]] in 1911<ref>{{cite | author=Alwin R. Korselt | editor=Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal | title=Über einen Beweis des Äquivalenzsatzes | journal=[[Mathematische Annalen]] | volume=70 | number=2 | publisher=B.&nbsp;G. Teubner | location=Leipzig | year=1911 | pages=294–296 | ISSN=0025-5831 | url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235181684_0070&DMDID=DMDLOG_0029}}</ref> (confirmed by Schr&ouml;der).<ref>p.295</ref><ref name="Brieskorn.Chatterji.2002"/>
* '''1897''' '''Bernstein''', a 19 years old student in Cantor's Seminar, presents his proof.<ref name="Deiser.2010">{{cite | author=Oliver Deiser | title=Einführung in die Mengenlehre - Die Mengenlehre Georg Cantors und ihre Axiomatisierung durch Ernst Zermelo | edition=3rd, corrected | publisher=Springer | location=Berlin/Heidelberg | year=2010 | pages=71, 501 | ISBN=3-540-20401-6 | DOI=10.1007/978-3-642-01445-1}}</ref><ref name="Suppes.1972">{{cite | author=[[Patrick Suppes]] | title=Axiomatic Set Theory | edition=1. | publisher=Dover Publications | location=New York | year=1972 | pages=95&nbsp;f. | ISBN=0-486-61630-4 }}</ref>
* '''1897''' Almost simultaneously, but independently, '''Schröder''' finds a proof.<ref name="Deiser.2010"/><ref name="Suppes.1972"/>
* '''1897''' After a visit by Bernstein, '''Dedekind''' independently proves the theorem a second time.<!---taken from 31 Jan 2014 version of [[:en:Cantor–Bernstein–Schroeder theorem#History]], without further sources--->
* '''1898''' '''Bernstein''''s proof (not relying on the axiom of choice) is published by [[Émile Borel]] in his book on functions.<ref>{{cite | author=Émile Borel | title=Leçons sur la théorie des fonctions | publisher=Gauthier-Villars et fils | location=Paris | year=1898 | pages=103&nbsp;ff. | url=http://archive.org/stream/leconstheoriefon00borerich#page/n115/mode/2up}}</ref> (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.<ref>{{cite | author=Felix Bernstein | title=Untersuchungen aus der Mengenlehre | publisher=Buchdruckerei des Waisenhauses | location=Halle a.&nbsp;S. | year=1901 | url=http://www.archive.org/details/untersuchungena00berngoog}}<BR>Reprinted in: {{cite | author=Felix Bernstein | editor=Felix Klein, Walther von Dyck, David Hilbert | title=Untersuchungen aus der Mengenlehre | journal=[[Mathematische Annalen]] | volume=61 | number=1 | publisher=B.&nbsp;G. Teubner | location=Leipzig | year=1905 | pages=117–155, (Theorem see "Satz 1" on p.121) | ISSN=0025-5831  | url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN235181684_0061&DMDID=DMDLOG_0015}}</ref><ref name="Brieskorn.Chatterji.2002"/>

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,<ref name="Cantor.1895"/> 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]].<!---taken from 31 Jan 2014 version of [[:en:Cantor–Bernstein–Schroeder theorem#History]], without further sources--->

'''References'''
{{reflist}}


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

: Looks good! [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 17:20, 2 February 2014 (UTC)

:: Moved to the article's section today. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 16:48, 12 March 2014 (UTC)

== Doubts of 1.52.104.114 ==

About "citation needed" in Sect. "Proof": ''A'' and ''B'' may be made disjoint by a well-known simple trick: we consider <math>A \times \{1\} = \{ (a,1) : a \in A \}</math> instead of ''A''; we use the evident bijective correspondence between ''A'' and <math>A \times \{1\};</math> and similarly, <math>B \times \{2\} = \{ (b,2) : b \in B \}</math> instead of ''B''; these new sets are disjoint.

About "citation needed" in the lead: the proof mentioned above does not use the choice axiom.

[[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 20:33, 22 November 2016 (UTC)

== History ==
There are some problems with this section (but with many interesting references and links anyway).

The proof of Schröder with is shown faulty by Korselt is the one published in 1898 (and sent in 1896). There is no other proof in 1897 : Schröder aknowledges (in a letter to Korselt, may 1902, see Korselt paper)  "Daß ich Herrn F. Bernstein die Ehre, den G. Cantorschen Satz bewiesen zu haben, allein überlasse, hatte ich einstweilen einem Freunde desselben, Herrn Dr. Max Dehn (jetzt in Münster) schon vorigen Herbst resp. Sommer -- natürlich zum Weitergeben -- gesagt" (that is Bernstein is the only one to be credited for the proof, and he says that to a friend in 1901, Schröder died in june 1902).
 
Deiser (given as reference) does not say anything about Schröder and the theorem p 501 (and in other pages too) ! Suppes (1972) is not reliable on historical matters (it was overlooked a long time that Schröder's proof was faulty). All that is known today (see for instance [http://www.tandfonline.com/doi/abs/10.1080/01445340412331313602 this review] (p 164) by [[William W. Tait]]).

<s>The "Proof sketch" of 1896 : the only given reference is Schröder 1898 (manuscript sent in 1896), nothing about this proof sketch and about Jevons, it seems to me.</s>

Zermelo sent his proof to Poincaré in 1906 (who published a translation), no evidence that he knew Dedekind's proof at this time, and even in 1908,  Deiser p 501 says the opposite (and other historians too). [[User:Proz|Proz]] ([[User talk:Proz|talk]]) 20:55, 1 February 2017 (UTC)

== Clarification from Wolfram ==

Hi,
the 2nd link on the page when I searched for this was Wolfram and it said 

"The Schröder-Bernstein theorem for numbers states that if n<=m<=n, then m=n"

To put this at the top and say "the equivalent for sets involves their sizes" (or perhaps something a bit more rigorous) would make this immediately understandable and intuitive for me. It's been 30 years since I did injective/bijective funcs, so the lead-in description left me floundering.

[[Special:Contributions/79.75.109.121|79.75.109.121]] ([[User talk:79.75.109.121|talk]]) 18:10, 26 November 2017 (UTC)

== Intuitionistic rejection ==

(from the same guy who posted chunk immediately above).
I only recently came across intuitionist logic and as someone with a background in classical logic, it was a very strange thing... but anyway. 

In the article it says "However, its various proofs are non-constructive, as they depend on the law of excluded middle, and are therefore rejected by intuitionists".

If we consider only finitely-sized sets then could you not ask an intuitionist to provide a counterexample? Isn't the onus on them to support their claim in this limited domain? 

[[Special:Contributions/79.75.109.121|79.75.109.121]] ([[User talk:79.75.109.121|talk]]) 18:15, 26 November 2017 (UTC)

:For intuitionists, some things are true for finite sets which they do not consider to be true for infinite sets. And I suspect that may be so in this case. In any event, since they reject the excluded middle as a general proposition, they would not feel that merely failing to accept the truth of Schröder–Bernstein is the same as believing it to be false. So they would not accept the onus of giving a counter-example. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 22:38, 26 November 2017 (UTC)

== On "Statement C and a transparent proof" ==

A couple of days ago, I added the small section on Statement C and a transparent proof. 
This proof is for the ''one-sided version'' of the Schröder-Bernstein Theorem, where the second injection is the identity and (hence) the second set a subset of the first one. That this trivially implies the general form is also shown.
The one-sided proof can be found by translating a proof (either Tarski-Knaster or König - which really is only Tarski-Knaster in disguise) for the general case to this situation, but that was not how I found it. Rather, it imposes itself via two well-known examples. The first one is the so-called ''Hilbert Hotel'': the set of all natural numbers (including 0) is equipollent with the set of positive natural numbers. The second one is the fact that the closed unit interval [0,1] of the reals is equipollent with the half-open one [0,1), with the number 1 left out. Solutions for these cases straightforwardly generalise to the general case, which, I think, is more or less trivial once you understand these examples.
I now stumbled upon the french wiki page for the theorem (there called the Cantor-Bernstein Theorem). To my surprise, three proofs are presented. Next to the one using the Tarski-Knaster fixpoint-trick (to which this page only offers a link) and the König proof, there is the one-sided version that I had just added here. (I'm told now that the polish wiki has two proofs: from the three, it leaves out König.)
August 11, 2018. [[User:KeesDoe|KeesDoe]] ([[User talk:KeesDoe|talk]]) 08:43, 11 August 2018 (UTC)

:I just initiated [[Wikipedia_talk:WikiProject_Mathematics#Schröder–Bernstein_theorem:_OR_or_not?|a discussion on wikiproject math]]. [[User:Tsirel|Boris Tsirelson]] ([[User talk:Tsirel|talk]]) 10:18, 11 August 2018 (UTC)

The German wiki ("Satz von Cantor-Bernstein-Schröder") has the proof I have added, be it in the completely general setting (with two sets and two injections) which makes it unnecessarily harder to understand than the proof of the special case (with one set and one injection). By way of explanation, it offers the König argument. The picture that goes with it has been copied to the presentation here! Which explains the origin of the mysterious set ''C'': it makes perfectly good sense in the German exposition but, here, ''C'' remains an unexplained mystery. [[User:KeesDoe|KeesDoe]] ([[User talk:KeesDoe|talk]]) 18:13, 21 August 2018 (UTC)

== The "alternate" proof should be kept ==

There was an "alternate" proof https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem#Alternate_proof which was added 14th January by "Dunloskinbeg"
but deleted on 29 Jan by Jochen Burghardt. 

I found this "alternate" proof very clear and convenient for generalizing it from sets to ∞-groupoids (https://homotopytypetheory.org/2020/01/26/the-cantor-schroder-bernstein-theorem-for-%e2%88%9e-groupoids). This reference has a proof in mathematical vernacular, and also a proof formalized in a proof assistant and verified by it. I didn't need to check any reference to make complete sense of it. I would like this proof to be reinstated (with a citation for it, if possible), so that my citation to it still makes sense. No further details for the proof are needed. It may be laconic, but it does have all the necessary information. And I like it very much, much better than the proof that produces three equivalence classes. This proof with two equivalence classes is much better and direct and intuitive. Thank you.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/31.185.241.7|31.185.241.7]] ([[User talk:31.185.241.7#top|talk]]) 20:03, 10 February 2020 (UTC)</small> <!--Autosigned by SineBot-->

:For convenience, I include below the section I deleted. I found it hard to understand (this might be a matter of presentation, and thus fixable); after the reference "derived from Halmos" was added, I read the (German translation of) the cited book, and found Halmos' proof a slight variant of König's. This was my reason to delete it. - As for the formally verified proof, I agree with 31.185.241.7 that it's a good idea to mention it. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 10:10, 11 February 2020 (UTC) 

 ***** Begin of deleted text *****

'''Alternate proof'''

'''Statement'''    If there is a one-to-one mapping ''f'' from A into B, and a one-to-one mapping ''g'' from B into A, then there is a one-to-one mapping ''h'' from A '''onto''' B.


'''Proof'''    We construct ''h'' by taking ''f'' for some of the points in A, and ''g'' <sup>-1</sup> for the others.  

We may suppose there are points in A and not in ''g''(B), else ''g'' is onto.

Take a point ''a'' in A – ''g''(B) and form the sequence ''a'', ''f'' (''a''), ''g''(''f'' (''a'')), ''f'' ''(g''(''f'' (''a''))), . . .of points belonging alternately to A and B.  Call these points ‘sequence points’.

Form similar sequences beginning with '''all''' points in A – ''g''(B).

Define ''h'' = ''f'' for all sequence points in A.

The remaining points of A are in ''g''(B) so for them we can define ''h'' = ''g'' <sup>-1</sup>. 

To verify that ''h'' is a 1-1 mapping we need to check that the image of a sequence point cannot coincide with the image of a non-sequence point.

Suppose therefore that ''a''<sub>s</sub> is  a sequence point and ''a''<sub>n</sub> is a non-sequence point and that ''f'' (''a''<sub>s</sub>) = ''g'' <sup>-1</sup>(''a''<sub>n</sub>).

It follows that  ''g''(''f'' (''a''<sub>s</sub>)) = ''g''(''g'' <sup>-1</sup>(''a''<sub>n</sub>)).  But the LHS is a sequence point in A while the RHS is just the non-sequence point ''a''<sub>n</sub>  — a contradiction.

Next we show that ''h'' is onto.  Consider any ''b'' in B then : 

Case 1     if ''b'' is a sequence point, then ''f''<sup>  -1</sup>(''b'') exists and is a sequence point.  Hence ''h'' = ''f'' maps ''f''<sup>  -1</sup>(''b'') to ''b.'' 

Case 2     if ''b'' is not a sequence point then neither is ''g''(''b'').

Hence ''h'' = ''g'' <sup>-1</sup> maps ''g''(''b'') to ''b''.    ∎ <ref>derived from  [[Paul Halmos|Halmos, Paul]], ''[[Naive Set Theory (book)|Naive Set Theory]]''. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by [[Springer-Verlag]], New York, 1974. {{ISBN|0-387-90092-6}} (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. {{ISBN|978-1-61427-131-4}} (Paperback edition).</ref>
{{reflist}}

 ***** End of deleted text *****

I am the same person as 31.185.241.7 and the author of the blog post cited in this discussion. I do not mean for a link to the blog post or the formalizationi to be added. On the contrary, I had added a link to the now-deleted proof here from that blog post. Now the proof the blog post points to doesn't exist any more on Wikipedia. The proof in the blog post generalizes the particular proof that was deleted (which seems to be due to Halmos, according to the above discussion).  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/147.188.200.83|147.188.200.83]] ([[User talk:147.188.200.83#top|talk]]) 13:44, 11 February 2020 (UTC)</small> <!--Autosigned by SineBot-->

I guess that "hard" is a matter of taste. I personally found the alternative proof more intuitive and easier to understand that the adopted one by Koenig. Given that (1) the alternative proof is short and rigorous, and (2) sufficient motivation was given using Koenig's formulation, couldn't we keep the alternative proof as it was, with an attribution to Halmos added? In my view it doesn't harm having different presentations of the same idea with different levels of detail. Some proofs work better for some people, and other proofs (or reformulations of the same proof) work better for other people. I strongly vote to reinstate the "alternate" proof as it was formulated originally, with an added reference to Halmos as above, as you suggest.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/31.185.241.7|31.185.241.7]] ([[User talk:31.185.241.7#top|talk]]) 17:43, 11 February 2020 (UTC)</small> <!--Autosigned by SineBot-->

Will it be OK if I revert the last change and add the reference to Halmos given above by Jochen Burghardt? Thanks.  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/31.185.241.7|31.185.241.7]] ([[User talk:31.185.241.7#top|talk]]) 19:13, 12 February 2020 (UTC)</small> <!--Autosigned by SineBot-->

I am quitting this discussion, for lack of response, and unwillingness to engage with the issue, and a determination by the Wikipedia editors to just delete useful material on their own determination. I don't find this environment conductive to constructive progress, and, given that information in a Wikipedia page just comes and goes, it is not a reliable place to refer to as a source of mathematical information (which includes not just facts, but different proofs of the same facts that the mathematical community considers useful, not only for understanding, but for generalization - not all proof of the same fact are suitable for generalization).  <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/31.185.241.7|31.185.241.7]] ([[User talk:31.185.241.7#top|talk]]) 21:22, 13 February 2020 (UTC)</small> <!--Autosigned by SineBot-->

:Archeological findings: this was the first proof from 2003 (https://en.wikipedia.org/w/index.php?title=Schr%C3%B6der%E2%80%93Bernstein_theorem&oldid=584997):

::Here is a proof [due to Eilenberg?]:

::Let

:::<math>C_0=A\setminus g[B]</math>,

::and

:::<math>C_{n+1}=g[f[C_n]]</math>

::and

:::<math>C=\bigcup_{n=0}^\infty C_n.</math>

::Then for <math>x\in A</math> let

::<math>
h(x)=\left\{
\begin{matrix}
f(x) & \mbox{if }x\in C \\  \\
g^{-1}(x) & \mbox{if }x\not\in C
\end{matrix}
\right.
</math>

::Then ''h'' is the desired bijection.

:I find it to be the easiest to follow of all presented here or in the history of the page. Unlike the current König proof it has no weasel words, no multiple cases, no bidirectional sequences of individual elements, etc... It is also rather similar to the version from Hrbacek & Jech Introduction to Set Theory (1999).

:It was later amended with superfluous 'intuitive' explanations, and in parallel König's proof was added to the page. In 2010 [[User:Ciphergoth]], whose unanswered comment is still here at the top, unilaterally swapped the two with the pretext that König's is simpler. Over the course of a decade the first proof was edited to be even less readable, and even more resembling the König one.

:IMO the original proof should be reinstated. [[User:Ybungalobill|bungalo]] ([[User talk:Ybungalobill|talk]]) 00:58, 18 December 2020 (UTC)

::You would have to show that ''h'' is, in fact, a bijective function. When you think about how that would have to be done, it is not simpler than the other proofs. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 20:48, 20 December 2020 (UTC)

== explicit reference to standard notion needed ==

This theorem establishes the anti-symmetry property for cardinality. Anti-symmetry is a cardinal (pun intended) notion within Set Theory, and should be explicitly acknowledged when it occurs. If I do a google search for 'anti-symmetry of cardinality' I should get a hit on this article.
 
Here's the link to a site that does what I'm suggesting:
 
https://www.whitman.edu/mathematics/higher_math_online/section04.09.html [[User:Kontribuanto|Kontribuanto]] ([[User talk:Kontribuanto|talk]]) 11:54, 23 February 2024 (UTC)

: I just performed the google search for "anti-symmetry of cardinality", and found only one hit (https://www.scribd.com/document/520363930/Mathematics-Mind-Map). Apparently nobody uses this term literally, not even the article at whitman.edu you cited. - [[User:Jochen Burghardt|Jochen Burghardt]] ([[User talk:Jochen Burghardt|talk]]) 15:29, 23 February 2024 (UTC)