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.

  • $\begingroup$ What is $N_{even},N_{odd},N_p,N_d,?$ $\endgroup$ – Sahiba Arora Jan 13 '18 at 15:23
  • $\begingroup$ Set of natural even numbers and set of natural odd numbers. $\endgroup$ – Marco Carta Jan 13 '18 at 15:24
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Why is it a contradiction? $\endgroup$ – Marco Carta Jan 13 '18 at 15:45
  • $\begingroup$ @MarcoCarta $b$ is even, so $b+4$ is even as well. But $a$ is assumed to be odd. $\endgroup$ – 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.$$

  • $\begingroup$ So my attempt is right? $\endgroup$ – Marco Carta Jan 13 '18 at 15:26
  • $\begingroup$ @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. $\endgroup$ – 57Jimmy Jan 13 '18 at 15:28
  • $\begingroup$ @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. $\endgroup$ – José Carlos Santos Jan 13 '18 at 15:29
  • $\begingroup$ Do I have to write all of your answer to prove the injectivity or only the 3 equations? $\endgroup$ – Marco Carta Jan 13 '18 at 15:33
  • 1
    $\begingroup$ @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. $\endgroup$ – José Carlos Santos Jan 13 '18 at 15:37

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.