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 Cantor–Bernstein theorem, or Cantor–Schröder–Bernstein, after Georg Cantor 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 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).

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 $$, 1to ,_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_...