Schröder–Bernstein theorem

In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions and between the sets and , then there exists a bijective function .

In terms of the cardinality of the two sets, this classically implies that if and , then ; that is, and are equipotent.
This is a useful feature in the ordering of cardinal numbers.

The theorem is named after Felix Bernstein and Ernst Schröder.
It is also known as the Cantor–Bernstein theorem or Cantor–Schröder–Bernstein theorem, after Georg Cantor, who first published it (albeit 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 functions.)
: ''$\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 of the (disjoint) union of ''A'' and ''B''. Hence it suffices to produce a bijection between the elements of ''A'' and ''B'' in each of the sequences separately, as follows:

Call a sequence an ''A-stopper'' if it stops at an element of ''A'', or a ''B-stopper'' if it stops at an element of ''B''. Otherwise, call it ''doubly infinite'' if all the elements are distinct or ''cyclic'' if it repeats. See the picture for examples.
* For an ''A-stopper'', the function ''$f$'' is a bijection between its elements in ''A'' and its elements in ''B''.
* For a ''B-stopper'', the function ''$g$'' is a bijection between its elements in ''B'' and its elements in ''A''.
* For a ''doubly infinite'' sequence or a ''cyclic'' sequence, either ''$f$'' or ''$g$'' will do ($g$ is used in the picture).

Corollary for surjective pair

If we assume the axiom of choice, then a pair of surjective functions $f$ and $g$ also implies the existence of a bijection. We construct an injective function from $f^$ by picking a single element from the inverse image of each point in $B.$ The surjectivity of $f$ guarantees the existence of at least one element in each such inverse image. We do the same to obtain an injective function from $g^.$ The Schröder-Bernstein theorem then can be applied to the injections ''h'' and ''k''.

Examples

; Bijective function from $$, 1to[0, 1 ) :
: ''Note: $[0, 1 )$ is the half open set from 0 to 1, including the boundary 0 and excluding the boundary 1.''
: Let $f:$, 1to[0, 1) with $f(x)=x/2 ;$ and $g: [0, 1 )\to$, 1 with $g(x)=x ;$ the two injective functions.
: 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$, 1\smallsetminus C\end is a bijective function from $$, 1to[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 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) but neither publishes his proof nor tells Cantor about it. Ernst Zermelo discovered Dedekind's proof and in 1908 he publishes his own proof based on the ''chain theory'' from Dedekind's paper ''Was sind und was sollen die Zahlen?''
* 1895 Cantor states the theorem in his first paper on set theory and transfinite numbers. He obtains it as an easy consequence of the linear order of cardinal numbers.() However, he could not prove the latter theorem, which is shown in 1915 to be equivalent to the axiom of choice by Friedrich Moritz Hartogs.
* 1896 Schröder announces a proof (as a corollary of a theorem by Jevons).
* 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 in his book on functions. (Communicated by Cantor at the 1897 International Congress of Mathematicians in Zürich.) In the same year, the proof also appears in Bernstein's dissertation.
* 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 and implies . 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.

Prerequisites

The 1895 proof by Cantor relied, in effect, on the axiom of choice by inferring the result as a corollary of the well-ordering theorem. 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 to draw a conclusion through case analysis. As such, the above proof is not a constructive one. In fact, in a constructive set theory such as intuitionistic set theory $$, which adopts the full axiom of separation but dispenses with the principle of excluded middle, assuming the Schröder–Bernstein theorem implies the latter. In turn, there is no proof of König's conclusion in this or weaker constructive theories. Therefore, intuitionists do not accept the statement of the Schröder–Bernstein theorem.

There is also a proof which uses Tarski's fixed point theorem. Example 3.

See also

* Myhill isomorphism theorem
* Netto's theorem, 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 & Gunter M. Ziegler (1998) Proofs from THE BOOK, § 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