# If $f:A\to B\subseteq A$ is injective, then there exists a bijection $h:A\to B$

Please check whether my proof has any error! Thank you so much!

Theorem:

If $$f:A\to B\subseteq A$$ is injective, then there exists a bijection $$h:A\to B$$.

Proof:

Let $$Y=A \setminus B$$, and $$X=\bigcup_{i\in \mathbb{N}}f^i(Y)$$ where $$f^i(Y)=f(f(...f(Y)...)), i$$ times.

$$f(X)=f(\bigcup_{i \in \mathbb{N}}f^i(Y))=\bigcup_{i \in \mathbb{N}}f(f^i(Y))=\bigcup_{i \geq1}f^i(Y)$$.

$$X=\bigcup_{i \in \mathbb{N}}f^i(Y) = f^0(Y) \cup (\bigcup_{i \geq1}f^i(Y))=Y \cup (\bigcup_{i \geq1}f^i(Y))=Y \cup f(X)$$.

To sum sup, $$X=Y \cup f(X)$$.

$$A \setminus X=(Y\cup B) \setminus (Y\cup f(X))=B \setminus f(X)$$.

We define $$h:A\to B$$ such that $$h(x)=f(x)$$ for all $$x \in X$$, and $$h(x)=x$$ for all $$x \in A \setminus X$$, then $$h$$ is bijective.

• Compare with math.stackexchange.com/questions/1877323/… – Robert Z Apr 13 '18 at 5:28
• @RobertZ I'm still unable to figure out why the OP in that link need to prove $X$ is a union of disjoint sets. Could you please explain this difference? – LE Anh Dung Apr 13 '18 at 8:42
• Your final $h$ is a bijection from $A$ to $B$ iff $f$ is injective in $X$ (trivial) and $f(X)=B\setminus (A\setminus X)$. If you show it your proof is fine. – Robert Z Apr 13 '18 at 11:30
• Did you mean that I used $(Y\cup B) \setminus (Y\cup f(X))=B \setminus f(X)$ without giving proof for this identity? If so, here is my proof for that identity: $(Y\cup B) \setminus (Y\cup f(X))=((Y\cup B) \setminus Y) \cap ((Y\cup B) \setminus f(X))=B \cap ((Y\cup B) \setminus f(X))=(B \cap (Y\cup B)) \setminus f(X)=(B \cap A) \setminus f(X)=B\setminus f(X)$. – LE Anh Dung Apr 13 '18 at 12:58
• @RobertZ, I have presented a detail proof here math.stackexchange.com/questions/2735694/…, can you have a look at it and give some comments? – LE Anh Dung Apr 15 '18 at 4:57

Since $f:A \to B$ is injective, this implies that $|A| \leq |B|$. Now, since $B \subset A$, this implies that $|B| \leq |A|$. Combining these two inequalities, we have that $|A| =|B|$. Then, since $f$ is an injection, it is also a surjection and hence a bijection.
• The Cantor–Bernstein theorem is the way to prove that $|A|\leq|B|$ and $|B|\leq|A|$ implies $|A|=|B|$. So as remarked by @egreg, this is entirely unhelpful as it would be circular. Unless, of course, you have a better way of proving that $\leq$ is antisymmetric on the cardinals. – Asaf Karagila Apr 13 '18 at 11:04