Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
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/… –  LePressentiment Oct 30 '13 at 14:18
add comment

1 Answer

up vote 0 down vote accepted

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.