Schröder–Bernstein theorem
   HOME

TheInfoList



OR:

In
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, the Schröder–Bernstein theorem states that, if there exist
injective function In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
s and between the sets and , then there exists a
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
function . In terms of the
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
of the two sets, this classically implies that if and , then ; that is, and are
equipotent In mathematics, two sets or classes ''A'' and ''B'' are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from ''A'' to ''B'' such that for every element ''y'' of ''B'', the ...
. This is a useful feature in the ordering of
cardinal number In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. Th ...
s. The theorem is named after Felix Bernstein and Ernst Schröder. It is also known as Cantor–Bernstein theorem, or Cantor–Schröder–Bernstein, after
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  â€“ January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...
who first published it without proof.


Proof

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 from ''A'' to ''B'' and g and f^ to go from ''B'' to ''A'' (where defined; the inverses f^ and g^ are understood as
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
s.) :'' \cdots \rightarrow f^(g^(a)) \rightarrow g^(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^ or g^ 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 Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...
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 In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called t ...
'' 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).


Another proof

Let f: A\to B and g: B\to A be the two injective functions. Then define the sets: C_0 = A \setminus g(B)\quad and \quad C_ = g(f(C_k)) for k \in \ and finally \quad C = \bigcup_^\infty C_k Now \; h(x) := \begin f(x), & \mathrm\ x \in C \\g^(x), & \mathrm\ x \in A\setminus C\end\quad defines a bijective function \quad h: A\to B\quad. For the proof let's first observe that g(f(C))= g(f( \bigcup_^\infty C_k)) = \bigcup_^\infty g(f(C_k)) = \bigcup_^\infty C_ = \bigcup_^\infty C_k * h is indeed a function: If x \in C\subset A \quad then h(x)=f(x) \in B\quad and if \quad x\in A\setminus C \subset A\setminus C_0 = g(B)\quad then \quad h(x)=g^(x) exists and is one element from the set B since g: B\to A is injective. * h is injective: Assume h(x_1)=h(x_2) ** If x_1, x_2 \in C then h(x_1)=f(x_1)=f(x_2)=h(x_2) and hence x_1=x_2 as f is injective. ** and if x_1, x_2 \in A\setminus C then g^(x_1)=g^(x_2) that implies g(g^(x_1))=x_1=x_2=g(g^(x_2)) ** x_1 \in C, x_2 \in A\setminus C is impossible since h(x_1)=h(x_2) would mean f(x_1)=g^(x_2) and hence x_2=g(g^(x_2))=g(f(x_1)) \in g(f(C)) = \bigcup_^\infty C_k \subset C (!) And for x_2 \in C, x_1 \in A\setminus C one gets also a contradiction. * h is surjective: Let y \in B ** if y \in f(C) then there is a x \in C with h(x)=f(x)=y ** if y \in B\setminus f(C) then g(y) \notin g(f(C)) since g is injective. Now g(y) \notin g(f(C))= \bigcup_^\infty C_k but g(y)\in g(B) and hence g(y) \notin C_0=A\setminus g(B). So together g(y)\notin C and therefore h(g(y))=g^(g(y))=y\quad So x=g(y) has the property h(x)=y. Et fini. (Thanks to the German and French Wikipedia sister articles, see for instance :fr:Théorème de Cantor-Bernstein#Première démonstration).


Examples

;Bijective function from
, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
to ,_1_ The_comma__is_a_punctuation_mark_that_appears_in_several_variants_in_different_languages._It_has_the_same_shape_as_an_apostrophe_or_single_closing_quotation_mark_()_in_many_typefaces,_but_it_differs_from_them_in_being_placed_on_the_baseline_(t_...
to[0,_1_)\;__with__f(x)=x/2_;\;_and_g:_[0,_1_)\to_,_1_ The_comma__is_a_punctuation_mark_that_appears_in_several_variants_in_different_languages._It_has_the_same_shape_as_an_apostrophe_or_single_closing_quotation_mark_()_in_many_typefaces,_but_it_differs_from_them_in_being_placed_on_the_baseline_(t_...
;__with__g(x)=x_;_\;_the_two_injective_functions_as_in_the_#Another_proof.html" ;"title=", 1 ) :''Note: [0, 1 ) is the half open set from 0 to 1, including the boundary 0 and excluding the boundary 1.'' :Let f:
, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
to[0, 1 )\; with f(x)=x/2 ;\; and g: [0, 1 )\to
, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
; with g(x)=x ; \; the two injective functions as in the #Another proof">previous procedure of proof. :In line with that procedure C_0=\, \; C_k=\, \; C = \bigcup_^\infty C_k = \ :Then \; h(x) = \begin \frac , & \mathrm\ x \in C \\x , & \mathrm\ x \in [0; 1] \setminus C\end \; is a bijective function from
, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...
to[0, 1 ). ;Bijective function from [0, 2 ) \to [0, 1 )^2 :Let f: [0, 2 ) \to [0, 1 )^2\; with f(x)=(x/2; 0) ;\; :Then for (x;y) \in [0, 1 )^2\; one can use the expansions \;x= \sum_^\infty a_k\cdot 10^\; and \;y= \sum_^\infty b_k\cdot 10^\; with \;a_k, b_k \in \\; :and now one can set g(x;y) = \sum_^\infty (10\cdot a_k+ b_k)\cdot 10^ which defines an injective function [0, 1 )^2 \to [0, 2)\;. (Example: g(\tfrac; \tfrac) = 0.363636...= \tfrac) :And therefore there a bijective function h can be constructed with the use of f(x) and g^(x). :In this case C_0=[1, 2 ) is still easy but already C_1=g(f(C_0)) = g(\)\; gets quite complicated. :Note: Of course there's a more simple way by using the (already bijective) function definition g_2(x;y) = 2\cdot \sum_^\infty (10\cdot a_k+ b_k)\cdot 10^. Then C would be the empty set and h(x)=g_2^(x) for all x.


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 1887, 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). â€
Original edition (1914)
/ref> * 1887 Cantor publishes the theorem, however without proof.
Reprinted in: Here: p.413 bottom
* 1887 On July 11, Dedekind proves the theorem (not relying on the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
) but neither publishes his proof nor tells Cantor about it.
Ernst Zermelo Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic se ...
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 could not prove the latter theorem, which is shown in 1915 to be equivalent to the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
by Friedrich Moritz Hartogs. * 1896 Schröder announces a proof (as a corollary of a theorem by Jevons). * 1897 Bernstein, a 19-year-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 Félix Édouard Justin Émile Borel (; 7 January 1871 – 3 February 1956) was a French mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Math ...
in his book on functions. (Communicated by Cantor at the 1897
International Congress of Mathematicians The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU). The Fields Medals, the Nevanlinna Prize (to be rename ...
in Zürich.) In the same year, the proof also appears in Bernstein's dissertation. * 1898 Schröder publishes his proof which, however, is shown to be faulty by Alwin Reinhold Korselt in 1902 (just before Schröder's death), (confirmed by Schröder), but Korselt's paper is published only in 1911. Both proofs of Dedekind are based on his famous 1888 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 was therefore (implicitly) relying on the
Axiom of Choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
.


Prerequisites

The 1895 proof by
Cantor A cantor or chanter is a person who leads people in singing or sometimes in prayer. In formal Jewish worship, a cantor is a person who sings solo verses or passages to which the choir or congregation responds. In Judaism, a cantor sings and lead ...
relied, in effect, on the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
by inferring the result as a
corollary In mathematics and logic, a corollary ( , ) is a theorem of less importance which can be readily deduced from a previous, more notable statement. A corollary could, for instance, be a proposition which is incidentally proved while proving another ...
of the
well-ordering theorem In mathematics, the well-ordering theorem, also known as Zermelo's theorem, states that every set can be well-ordered. A set ''X'' is ''well-ordered'' by a strict total order if every non-empty subset of ''X'' has a least element under the orde ...
. However, König's proof given above shows that the result can also be proved without using the axiom of choice. On the other hand, König's proof uses the principle of
excluded middle In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontradi ...
, to do the analysis into cases, so this proof does not work in
constructive set theory Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "=" and "\in" of classical set theory is usually used, so this is not to be confused with a co ...
. Even more, no proof at all can exist from constructive set theory alone (i.e. dispensing with the principle of excluded middle), since the Schröder–Bernstein theorem implies the principle of excluded middle. Therefore,
intuitionist In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fu ...
s do not accept the theorem. There is also a proof which uses Tarski's fixed point theorem.R. Uhl,
Tarski's Fixed Point Theorem
, from ''MathWorld''–a Wolfram Web Resource, created by Eric W. Weisstein. (Example 3)


See also

*
Myhill isomorphism theorem In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of computability on a set. Myhill isomorphism theorem Sets ''A'' and ''B'' of natural nu ...
*
Netto's theorem In mathematical analysis, Netto's theorem states that continuous bijections of smooth manifolds preserve dimension. That is, there does not exist a continuous bijection between two smooth manifolds of different dimension. It is named after Eugen N ...
, according to which the bijections constructed by the Schröder–Bernstein theorem between spaces of different dimensions cannot be continuous * Schröder–Bernstein theorem for measurable spaces * Schröder–Bernstein theorems for operator algebras * Schröder–Bernstein property


Notes


References

*
Martin Aigner Martin Aigner (born February 28, 1942 in Linz) is an Austrian mathematician and professor at Freie Universität Berlin since 1974 with interests in combinatorial mathematics and graph theory. He received his Ph.D from the University of Vienna. Hi ...
& Gunter M. Ziegler (1998)
Proofs from THE BOOK ''Proofs from THE BOOK'' is a book of mathematical proofs by Martin Aigner and Günter M. Ziegler. The book is dedicated to the mathematician Paul Erdős, who often referred to "The Book" in which God keeps the most elegant proof of each mathema ...
, § 3 Analysis: Sets and functions, Springer books , fifth edition 2014 , sixth edition 2018 * *


External links

* *
Cantor-Bernstein’s Theorem in a Semiring
by Marcel Crabbé. * {{DEFAULTSORT:Schroeder-Bernstein theorem Theorems in the foundations of mathematics Cardinal numbers Articles containing proofs