# Lemma required for Cantor-Bernstein-Schroeder Theorem

Let $A$ and $B$ bet sets such that $A \subseteq B$. If there is an injective function $f: B \rightarrow A$, then there is a bijective function $h:B \rightarrow A$.

I understand how to prove this except up to a certain point. We define a subset $E$ of $B$ and a function $h$ such that $h=f$ on $E$ and $h=\text{ identity }$ elsewhere. So the function is as follows: $$h(x) = \begin{cases} f(x)&\mathrm{\ if\ }x\in E\\ x&\mathrm{\ if\ }x\in B\setminus E. \end{cases}$$ There are also these following facts: (i) $f(E)\subseteq E$ amd (ii) $B\setminus E \subseteq B \setminus E_0 = A$.

There is a sequence of sets $E_{n+1}=f(E_n)$ for all n=0, 1, 2, 3, 4,...etc. Furthermore $E = \cup E_n$. I'm not sure if the immediately previous sentence is necessary as I was informed only the two enumerated facts were required.

My understanding of the problem is as follows. By how we defined $h$ we get that it is injective for free since it behaves like an injective function on $E$ and the identity function elsewhere. The only part I am stuck on is how to prove that $h(x)$ is onto. Specifically with regards to $h(x)$ when its on $E$.

-
I edited your definition of $h$ to use \begin{cases}. I guess tha's what you meant – Hagen von Eitzen Sep 11 '12 at 15:59
Thanks. I tried using \begin{displaymath} but that didn't work. – emka Sep 11 '12 at 16:12
@LePressentiment: I must disagree. The other question simply asks for proof of this Lemma, and all answers to that effect simply use CBS Theorem. This question is in regards to proving a particular aspect of this Lemma, which will in turn be used to prove CBS Theorem, so while the subject is the same, the focus and purpose is not. – Cameron Buie Oct 29 '13 at 8:09
@CameronBuie: Admittedly, you're right! I'll just link to it: math.stackexchange.com/questions/121225/… – Timere Oct 30 '13 at 14:18
It seems that in the suggested proof there are some typos. The first B should be A and the second E. The second sentence should be replaced by "Now n cannot be $0$ because $A=B\setminus E_0$." The last sentence is OK. – Arik May 19 '14 at 12:01

Let $y\in B$. If $y\notin B$ then $h(y)=y$. But if $y\in E$ then $y\in E_n$ for some $n\in \mathbb N_0$. If $n=0$ then $y\in E_0=f(B)$ implies that $y=f(x)$ for some $x\in B$. if $n>0$ then $y\in E_n=f(E_{n-1})$ implies $y=f(x)$ for some $x\in E_{n-1}$.