0
$\begingroup$

How do I prove that this piecewise function is injective?

The function is $f$ from $\mathbb Z$ to $\mathbb Z$, defined as

$$f(x) = \begin{cases} 3x+1\,\,\,\,, & \text{if $x$ ≥ 0} \\ -3x+2, & \text{if $x$ < 0} \end{cases}$$

Usually I would provide my working, but this time I don't even know how to approach this. (http://www.cs.utexas.edu/~isil/cs311h/lecture-functions-6up.pdf) I am learning using this link but there are no notes on the proof, there are just blank slides.

$\endgroup$
  • $\begingroup$ In the linked slides the function is specified as being $\mathbb Z\to\mathbb Z$. That's important because then it is injective. $\endgroup$ – Henrik Jan 9 '17 at 15:24
2
$\begingroup$

This function is injective, because it's defined from $\mathbb Z$ to $\mathbb Z$ (as defined in the slides).

Therefore, you can prove that it is injective, e.g. in the following way: suppose you have a value $y$ and need to determine the corresponding $x$. If $y \equiv 1 \mod 3$, it can only be the equal to $f(x)$ if $x = (y-1)/3$. If $y \equiv 2 \mod 3$, it can only be equal to $f(x)$ if $x = -(y-2)/3$.

This is not a rigorous proof, but it gives you a general idea how to construct one.

$\endgroup$
1
$\begingroup$

To prove that this is not injective, you need to only provide one counterexample:

$$f(1)=f(-\frac{2}{3})=4$$

$\endgroup$
1
$\begingroup$

If $x_0>0$ , $x_1 <0$ and $x_0+x_1=1/3$, then

$$f(x_0)=f(x_1).$$

Hence $f$ is very far away from being injective.

$\endgroup$
1
$\begingroup$

After looking at your link we see $f: \mathbb Z \to \mathbb Z$ so you see by Campbells answer it is important to write down the domains too (he considered $f: \mathbb R \to \mathbb R$ where the function is indeed not injective!).

Now assume $f$ is not injective, this means there exists $x,y \in \mathbb Z$ with $f(x)=f(y)$. Since $f$ is strictly monotone on the positive and negative numbers we deduce wlog. $x\leq 0 <y$ (they have different signs).

Hence we have $3|x|+2=3y+1$, so $x=y-\frac{1}{3}$. Assuming $y \in \mathbb Z$ we now see that $x \not\in \mathbb Z$ and hence our counterexample is wrong.

So no such $x$ and $y$ can exist and $f$ is injective.

$\endgroup$

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.