Surjection/Examples/Floor of Half x+1 on Integers

From ProofWiki
Jump to navigation Jump to search

Example of Surjection

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

$\forall x \in \Z: \map f x = \floor {\dfrac {x + 1} 2}$

where $\floor {\, \cdot \,}$ denotes the floor function.

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


Proof

Let $y \in \Z$ be an integer.

Consider the integer $x = 2 y$.

Then:

\(\ds \map f x\) \(=\) \(\ds \floor {\dfrac {\paren {2 y} + 1} 2}\) Definition of $f$
\(\ds \) \(=\) \(\ds \floor {\dfrac {2 y} 2}\)
\(\ds \) \(=\) \(\ds y\)

Thus:

$\forall y \in \Z: \exists x \in \Z: \map f x = y$

Thus $f$ is a surjection by definition.

$\Box$


Let $n \in \Z$ be an integer.

Let $x_1 = 2 n - 1$ and $x_2 = 2 n$.

Then:

\(\ds \map f {x_1}\) \(=\) \(\ds \floor {\dfrac {\paren {2 n - 1} + 1} 2}\) Definition of $f$
\(\ds \) \(=\) \(\ds \floor {\dfrac {2 n} 2}\)
\(\ds \) \(=\) \(\ds n\)


while:

\(\ds \map f {x_2}\) \(=\) \(\ds \floor {\dfrac {\paren {2 n} + 1} 2}\) Definition of $f$
\(\ds \) \(=\) \(\ds \floor {n + \dfrac 1 2}\)
\(\ds \) \(=\) \(\ds n\)

Thus we have that $x_1 \ne x_2$ but $\map f {x_1} = \map f {x_2}$.

Hence by definition $f$ is not an injection.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Surjection/Examples/Floor_of_Half_x%2B1_on_Integers&oldid=376583"