Proof of surjection for piecewise $f: N \to N$

346 Views Asked by At

The problem gives the following piecewise function and asks for a proof of surjection.

$f: N \to N$ as defined by

$$f(x)= \begin{cases} x-1, & \text{if $x$ is odd,} \\ x+1, & \text{if $x$ is even.} \end{cases}$$

I know that 1 is not in the image of the function. But the nature of the piecewise function is causing me some confusion on how to formally prove this.

2

There are 2 best solutions below

0
On BEST ANSWER

As is so often the case this depends upon whether your text considers $0$ to be a natural number or not.

As the book is claiming this function maps $\mathbb N \to \mathbb N$ and $f(1) = 1-1 = 0$, your text must consider $0$ to be a natural number.

So your claim there is no $f(n)=1$ is not true as $f(0) = 1$.

....

To prove this is surjective:

Show for any $m\in \mathbb N$ that there is an $n\in \mathbb N$ so that $f(n) = m$.

There are two cases:

1) $m$ is even so $m = 2k$; $m \ge 0$ and $k \ge 0$. So we must prove there is an $n$ so that $f(n)=2k$.

So

$\begin{cases}n\text{ is even}& f(n) = n+1 = 2k;&n=2k-1\text{ is odd; a contradiction}\\ n\text{ is odd}& f(n)=n-1=2k;&n=2k+1;\text{ is odd}&n\in \mathbb N\end{cases}$

We are done. For any even $2k$ we have $f(2k+1) =2k$.

2) $m$ is odd so $m = 2k+1$; $m \ge 1$ and $k \ge 0$. So we must prove there is an $n$ so that $f(n)=2k+1$.

So

$\begin{cases}n\text{ is odd}& f(n) = n-1 = 2k+1;&n=2k+2\text{ is even; a contradiction}\\ n\text{ is even}& f(n)=n+1=2k+1;&n=2k;\text{ is even}&n\in \mathbb N\end{cases}$

We are done. For any even $2k+1$ we have $f(2k) =2k+1$.

....

So for any $m\in\mathbb N$ there is an $n\in \mathbb N$ so that $f(n) =m$.

0
On

Hint: Note that $f(f(n)) =n$.