0
$\begingroup$

I've got a function that looks as follows: $$ f(x)= \begin{cases} x+1 & \text{for } x<16,\ x \text{ even} \\ x-16 & \text{for } x≥16,\ x \text{ even} \\ x+16 & \text{for } x \text{ odd} \end{cases} $$

Defined in $f:\mathbb{N}\rightarrow\mathbb{N}$

As far as I get it, this function is injective but how can I prove that this is injective?

Do I break it down to 3 "sub functions" like $f_1(x) = x+1$ etc and prove it for each one? Or is there another better way to go about it?

$\endgroup$
  • $\begingroup$ Is this function only defined for integral $x$? In other words, what is the domain? $\endgroup$ – MPW Nov 7 '16 at 20:59
  • $\begingroup$ Yes, sorry. For $f:\mathbb{N}\rightarrow\mathbb{N}$. $\endgroup$ – Void Nov 7 '16 at 21:02
  • $\begingroup$ Start by drawing the picture, with the three incomplete lines. That's really simple and will suggest the answer. $\endgroup$ – Michael Hardy Nov 7 '16 at 22:41
1
$\begingroup$

Please note that it does not suffice to show that each of the branches are injective separately. If you extended your function to $\mathbb {Z} $ it would no longer be injective even though all branches are.

The easiest way to go about it is to notice that if $k $ is odd then $f(k) $ is also odd. On the other hand, if $k $ is even and less than 16, $f(k)$ is also odd. Otherwise it is even.

Therefore if it was not injective, the problem would be for odd $k $ and even $k < 16$. That is because you can easily prove that if $k_1, k_2 \ge 16, k_1, k_2$ even $\rightarrow f(k_1) \neq f(k_2) $. But the image of $f $ over odd numbers is the set $\{17, 19, ...\}$.

On the other hand, the image of $f$ over even numbers below 16 is, at the most, 15, which is $f(14) $. Therefore $f $ is injective.

EDIT: Let us formally prove that $f $ is injective over the set $\mathbb {N} $. We will split the proof in two parts. First we show that each one of the three branches is injective. Then we show that $f $ on its own is injective.

1) We start by showing that each branch $f_i $, on its own, is injective. Remember that $f_i $ is invective if and only if $f_i(x_1) = f_i(x_2) \rightarrow x_1 = x_2$.

Let us start with $f_1(x) = x + 1$.

$$f_1(x_1) = f_1(x_2) \iff x_1 + 1 = x_2 + 1 \iff x_1 = x_2$$

We imposed no restrictions on $x $ so it is surely true for $x \in \mathbb {N} $.

We will leave the proofs of $f_2$ and $f_3$ for the reader as they are essentially the same.

2) Note that if $x $ is odd then $f(x)$ is odd. If $x $ is even, $f(x) $ may be odd or even. Assume $f(x) = f(y) = a $. If $a $ is even then we know that $a $ can only be the image of $f $ through the branch $f_2$. That means $a = f_2(x) = f_2(y) $. But $f_2$ is injective so we know that $x = y $.

Now we suppose $a $ is odd:

The branch used to calculate $f(x)$ depends on the parity of $x $ but it can also be deduced by comparing $a $ with 16. If $a < 16$ we can see that $a $ is not the image of $f_3$: $f_3(k) = k + 16 \ge 16$ because $k \in \mathbb {N}$. That means $a < 16 \rightarrow a = f_1(x) = f_1(y) \rightarrow x = y $ because $f_1$ is injective.

If $a \ge 16$ then $a $ is not the image of $x $ through $f_1$: $f_1(x) = x + 1$ but $x + 1 < 16$ because $x < 15$. That means $a $ is the image of $f$ through the third branch: $a > 16 \rightarrow a = f_3(x) = f_3(y) \rightarrow x = y $ because $f_3$ is injective.

Therefore $f $ is injective over $\mathbb {N} $.

$\endgroup$
  • $\begingroup$ Thanks a lot! Could you elaborate on this part: "That is because you can easily prove that if $k_1, k_2 \ge 16, k_1, k_2$ even $\rightarrow f(k_1) \neq f(k_2) $." $\endgroup$ – Void Nov 7 '16 at 21:35
  • $\begingroup$ @Void answer edited to include formal proof that explains that $\endgroup$ – RGS Nov 7 '16 at 22:43

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.