Schröder–Bernstein theorem

In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B.

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

The theorem is named after Ernst Schröder and Felix Bernstein. 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

{\displaystyle f}

and

g

−

1

{\displaystyle g^{-1}}

to go from A to B and

g

{\displaystyle g}

and

f

−

1

{\displaystyle f^{-1}}

to go from B to A (where defined; the inverses

f

−

1

{\displaystyle f^{-1}}

and

g

−

1

{\displaystyle g^{-1}}

are understood as partial functions.)

⋯

→

f

−

1

(

g

−

1

(

a

)

)

→

g

−

1

(

a

)

→

a

→

f

(

a

)

→

g

(

f

(

a

)

)

→

⋯

{\displaystyle \cdots \rightarrow f^{-1}(g^{-1}(a))\rightarrow g^{-1}(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

−

1

{\displaystyle f^{-1}}

or

g

−

1

{\displaystyle g^{-1}}

is not defined.

By the fact that

f

{\displaystyle f}

and

g

{\displaystyle 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.