2
$\begingroup$

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

  • 0
    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.2014-05-19

1 Answers 1

0

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

  • 1
    "Let $y \in B$. If $y \notin B$ ..."? I guess you mean "if $y \in B \setminus E$"?. But for this case I have one question. Why do I know that then $h(y)=y$? Of course if $x \in B \setminus E$ then also $y=x \in B \setminus E$, but there could be more points in $B \setminus E$ ... I mean $f$ could also send points to $B \setminus E$?2017-10-30