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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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