Schröder-Bernstein theorem

The Schröder-Bernstein theorem (sometimes Cantor-Schröder-Bernstein theorem) is a fundamental theorem of set theory. Essentially, it states that if two sets are such that each one has at least as many elements as the other then the two sets have equally many elements. Though this assertion may seem obvious it needs a proof, and it is crucial for the definition of cardinality to make sense.

Remark: In analogy to this theorem the term Schröder-Bernstein property is used in other contexts to describe similar properties.

The Schröder-Bernstein theorem

Theorem. If for two sets A and B there are an injective function from A into B and an injective function from B into A then there is a bijective function from A onto B.

In terms of cardinal numbers this is equivalent to:

Corollary. If |A| ≤ |B| and |B| ≤ |A| then |A| = |B|.

Here |A| and |B| denote the cardinal numbers corresponding to the sets A and B.
The corollary shows that ≤ is a partial order for cardinal numbers. (The order is indeed a linear order, but this aspect is not touched by the theorem since the existence of injective functions between the two sets is assumed in its statement.)

Remark. It is of theoretical interest that the proof of the theorem does not depend on the Axiom of Choice.

History

As it is often the case in mathematics, the name of this theorem does not truly reflect its 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 1895, while Schröder's name is often omitted because his proof turned out to be flawed while the name of the mathematician who first proved it is not connected with the theorem.

Georg Cantor (1895) states the theorem (B.)

In reality, the history was more complicated:

• 1887 Richard Dedekind proves the theorem but does not publish it.
• 1895 Georg Cantor states the theorem in his first paper on set theory and transfinite numbers (as an easy consequence of the linear order of cardinal numbers which he was going to prove later).
• 1896 Ernst Schröder announces a proof (as a corollary of a more general statement).
• 1897 Felix Bernstein, a young student in Cantor's Seminar, presents his proof.
• 1897 After a visit by Bernstein, Dedekind independently proves it a second time.
• 1898 Bernstein's proof is published by Émile Borel in his book on functions. (Communicated by Cantor at the 1897 congress in Zürich.)

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:

$A\subset B\subset C\quad {\textrm {and}}\quad |A|=|C|\qquad \Rightarrow \qquad |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.

Proof

The bijective function between the two sets can be explicitly constructed from the two injective functions given. Therefore the Axiom of Choice is not needed in the proof. (There are many versions of the proof.)

Outline

We denote by f the injective function from A to B, and by g the injective function from B to A.

The proof is based on a simple observation:
If A is the disjoint union of two sets, A₁ and A₂, and B the disjoint union of two sets, B₁ and B₂, such that B₁ is the image of A₁ under f and A₂ is the image of B₂ under g then a bijection from A onto B is obtained by taking f on A₁ and g⁻¹ on A₂.

Such a dissection is characterized by the property that the following process, if performed on A₁, gives A₁ as a result. (Thus A₁ is a fixed point.)

Take a subset of A, find its image under f in B, take the complement, find its image under g in A, and, finally, take the complement.

This defines a mapping of subsets of A to subsets of A that is increasing, and such a mapping always has a fixed point.

Proof

By assumption, there are injective functions

$f:A\to B\quad {\text{and}}\quad g:B\to A$

They induce two (injective) image mappings between the power sets

$f_{\ast }:{\mathcal {P}}(A)\to {\mathcal {P}}(B)\quad {\text{and}}\quad g_{\ast }:{\mathcal {P}}(B)\to {\mathcal {P}}(A)$

The mapping

$\sigma (S):=A\setminus g_{\ast }(B\setminus f_{\ast }(S))\quad (S\subset A)$

on the power set of A is monotone increasing

$S_{1}\subset S\subset A\Rightarrow \sigma (S_{1})\subset \sigma (S)$

and

$A_{1}:=\bigcap \{\sigma (S)\mid \sigma (S)\subset S\subset A\}$

is a fixed point of σ

$\sigma (A_{1})=A_{1}$

Thus the function h defined as

$h(a):={\begin{cases}f(a)&a\in A_{1}\\g^{-1}(a)&a\in A\setminus A_{1}\\\end{cases}}$

is a bijective function between A and B.

Details

(1) Recalling the definition of the image of a set under a function, the induced image mappings are

$f_{\ast }(S):=\{f(s)|s\in S\}\quad (S\subset A)\quad {\text{and}}\quad g_{\ast }(T):=\{g(t)|t\in T\}\quad (T\subset B)$

(2) σ is a monotone increasing function on the power set of A:

$S_{1}\subset S\Rightarrow f_{\ast }(S_{1})\subset f_{\ast }(S)\Rightarrow B\setminus f_{\ast }(S_{1})\supset B\setminus f_{\ast }(S)$

$\Rightarrow g_{\ast }(B\setminus f_{\ast }(S_{1}))\supset g_{\ast }(B\setminus f_{\ast }(S))$

$\Rightarrow \sigma (S_{1}):=A\setminus (g_{\ast }(B\setminus f_{\ast }(S_{1})))\subset A\setminus (g_{\ast }(B\setminus f_{\ast }(S)))=:\sigma (S)$

(3) Any monotone increasing function on a power set has a fixed point A₁:

$\sigma (A)\in {\mathcal {A}}:=\{\sigma (S)\mid \sigma (S)\subset S\subset A\}\Rightarrow {\mathcal {A}}\not =\emptyset$

$(\forall \sigma (S)\in {\mathcal {A}})A_{1}\subset \sigma (S)\subset S\Rightarrow \sigma (A_{1})\subset \sigma ^{2}(S)\subset \sigma (S)\in {\mathcal {A}}$

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Rightarrow \sigma (A_1) \subset \bigcap \mathcal A = A_1 \Rightarrow \sigma(A_1) \in \mathcal A \Rightarrow \sigma (A_1) \supset \bigcap \mathcal A = A_1 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Rightarrow \sigma (A_1) = A_1 }

(4) h is well-defined and injective because f and g are injective and g⁻¹ is defined on the complement of A₁:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \setminus ( g_\ast ( B \setminus f_\ast (A_1) ) ) = \sigma (A_1) = A_1 = A \setminus ( A \setminus A_1 ) }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Rightarrow g_\ast ( B \setminus f_\ast (A_1) ) = A \setminus A_1 }

Moreover, this also shows that h is bijective because it follows that the image of A under h is

$f_{\ast }(A_{1})\cup g^{-1}(A\setminus A_{1})=f_{\ast }(A_{1})\cup (B\setminus f_{\ast }(A_{1}))=B$

In other words, A₁ induces a decomposition of A and B as described in the outline of the proof:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1 , \qquad A_2 := A \setminus A_1 , \qquad B_1 := f_\ast (A_1) , \qquad B_2 := B \setminus B_1 }

that has the desired properties.