Discrete math functions (Onto, One-to-One) Proof Let $f : \mathbb Z \to \mathbb Z$ and $g : \mathbb Z \to \mathbb Z$ be functions defined by $f(x) = 3x + 1$ and $g(x) = \lfloor x/2\rfloor$ (this is floor of x/2) for each $x\in\mathbb Z$


*

*Is $g\circ f$ one-to-one? Prove your answer.

*Is $g\circ f$ onto? Prove your answer.

*Is $f\circ g$ one-to-one? Prove your answer.

*Is $f\circ g$ onto? Prove your answer.


What I am thinking to try is to prove they are inverses, then I can conclude that they are both onto and one-to-one. However, I am told that they are not inverses?
 A: Here's a push in the right direction:
Note that $f$ is not onto, because given an integer, it will only yield numbers that are one more than a multiple of three. In particular, we know there is no $x$ such that $f(x)=0$.  What can we then say about $f\circ g$?
Note that $g$ is not one-to-one, because it will yield the same output for an even number and its odd successor.  In particular, we note that $g(1)=g(0)=0$.  What can we then say about $f\circ g$?
That should take care of $f\circ g$.  Now, for $g\circ f$:
Is there any $x$ for which $g(f(x))=4$?
What would we be able to deduce if we could show that $g(f(x))$ is a strictly increasing function?

Answers so far:
$f\circ g$ is neither one to one nor onto.  
It is not onto because there is no $x$ such that $f(g(x))=0$.  It is not one to one because $f(g(0)) = f(g(1))=1$
$g\circ f$ is one to one but not onto.
It is not onto because there is no $x$ such that $g(f(x))=4$.  It is one to one because for any $x\in\mathbb Z$, we find that
$$
\begin{align}
g(f(x+1)) &= \left\lfloor\frac12(3(x+1)+1) \right\rfloor\\
&= \left\lfloor\frac12(3x+1)+\frac32 \right\rfloor\\
&\geq \left\lfloor\frac12(3x+1) \right\rfloor + 1\\
&>\left\lfloor\frac12(3x+1) \right\rfloor
=g(f(x))
\end{align}
$$
That is, $g(f(x))$ is strictly increasing since for any integer $x$: $g(f(x+1))>g(f(x))$.
This means that for any integers $x,y$: $x>y$ implies $g(f(x))>g(f(y))$.
This means that $g(f(x))$ must be one to one.

To some of the points in the comments:
Your proof that $g\circ f$ is one to one was as folllows:

Suppose $g(f(a))=g(f(b))$.  That is, 
  $$\lfloor (3a+1)/2\rfloor = \lfloor (3b+1)/2\rfloor$$
  It follows that
  $$
\frac12(3a+1)-1<\frac12(3b+1)<\frac12(3a+1) + 1 \implies\\
3a + 1 - 2 < 3b + 1 < 3a + 1 + 2 \implies\\
a - 2/3 < b < a + 2/3
$$
  It follows that if $a,b$ are both integers, we must have $a=b$.  Thus, $g\circ f$ is one to one.

That works! Good proof.

"Two functions f o g are onto if and only if both f and g are onto". 

False. Consider $f,g:\mathbb{Z}\to\mathbb{Z}$ given by $g(x)=2x$, and $f(x) = \lfloor x/2\rfloor$. Note that $g$ is not onto, but $f\circ g$ is onto. Also, note that $f$ is not one to one, but $f\circ g$ is one to one.
