[Math] Discrete math functions (Onto, One-to-One) Proof

elementary-set-theoryfunctions

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$

  1. Is $g\circ f$ one-to-one? Prove your answer.
  2. Is $g\circ f$ onto? Prove your answer.
  3. Is $f\circ g$ one-to-one? Prove your answer.
  4. 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?

Best Answer

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.

Related Question