# Given a function, prove that it's injective

Given a function $f: \mathbf{N}_0 \to \mathbf{N}_0$, defined $$f(x) = \begin{cases} x+3 & \text{if } x \in \mathbf{N}_{\text{even}} \\ x-1 & \text{if } x \in \mathbf{N}_{\text{odd}} \end{cases}$$

I have to prove that the function is injective.

My attempt:

Suppose that $f(a) = f(b), \forall a,b \in N_{even}$

$a+3=b+3 \implies a = b$

Suppose that $f(a) = f(b), \forall a,b \in N_{odd}$

$a-1=b-1 \implies a = b$

Since $a,b$ are arbitrary, $f$ is injective.

• What is $N_{even},N_{odd},N_p,N_d,?$ – Sahiba Arora Jan 13 '18 at 15:23
• Set of natural even numbers and set of natural odd numbers. – Marco Carta Jan 13 '18 at 15:24
• You only prove $f(a)=f(b) \implies a =b$ when both $a,b$ are even or both or odd. You either need to prove it for the other case or show that case doesn't hold. – Sahiba Arora Jan 13 '18 at 15:26

Sorry, but your attempt is incomplete.

What you have to prove is that, if $f(a)=f(b)$, then $a=b$.

There are four cases:

1. $a$ and $b$ even
2. $a$ even and $b$ odd
3. $a$ odd and $b$ even
4. $a$ and $b$ odd

In case 1, we have $a+3=b+3$, hence $a=b$.

In case 4, we have $a-1=b-1$, hence $a=b$.

You’re missing the other two cases, which actually are the same, so I’ll only deal with 2. In this case, $a-1=b+3$, therefore $$a=b+4$$ which is a contradiction.

The fact that cases 2 and 3 can’t happen doesn’t allow you to skip them without justification.

• Why is it a contradiction? – Marco Carta Jan 13 '18 at 15:45
• @MarcoCarta $b$ is even, so $b+4$ is even as well. But $a$ is assumed to be odd. – egreg Jan 13 '18 at 15:49

Proving that $f$ is injective means to prove that$$(\forall a,b\in\mathbb{N}_0):f(a)=f(b)\implies a=b.$$So, take $a,b\in\mathbb{N}_0$ and assume that $f(a)=f(b)$. Note that $f$ maps odd numbers into even numbers and vice-versa. So, since $f(a)=f(b)$, $a$ and $b$ are both odd or both even. If $a$ and $b$ are even, then$$f(a)=f(b)\iff a+3=b+3\iff a=b.$$If $a$ and $b$ are odd, then$$f(a)=f(b)\iff a-1=b-1\iff a=b.$$

• So my attempt is right? – Marco Carta Jan 13 '18 at 15:26
• @Marco Carta There are two problems: you only check that all the even (/odd) numbers have different images, NOT that even and odd numbers can't have the same image (easy). And, you use the symbol $\forall$ in the wrong way. Otherwise it's fine. – 57Jimmy Jan 13 '18 at 15:28
• @MarcoCarta No, because you wrote “Suppose that $f(a) = f(b), \forall a,b \in N_{even}$”. That's not what injective means. And at no point you explaind why is it that, if $f(a)=f(b)$, then $a$ and $b$ have the same parity. – José Carlos Santos Jan 13 '18 at 15:29
• Do I have to write all of your answer to prove the injectivity or only the 3 equations? – Marco Carta Jan 13 '18 at 15:33
• @MarcoCarta If a student of mine provided an answer which consisted only of the three expressions which you describe as “equations”, I would see it as very far from a complete answer. – José Carlos Santos Jan 13 '18 at 15:37