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

## 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$