# Injective function proof involving floor function

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.

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!

One possible Case would be:

Let $[x]=[y]$ in which $[x]=\text{floor}(x)$. If $x\in\mathbb Z$ then $[x]=x$ and so $[y]=x\in\mathbb Z$ so $$y\in [x,x+1)$$ Since, here, $y\in\mathbb Z$ so we necessarily have $y=x$.

Hint:

Observe that for any integer $x$, $f(x+1)-f(x)=\frac32$. Hence $f(x+1)$ has a strictly greater floor function value than $f(x)$.

IDEA $\lfloor x \rfloor=\lfloor y \rfloor \Rightarrow |x-y|<1$.

If $g(f(n))=g(f(m))$ for some $n,m\in\Bbb Z$, $\left\lfloor{3n+1\over2}\right\rfloor=\left\lfloor{3m+1\over2}\right\rfloor$, so $$\left|{3n+1\over2}-{3m+1\over2}\right|<1.$$ But $\text{LHS}=\frac32|n-m|$, so $|n-m|<\frac23$, thus we get $m=n$.

Oh for god sake, $$\lfloor\frac{3(1.1)+1}{2}\rfloor = \lfloor\frac{3(1.2)+1}{2}\rfloor = 2.$$ Thus, $g\circ f$ is not one-to-one.

• 1.1 and 1.2 are not integers though. – user3444564 Aug 11 '14 at 2:37