# How do I prove that this function is injective?

Suppose for one $B\subset A$, there is an injection $f: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}$$ Prove that $h$ is injective.

• What seems to be the problem? – Shahab Sep 10 '15 at 14:20
• @shahab: I'm new to Set theory and so I don't know how to deal with functions with two definitions. – Sisabe Sep 10 '15 at 14:26
• The start should be: “Suppose that for one $B\subset A$”. – egreg Sep 10 '15 at 15:03

If $c\in C$ then $c\in C_n$ for some integer and consequently $f(c)\in C_{n+1}\subseteq C$.

Let $a,b\in A$ with $a\neq b$.

It is enough to prove that $h(a)\neq h(b)$.

The injectivity of $f$ tells us that $f(a)\neq f(b)$.

Discern the following cases:

1) $a,b\notin C$. Then: $h(a)=a\neq b=h(b)$

2) $a\notin C$ and $b\in C$. Then $h(a)=a\notin C$ and $h(b)=f(b)\in C$ so $h(a)\neq h(b)$

3) $a\in C$ and $b\notin C$. Then $h(a)=f(a)\in C$ and $h(b)=b\notin C$ so $h(a)\neq h(b)$

4) $a,b \in C$. Then $h(a)=f(a)\neq f(b)=h(b)$

In 2) and 3) it was used that $c\in C\implies f(c)\in C$