# How to prove $f(n)=\lceil\frac{n}{2}\rceil$ is one-to-one and onto?

Edit: Both domain and codomain are the set of all integers ($\mathbb{Z}$)

I proved $f(n) = \lceil\frac{n}{2}\rceil$ was one-to-one this way: $\forall{x_1}\forall{x_2}[(f(x_1) = f(x_2)) \to(x_1 = x_2)]$

Let $f(n) = f(x) = y$

Let $x_1 = 2$ and Let $x_2 = 1$

Then $f(x_1) = \lceil\frac{x_1}{2}\rceil$ and $f(x_2) = \lceil\frac{x_2}{2}\rceil$

$f(x_1) = f(x_2)$ becomes $\lceil\frac{2}{2}\rceil = \lceil\frac{1}{2}\rceil$, which in turn becomes $1 = 1$, but $x_1\neq x_2$.

$\therefore$ this function is not one-to-one.

1 -- Is this proof coherent and correct?

2 -- Next, I'm trying to prove onto by letting $f(x) = y = f(n)$ and $x=n$, then solving for $x$ in $y=\lceil\frac{x}{2}\rceil$. But I don't know how to do this, because I'm not sure if the ceiling function allows associativity, nor how that would work if it does.

I've been trying to prove this based on the (book's) logical definition of onto as $\forall{y}\in{Y}\exists{x}\in{X}|[f(x)=y]$ but have been coming up short.

Any help would be greatly appreciated.

• For the first part, it would be much simpler to just write $f(2) = f(1) = 1$, yet $2 \neq 1$, so the function is not one-to-one. – The Chaz 2.0 Sep 20 '15 at 23:33
• @TheChaz2.0 Excellent point. – Irongrave Sep 20 '15 at 23:42

## 1 Answer

In general when you prove functions are 1-1 and onto, you need to start by specifying the domain and codomain for your function. In this case both your domain and codomain are $\mathbb{Z}$, so you can write your ceiling function as $f:\mathbb{Z} \to \mathbb{Z}$.

To prove $f$ is onto, you want to show for any number $y$ in the codomain, there exists a preimage $x$ in the domain mapping to it. To show this, start by taking an arbitrary $y \in \mathbb{Z}$. Does $y$ have something in the domain mapping to it? Sure, take $x=2y$ (which we know is in the domain, because if $y$ is an integer, then so is $2y$), and observe that \begin{equation*}f(x)=\lceil \frac{x}{2} \rceil = \lceil \frac{(2y)}{2} \rceil = \lceil y \rceil =y \end{equation*} as desired.

• The OP's function is $n \mapsto \lceil \frac{n}{2} \rceil$ (and the domain is obviously not $\mathbb{R}$ if it is going to be one-to-one). – Rob Arthan Sep 20 '15 at 23:38
• Sorry! I forgot to specify that both domain and codomain are $\mathbb{Z}$ .. will edit! – Irongrave Sep 20 '15 at 23:39
• No problem. I updated the answer as well. – Mathemanic Sep 20 '15 at 23:46