Let $f : \Bbb{Z} \to \Bbb{Z}$ and $g : \Bbb{Z} \to \Bbb{Z}$ be functions defined by $f(x)=3x+1$ and $g(x)=\lfloor\frac{x}{2}\rfloor$. Is $g(f(x))$ one-to-one?
So, $g(f(x)) = \lfloor\frac{3x+1}{2}\rfloor$. I know that $g(f(x))$ is one to one because we are only considering the integers. So for every $x$ integer there is a different $y$ integer. How do I prove this? I'm supposed to prove one-to-one functions by assuming $F(x_1)=F(x_2)$ and then proving $x_1=x_2$, but I don't know how to approach this when the function is a floor function.
Thanks in advance!
Best Answer
This' neat. We can prove a more general result, actually: $$h : \mathbb{R} \to \mathbb{R} \text{ injective } \Rightarrow \lfloor h \rfloor : \mathbb{Z} \to \mathbb{Z} \text{ injective }$$ then you're problem is solved by taking $h(x) := \frac{1}{2}\left(3x+1\right)$.
(Note that the typing changes were so that your specfic problem applies immediately.)
First let's recall the characterization of floor $\lfloor\_{}\rfloor : \mathbb{R} \to \mathbb{Z}$, $$\forall r \in \mathbb{R}, n \in \mathbb{Z} \;\bullet\; n \leq_\mathbb{Z} \lfloor r \rfloor \equiv n \leq_\mathbb{R} r$$ That is, the floor of $r$ is the largest integer at most $r$.
In particular, if we take $r=n$ ---since $\mathbb{Z} \subseteq \mathbb{R}$---, then we obtain $n \leq \lfloor n \rfloor$, and likewise we obtain $\geq$, and thus: $$(*) \;\;\forall n \in \mathbb{Z} \bullet \lfloor n \rfloor = n$$ That is, whole numbers are fixed points of floor.
Now the main result,
let $a,b$ be integers, then
$ \hspace{1em} \lfloor h(a) \rfloor = \lfloor h(b) \rfloor \\\equiv h(a)= h(b) \hspace{3em}\text{ since $\forall x. h(x) \in \mathbb{Z}$ and $(*)$} \\ \Rightarrow a = b \hspace{5em}\text{since $h$ is assumed injective } $
Whoah! That was a lot more work than I thought in my head.
Anyhow, hope that helps!