# Prove $A\subsetneq B \Rightarrow f(A)\subsetneq f(B)$ if and only if $f$ is injective.

So, it is straightforward to show that $$A\subseteq B \Rightarrow f(A)\subseteq f(B)$$. That holds for any function $$f:X\rightarrow Y$$. For arbitrary sets $$A,B\subseteq X$$. Suppose some $$a\in A$$, then also $$a\in B$$. now assume $$a\mapsto f(a)$$. We have that $$f(a)\in A$$, but since $$a\in B$$, also $$f(a)\in f(B)$$ so $$f(A)\subseteq f(B)$$. It should hold that $$f$$ is injective if and only if $$A\subsetneq B\Rightarrow f(A)\subsetneq f(B)$$. The intuition is clear, we simply cannot have any "smaller" images of sets (than sets itself), if the mapping is injective. But this is no mathematics and would very badly apply to infinite sets. Would someone provide a hint on how to go about the proper subsets and injectivity?

• There are plenty of example of $f$, $A$, $B$ where $A\subsetneq B \to f(A)\subsetneq f(B)$ and yet $f$ is not injective. E.g. $f(x)=x^2, A=\{1\}, B=\{-1,2\}$. – Henning Makholm Oct 23 '18 at 14:37
• x @Michal: And therefore $A\subsetneq B\to(\text{whatever})$ is true! – Henning Makholm Oct 23 '18 at 14:39
• @HenningMakholm What is wrong about the proofs given below? – Michal Dvořák Oct 23 '18 at 14:51
• x @Michal: They assume that one gets to choose $A$ and $B$ while proving the "only if" direction. (I suspect you meant to allow that but have forgotten to write quantifiers for $A$ and $B$ to the left of "if and only if" in your statement of what you want to prove). – Henning Makholm Oct 23 '18 at 14:54
• @HenningMakholm I think i spotted your mistake. We want this to hold for any subsets $A, B$. – Michal Dvořák Oct 23 '18 at 15:26

## 2 Answers

Suppose that $$f$$ is not injective. Then there are distinct elements $$x$$ and $$y$$ such that $$f(x)=f(y)$$. Now, take $$A=\{x\}$$ and $$B=\{x,y\}$$. Then $$A\varsubsetneq B$$, but $$f(A)=f(B)$$.

• Oh, now the $\Leftarrow$ follows from the fact that it holds for any function, right? – Michal Dvořák Oct 23 '18 at 14:33
• @MichalDvořák No. The $\Longleftarrow$ follows from taking $x,y\in X$, with $x\neq y$, taking $A=\{x\}$ and taking $B=\{x,y\}$. Then $A\varsubsetneq B$ and therefore $f(A)\varsubsetneq f(B)$. Therefore, $f(x)\neq f(y)$. – José Carlos Santos Oct 23 '18 at 14:37

Assume first that $$A\subsetneq B$$, but $$f(A)=f(B)$$ for some sets $$A$$ and $$B$$. We want to prove that $$f$$ is not injective. Take $$b\in B\setminus A$$. Since $$f(A)=f(B)$$, there exists an $$a\in A$$, such that $$f(a)=f(b)$$, and since $$b\not\in A$$, this $$a$$ must be different from $$b$$. This proves that $$f$$ is not injective.

Assume second that $$f$$ is not injective. Then we want to prove the existence of some sets $$A$$ and $$B$$, such that $$A\subsetneq B$$, but $$f(A)=f(B)$$. Since $$f$$ is not injective, there exists $$a\neq b$$, such that $$f(a)=f(b)$$. If you take $$A=\{a\}$$, and $$B=\{a,b\}$$, you obtain the desired.