# Determining if Function is 1:1 or Onto

I'm trying to solve the following question:

Given function $\displaystyle f\colon \mathbb Z \rightarrow \mathbb Z,$ where $f(n) = \lfloor {\frac {n}{3}} \rfloor$, determine if it's $1:1$, and onto; and prove why.

I could say that it is onto, because it will always have an element in the codomain that maps to the domain. It is also not one to one, because the floor would result in multiple numbers with the same floor (like $\frac {1}{3}$ and $\frac {2}{3}$ both having the floor $0$). But how can I actually prove these?

-

Look at the definition of $1$-$1$ function. See what happens, when you plugin $3$ and $4$ to $f$. You have $$f(3) = \biggl\lfloor{\frac{3}{3}\biggr\rfloor} = 1 = \biggl\lfloor{\frac{4}{3}\biggr\rfloor}=f(4)$$

but $3 \neq 4$ hence it is not $1$-$1$. Note that if you want to prove a function is one-one, then you have to show whenever $f(a)=f(b) \Longrightarrow a=b$.

To prove that it is onto, for each integer $n$ we want integer $m$ such that $\bigl\lfloor{\frac{m}{3}\bigr\rfloor} = n$. Doesn't $m=3n$ finish the job?

-
So since m=3n is a Real number, then it is onto? –  Christopher May 30 '11 at 18:14
@Christopher: It's an integer. Yes :). To see it give me an $x$. Say $3$, then i have 10 in $\mathbb{Z}$ such that $f(10)=3$. Next, give me 5 then i have 15 in $\mathbb{Z}$ such that $f(15)=5$. For ontoness you have to show there is $y in \mathbb{Z}$ such that $f(x)=y$ for some $x \in \mathbb{Z}$. –  user9413 May 30 '11 at 18:16

HINT $\rm\ \ \ \#\ f^{\:-1}(k)\ =\ \#\:\{\: n\ :\ k\:\le\: n/3\: <\: k+1\}\ =\ \#\:\{\: n\ :\ 3\:k\: \le\: n\: <\: 3\:k+3\}\ >\ 1$

-

You already have done most of the work.

To prove that it is not one to one, you just need a counterexample, which you already have.

To prove that it is onto, for each integer $n$ find (explicitly) an example of an integer $m$ such that floor $m/3 = n$.

-
Ok, so to prove that its ONTO, how can I prove that each n has a corresponding m/3? I haven't proved (or disproved) any floor/ceiling functions before. –  Christopher May 30 '11 at 18:10
@Christopher: One way, which works here, is to say that if I give you an $m$, you can always find an $n$ such that $f(n)=m$. You prove that by saying "and $n=3m$ (or $n=3m+1$) works". –  Ross Millikan Mar 6 '13 at 17:06