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.

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 monotone, 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 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}}$

$\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}$

$\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₁:

$A\setminus (g_{\ast }(B\setminus f_{\ast }(A_{1})))=\sigma (A_{1})=A_{1}=A\setminus (A\setminus A_{1})$

$\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:

$A_{1},\qquad A_{2}:=A\setminus A_{2},\qquad B_{1}:=f_{\ast }(A_{1}),\qquad B_{2}:=B\setminus B_{1}$

that has the desired properties: