Every injection yields a bijection onto its image

Stub grade: B

This page is a stub

This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:

Make sure this page is up to scratch before removing this. It should be pretty good; it'd be wrong to not mark it as a stub when it was made simply to be linked to

Statement

$\newcommand{\f}{\overline{f}}$Let $X$ and $Y$ be sets and suppose $f:X\rightarrow Y$ is any injective map between them. Then we claim that there is a map:

• $\overline{f}:X\rightarrow f(X)$ given by $\overline{f}:x\mapsto f(x)$- where $f(X)$ denotes the image of $X$ under $f$

that is a bijection between $X$ and $f(X)$ (that is to say, we claim that $\f$ is a bijection, a bijection is any map that is both injective and surjective)

Proof

We must show that $\f:X\rightarrow f(X)$ is a bijection (that means $\f$ is both injective and surjective), even though injectiveness is (even more than surjectiveness) trivial, we do it anyway. That's why this page is marked as first-year friendly

1. Injectivity of $\f:X\rightarrow f(X)$ given by $\f:x\mapsto f(x)$
   • We will take injectivity to mean: $\forall x_1,x_2\in X[\f(x_1)=\f(x_2)\implies x_1=x_2]$ (rather than other equivalent conditions documented on the injection page)
   • Let $x_1,x_2\in X$ be given
     • Suppose $\f(x_1)\ne\f(x_2)$
       • By the nature of logical implication we do not care if the RHS ($x_1=x_2$) is true or false.
         • By the principle of excluded middle $x_1=x_2$ must be true xor false, so we're done in either case.
     • Suppose $\f(x_1)=\f(x_2)$
       • In order for the implication to be true, we require that this means $x_1=x_2$
       • Notice that $\f(x_1)=f(x_1)$ and $\f(x_2)=f(x_2)$ (by definition of $\f$)
       • As $f:X\rightarrow Y$ was injective itself, this means:
         • $\forall x_1,x_2\in X[\f(x_1)=\f(x_2)\implies x_1=x_2]$
       • By hypothesis, $\f(x_1)=\f(x_2)$ so $f(x_1)=f(x_2)$
         • This means that $x_1=x_2$ by injectivity of $f$
       • So $\f(x_1)=\f(x_2)\implies f(x_1)=f(x_2)\implies x_1=x_2$ (then by transitivity of implies $\f(x_1)=\f(x_2)\implies x_1=x_2$)
         • We know $\f(x_1)=\f(x_2)$ to be true, therefore, by definition of implies and by knowing $\f(x_1)=\f(x_2)\implies x_1=x_2$ we must have:
           • $x_1=x_2$
     • This completes the first part of the proof
2. Surjectivity of $\f:X\rightarrow f(X)$ given by $\f:x\mapsto f(x)$
   • To be surjective we require: $\forall y\in f(X)\exists x\in X[\f(x)=y]$
   • Let $y\in f(X)$ be given
     • By definition of $f(X)$ (that is $f(X):=\{y\in Y\ \vert\ \exists x\in X[f(x)=y]\}$ remember) we see:
       • $y\in f(X)\iff\exists x\in X[f(x)=y]$
     • Choose $x\in X$ such that $f(x)=y$ (which we can do thanks to the above)
       • Now $\f(x)=f(x)$ by definition of $\f$ and
         • $f(x)=y$ by our choice of $x$
       • So $\f(x)=f(x)=y$ or just $\f(x)=y$
     • We have shown there exists an $x\in X$ such that $\f(x)=y$ for our given $y$
   • Since $y\in f(X)$ was arbitrary we have shown this for all $y$
   • That completes the surjectivity part of the proof

---

TODO: Check, I should have left this blank and marked it as low-hanging fruit....

---

Thus we have shown that $\f:X\rightarrow f(X)$ given by $\f:x\mapsto f(x)$ is a bijection

See also

• Bijection
• Surjection