Injection/Examples/2x Function on Integers

From ProofWiki
Jump to navigation Jump to search

Example of Injection which is Not a Surjection

Let $f: \Z \to \Z$ be the mapping defined on the set of integers as:

$\forall x \in \Z: \map f x = 2 x$

Then $f$ is an injection, but not a surjection.


Proof

Let $x_1$ and $x_2$ be integers.

Then:

\(\ds \map f {x_1}\) \(=\) \(\ds \map f {x_2}\) by supposition
\(\ds \leadsto \ \ \) \(\ds 2 x_1\) \(=\) \(\ds 2 x_2\) Definition of $f$
\(\ds \leadsto \ \ \) \(\ds x_1\) \(=\) \(\ds x_2\)

Hence $f$ is an injection by definition.

$\Box$


Now consider $y = 2 n + 1$ for some $n \in \Z$.

There exists no $x \in \Z$ such that $\map f x = y$.

Thus by definition $f$ is not a surjection.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Injection/Examples/2x_Function_on_Integers&oldid=390268"