Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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:… – 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
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|cite|improve this answer

Your Answer


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.