Consider the function $$f : \mathbb{N} \to \mathbb{Z}$$,

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

1. Show that $$f$$ is injective.
2. Show that $$f$$ is not surjective, so $$f$$ is not a bijection.

Define $$2\mathbb{Z} = \{ 2n \mid n \in \mathbb{Z} \}$$, i.e., the set of even integers.

3. Show that $$\operatorname{rng}(f)$$ is a subset of $$2\mathbb{Z}$$. This means that $$f$$ can be viewed as a function $$f : \mathbb{N} \to 2\mathbb{Z}$$.
4. Show that $$2\mathbb{Z}$$ is a subset of $$\operatorname{rng}(f)$$.
5. Show that $$f$$ is a bijection when considered as a function from $$\mathbb{N}$$ to $$2\mathbb{Z}$$.

So we see that whether or not a function is surjective (and, by extension, bijective) depends heavily on the choice of co-domain.

---

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

Show that $$f$$ is injective.

#### Scratchwork

Definition of injective:

$$\forall x,y \in \mathbb{N}, x \ne y \rightarrow f(x) \ne f(y)$$

Usually easier to work with positive constraints than negative constraints, so we will use the contrapositive.

$$\forall x,y \in \mathbb{N}, f(x) = f(y) \rightarrow x = y$$

$$f$$ is defined piecewise, so probably proof by cases. One possibility is $$f(x) = f(y)$$ where $$x$$ is odd vs $$x$$ is even, and similarly for $$y$$.

Notice: $$x$$ is odd, $$y$$ is even, and $$f(x) = f(y)$$ is impossible: $$f(x) > 0$$, $$f(y) \le 0$$, $$f(x) \ne f(y)$$. Similarly, $$x$$ even, $$y$$ odd, $$f(x) = f(y)$$ is also impossible. So really, we have two cases, $$f(x) = f(y) > 0$$, and $$f(x) = f(y) \le 0$$.

#### Proof.
Let $$x,y$$ be natural numbers so that $$f(x) = f(y)$$.

Case $$f(x) = f(y) > 0$$: $$x + 1 = y + 1$$, so subtract $$1$$ from both sides, $$x = y$$.

Case $$f(x) = f(y) \le 0$$: $$-x = -y$$, so once again, $$x = y$$.

In both cases, $$x = y$$, so $$f$$ is injective.


---

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

Show that $$f$$ is not surjective.

#### Scratchwork

Definition of surjective:

$$\forall y \in \mathbb{Z}, \exists x \in \mathbb{N}, f(x) = y.$$

Negation:

$$\exists y \in \mathbb{Z}, \forall x \in \mathbb{N}, f(x) \ne y.$$

If we stare at the two cases for $$f$$, when $$n$$ is odd, $$f(n) = n+1$$, which is even, and when $$n$$ is even, $$f(n) = -n$$, which is also even.

#### Proof.

Let $$y=1$$. Since $$1 > 0$$, $$f(x) = 1$$ implies $$x + 1 = 1$$, so $$x = 0$$. But $$f(0) = 0$$. So there is no natural number $$x$$ so that $$f(x) = 1$$. So $$f$$ is not surjective.

---

### Part 3

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

$$2\mathbb{Z} = \{ 2n \mid n \in \mathbb{Z} \}$$

Show that $$\operatorname{rng}(f)$$ is a subset of $$2\mathbb{Z}$$.

#### Scratchwork

Definition of subset: $$R \subseteq S$$ means $$\forall x, x \in R \rightarrow x \in S$$.

Outline:
>Let $$x \in \operatorname{rng}(f)$$.\
>[logic happens here]\
>Therefore $$x \in 2\mathbb{Z}$$.

Definition of $$x \in \operatorname{rng}(f)$$: $$\exists y \in \mathbb{N}, f(y) = x$$.\
Definition of $$x \in 2\mathbb{Z}$$: $$\exists z \in \mathbb{Z}, x = 2z$$.\
So given $$y$$, we need $$z$$ such that $$f(y) = 2z$$. Again, since $$f$$ is piecewise, we will do proof by cases.

#### Proof.
Let $$x \in \operatorname{rng}(f)$$.

There exists a natural number $$y$$ such that $$f(y) = x$$. There are two cases:
* If $$y$$ is odd, then $$x = f(y) = y + 1$$. Since $$y$$ is odd, there is an integer $$k$$ such that $$y = 2k + 1$$, so $$x = y + 1 = 2k + 1 + 1 = 2(k + 1)$$. Since $$k + 1$$ is an integer, $$x$$ is even, and we can set $$z = k + 1$$.
* If $$y$$ is even, then $$x = f(y) = -y$$. Since $$y$$ is even, there exists an integer $$k$$ so that $$y = 2k$$. Then $$x = 2(-k)$$, and since $$-k$$ is an integer, $$x$$ is even, we can set $$z = -k$$.

In both cases, $$x \in 2\mathbb{Z}$$, and so $$\operatorname{rng}(f) \subseteq 2\mathbb{Z}$$.

#### Interpretation
>This means that $$f$$ can be viewed as a function $$f : \mathbb{N} \to 2\mathbb{Z}$$.

For a function $$f$$ to be properly defined, $$f$$ needs to map each input to exactly one output in the codomain. Since $$\operatorname{rng}(f) \subseteq 2\mathbb{Z}$$, we can change the codomain from $$\mathbb{Z}$$ to $$2\mathbb{Z}$$ and it's still ok.

---
### Part 4

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

$$2\mathbb{Z} = \{ 2n \mid n \in \mathbb{Z} \}$$

Show that $$2\mathbb{Z}$$ is a subset of $$\operatorname{rng}(f)$$.

#### Scratchwork

Definition of subset: $$R \subseteq S$$ means $$\forall x, x \in R \rightarrow x \in S$$.

Outline:
>Let $$x \in 2\mathbb{Z}$$.\
>[logic happens here]\
>Therefore $$x \in \operatorname{rng}(f)$$.

Definition of $$x \in 2\mathbb{Z}$$: $$\exists z \in \mathbb{Z}, x = 2z$$.\
Definition of $$x \in \operatorname{rng}(f)$$: $$\exists y \in \mathbb{N}, f(y) = x$$.\
So given $$z$$, we need $$y$$ such that $$f(y) = 2z$$.

(This looks a lot like proving that a function is surjective, and for good reason! Recall that it is always true that $$\operatorname{rng}(f) \subseteq \operatorname{codom}(f)$$. So to show surjectivity, i.e., $$\operatorname{rng}(f) = \operatorname{codom}(f)$$, we just need to show that $$\operatorname{codom}(f) \subseteq \operatorname{rng}(f)$$. Showing $$R \subseteq \operatorname{rng}(f)$$ amounts to showing $$\forall z \in R, \exists x \in \operatorname{dom}(f), f(x) = z$$.)

Working backwards, we can find candidate values for $$y$$. We will need to check that these candidate values actually make sense in order to use them in a proof.\
If $$2z > 0$$ we are looking for an odd natural number $$y$$ so that $$f(y) = y + 1 = 2z$$. This solves to $$y = 2z - 1$$ which is odd. And since $$2z > 0$$, $$2z - 1 \ge 0$$. This is good.\
If $$2z \ne 0$$ we are looking for an even natural number $$y$$ so that $$f(y) = -y = 2z$$, i.e., $$y = -2z$$. This is even and non-negative. Very good.\
We can use these values in our proof.

#### Proof.
Let $$x \in 2\mathbb{Z}$$.

There exists an integer $$z$$ so that $$x = 2z$$.
There are two cases:
* If $$x > 0$$, set $$y = 2z - 1 = 2(z-1) + 1 \ge 0$$. So $$y$$ is an odd natural number, and so $$f(y) = y + 1 = (2z - 1) + 1 = 2z = x$$.
* If $$x \le 0$$, set $$y = -2z = 2(-z) \ge 0$$. So $$y$$ is an even natural number, and so $$f(y) = -y = -(-2z) = 2z = x$$.

In both cases, we found $$y \in \mathbb{N}$$ such that $$f(y) = x$$, i.e. $$x \in \operatorname{rng}(f)$$.

So $$2\mathbb{Z} \subseteq \operatorname{rng}(f)$$.

---

### Part 5
Show that $$f$$ is a bijection when considered as a function from $$\mathbb{N}$$ to $$2\mathbb{Z}$$.

#### Proof.
In part 1, we showed that $$f$$ is injective. In parts 3 and 4, we showed that $$\operatorname{rng}(f) = 2\mathbb{Z}$$, i.e., when considered as a function $$\mathbb{N} \rightarrow 2\mathbb{Z}$$, $$f$$ is surjective.

---
---
---
---
---