## You are here

HomeSchroeder-Bernstein theorem, proof of

## Primary tabs

# 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}}^{\infty}C_{k}$, and define $h:A\rightarrow B$ by

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

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.

## Mathematics Subject Classification

03E10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new image: information-theoretic-distributed-measurement-dds.png by rspuzio

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia