0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
-1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.