3

How can we prove that $f:\mathbb Z \to \mathbb Z, f(x) = \lfloor 1.5x \rfloor$ is not onto? While it's very obvious to see, how can I actually prove that this is in fact the case? Traditional methods that I would use don't seem applicable because of the floor part of the equation...

GFauxPas
  • 5,047
acak55
  • 31
  • 4
    Where does the function go from and to? – Mankind Sep 26 '16 at 21:17
  • 1
    Is your codomain (the set you map to) also the integers? – Alexis Olson Sep 26 '16 at 21:19
  • Yes, my bad for not specifying – acak55 Sep 26 '16 at 21:20
  • The traditional method of simply looking at values to find one you can guess isn't in the codomain seems applicable.... –  Sep 26 '16 at 21:22
  • Try graphing the function or thinking through examples methodically. Then try to write a proof that some particular value is not achieved. – Ted Shifrin Sep 26 '16 at 21:22
  • Note that it's a good practice on Stack Exchange to include the statement of the question in the body of the question. It makes it easier for the reader, so they don't have to dart back and forth from the body to the title. – GFauxPas Sep 26 '16 at 21:30

5 Answers5

10

Notice that $\lfloor 1.5x \rfloor $ is non-decreasing.

$f(1)=1$, $f(2)=3$.

We do not have a preimage for $2$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
2

For all $x \in \mathbb{Z}$, $f(x) = \lfloor 1.5 x \rfloor$ is either equal to $1.5x$ or equal to $1.5x - 0.5$. So $2f(x) = 3x \text{ or } 3x - 1$. In particular: \begin{align*} 2f(x) \equiv 0 \text{ or } 2 \pmod{3} \\ \implies f(x) \equiv 0 \text{ or } 1 \pmod{3}. \end{align*}

Thus $f$ does not attain any value $\equiv 2 \pmod{3}$, so it cannot be onto.

Caleb Stanford
  • 45,895
1

You actually haven't defined the function completely. A proper definition needs to show the domain and codomain of the function i.e. $f:\mathbb R\rightarrow \mathbb R$ or $f:\mathbb R\rightarrow \mathbb N$ etc. In general $f:A\rightarrow B$.

I'm assuming that you mean $f:\mathbb Z\rightarrow \mathbb Z$.

To prove the function isn't onto, just find one element $y \in B$ s.t. there is no element in $A$ that maps to $y$. Trying a few values, $f(0) = 0,\ f(1) = 1,\ f(2) = 3$. Seems we missed $2$. Can you prove that no future value will ever map to 2?

gowrath
  • 3,573
  • 13
  • 31
0

Hint: Find an element in the codomain that is not in the image (use your intuition here). Suppose it is $c\in\Bbb Z$. Then find the possible solutions for $\lfloor 1.5x\rfloor=c$. If the possible values for $x$ contain no integers, then there is no $x\in\Bbb Z$ such that $\lfloor 1.5x\rfloor=c$.

Clayton
  • 24,751
0

I'm assuming your function is $f:\mathbb{R} \to \mathbb{R}$.

$f$ isn't onto. Just choose any value $x \notin \mathbb{Z}$ and there won't be any correspondence in the domain of $f$.

Suppose by contradiction that given $y \notin \mathbb{Z}$ there is $x \in \mathbb{R} \text{ }st. f(x)=y$. Then $\lfloor{1.5x} \rfloor \notin \mathbb{Z}$, which is absurd by definition of floor function.

edit:

OP updated that it is $f:\mathbb{Z} \to \mathbb{Z}$. Then, firstly note that $f$ is non-decreasing. Then take a look at the image set $Im (f) = \{ ..., -3, -2, 0, 1, 3, ... \}$ and you can see that there are integers in between those elements that aren't in the image set. Just take one of them, say $2$. Suppose there is $x$ in the domain of $f$ such that $f(x)=2$. Then $\lfloor 1.5x \rfloor = 2$, which means $ 2 \leq 1.5x < 3$ which is absurd since $x$ is an integer.