###### tags: `108上助教` `數學`
# 數學導論HW9
## ch7-1

#### proof
Consider $f:\mathbb{N} \rightarrow \mathbb{Z}$ by
\begin{equation} f(n) =
\begin{cases}
\dfrac{n}{2} & \mbox{ if $n$ is even}\\
-\dfrac{n-1}{2} & \mbox{ if $n$ is odd}
\end{cases}
\end{equation}
We want to show that $f$ is 1-1 and onto.

**proof of 1-1**
Let $n, m \in \mathbb{N}$ such that $f(n)=f(m)$
We have two cases:

==case 1:== $f(n),f(m)>0$
that is, $\dfrac{n}{2} = f(n) = f(m) = \dfrac{m}{2}$
$\Rightarrow n = m$

==case 2:== $f(n),f(m)\leq 0$
that is, $-\dfrac{n-1}{2} = f(n) = f(m) = -\dfrac{m-1}{2}$
$\Rightarrow n = m$

Hence we proved that $f$ is 1-1.

**proof of onto**
We want to show that $\forall a \in \mathbb{Z}\ , \exists\ n \in \mathbb{N}$ such that $f(n) = a$
Suppose $a\in \mathbb{Z}$

==case 1:== $a = 0$
It is easy to find that $f(1) = 0$

==case 2:== $a > 0$
Note that $a = \dfrac{2a}{2}$
Let $n = 2a$ , then $n$ is even
that is, we find $n\in \mathbb{N}$ such that $f(n) = \dfrac{n}{2} = a$

==case 3:== $a < 0$
Note that $a = -\dfrac{(-2a+1)-1}{2}$
Let $n = -2a + 1$
$\because a < 0$ , we have $n > 0$
and $n$ is odd
that is, we find $n\in\mathbb{N}$ such that $f(n) = -\dfrac{n-1}{2} = a$
By the case above, we proved that $f$ is onto

Since $f$ is 1-1 and onto, we proved that $\mathbb{N}$ and $\mathbb{Z}$ have the same cardinality.$\Box$