# Schroeder-Bernstein theorem, proof of

We first prove as a lemma that for any $B\subset A$, if there is an injection $f:A\to B$, then there is also a bijection $h:A\to B$.

Inductively define a sequence $({C}_{n})$ of subsets of $A$ by ${C}_{0}=A\setminus B$ and ${C}_{n+1}=f({C}_{n})$. Now let $C={\bigcup}_{k=0}^{\mathrm{\infty}}{C}_{k}$, and define $h:A\to B$ by

$$h(z)=\{\begin{array}{cc}f(z),\hfill & z\in C\hfill \\ z,\hfill & z\notin C\hfill \end{array}.$$ |

If $z\in C$, then $h(z)=f(z)\in B$. But if $z\notin C$, then $z\in B$, and so $h(z)\in B$. Hence $h$ is well-defined; $h$ is
injective by construction. Let $b\in B$. If $b\notin C$, then
$h(b)=b$. Otherwise, $b\in {C}_{k}=f({C}_{k-1})$ for some $k>0$, and
so there is some $a\in {C}_{k-1}$ such that $h(a)=f(a)=b$. Thus $h$
is bijective^{}; in particular, if $B=A$, then $h$ is simply the identity
map on $A$.

To prove the theorem^{}, suppose $f:S\to T$ and $g:T\to S$
are injective. Then the composition^{} $gf:S\to g(T)$ is also
injective. By the lemma, there is a bijection ${h}^{\prime}:S\to g(T)$.
The injectivity of $g$ implies that ${g}^{-1}:g(T)\to T$ exists
and is bijective. Define $h:S\to T$ by $h(z)={g}^{-1}{h}^{\prime}(z)$; this
map is a bijection, and so $S$ and $T$ have the same cardinality.

Title | Schroeder-Bernstein theorem, proof of |
---|---|

Canonical name | SchroederBernsteinTheoremProofOf |

Date of creation | 2013-03-22 12:49:56 |

Last modified on | 2013-03-22 12:49:56 |

Owner | mps (409) |

Last modified by | mps (409) |

Numerical id | 19 |

Author | mps (409) |

Entry type | Proof |

Classification | msc 03E10 |

Synonym | proof of Cantor-Bernstein theorem |

Synonym | proof of Cantor-Schroeder-Bernstein theorem |

Related topic | AnInjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective |