# How to prove injectivity in function with multiple cases?

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?

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

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

• 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)$." – Void Nov 7 '16 at 21:35
• @Void answer edited to include formal proof that explains that – RGS Nov 7 '16 at 22:43