Schroeder-Bernstein theorem, proof of

We first prove as a lemma that for any $B\subset A$, if there is aninjection $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

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$ isinjective 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$, andso 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 identitymap 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 alsoinjective. 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$ existsand is bijective. Define $h:S\to T$ by $h(z)=g^{-1}{h}^{\prime }(z)$; thismap is a bijection, and so $S$ and $T$ have the same cardinality.