# Finding difficulty proving surjections

I'm finding it hard to prove surjections for the following problem. This is my thought process.

$\mathbb{N}$:

The only functions that take a $\mathbb{N}$ input is $x$. Every natural number $x$ maps to itself so it is injective. Every natural number maps back to itself so it's surjective (?). Therefore it's bijective.

$\mathbb{Z}$:

The only functions that take $\mathbb{Z}$ input are $x$, $2x+3$, and $-x$. Both inputs $x=1$ and $x=-1$ map to $f(x) = 1$ so it's not injective. I don't know how to prove that it's not surjective. I started out by thinking "Find an output $f(x) \in \mathbb{Z}$ such that $x \notin \mathbb{Z}$" but that didn't get me anywhere.

$\mathbb{R}$:

$\forall x \in \mathbb{R}$, $x$ is an input to $f(x)$. I know that it's not injective because $x=-1$ and $x=1$ map to $f(x)=1$. Not sure how to prove it is surjective.

• For $\Bbb Z$, you only have to worry about negatives (since you have the $\Bbb N$ part covered). Ignoring the aberration that is $x = -1$, for all other negatives, they'd need to come from the $2x + 3$ part. But for integer $x$, you have that $2x + 3$ is odd. – pjs36 Mar 19 '17 at 3:52
• @pjs36 thanks, I forgot that I've solved half the problem with natural numbers. And is knowing that there are only negative odd outputs for $f(x)$ proof that there is no mapping between positive odd outputs to integer inputs? – Carpetfizz Mar 19 '17 at 3:55
• Sketch the graph of $f$ for domain $\mathbb R.$ This should help you to see that if $f(x)=-1000$ then $x<-1$ but then$f(x)=-1000 \implies x=-997/2\not \in \mathbb Z.$ It should also help you to see why $f(\mathbb R)=\mathbb R.$ – DanielWainfleet Mar 19 '17 at 19:32

## 1 Answer

$\mathbb{N}$: I assume that the natural numbers here are $\{1, 2, 3, 4, \ldots\}$. In this case, yes, the function is a surjection because for every $n \in \mathbb{N}$, there is some $k \in \mathbb{N}$ for which $f(k) = n$. As you noted, it suffices to pick $k = n$.

$\mathbb{Z}$: Your initial thinking is on target. Think about what, if anything, gets sent to $-3$.

$\mathbb{R}$: Consider the outputs for $f(x)$ when $x \geq 1$. You end up getting all real numbers in $[1, \infty)$. Next, consider the outputs for $f(x)$ when $x < -1$. You end up getting all real numbers in $(-\infty, 1)$. (In both cases, it may help to draw a graph of this piecewise defined function so that you can see what the outputs are.) This already accounts for all real numbers since the union of these outputs is $\mathbb{R}$.

• Thank you for the reply, $x=0$ gets sent to $-0$ by the third function. I'm not sure how this helps just yet. Reasoning for real numbers makes perfect sense. – Carpetfizz Mar 19 '17 at 5:00
• @Carpetfizz Good point: How about $-3$? – Benjamin Dickman Mar 19 '17 at 9:26
• yep, can't seem to find a function that maps to $-3$ given an integer – Carpetfizz Mar 20 '17 at 0:37