9
$\begingroup$

Question:

Is $\mathbb{Z}= \{\dots, -3, -2, -1, 0 ,1 ,2 , 3, \dots \}$ countable?

My attemp so far:

Let us create the following one-to-one correspondence between $\mathbb{Z}$ and $\mathbb{N}$. $$\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & \dots \\ \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \updownarrow & \dots\\0 & 1 & -1 & 2 & -2 & 3 & -3 & \dots\end{matrix}$$

In order for $\mathbb{Z}$ to be countable we must define a function $f:\mathbb{N} \to \mathbb{Z}$ so that $\mathbb{Z} \sim \mathbb{N}$.

$$\displaystyle f(n) = \begin{cases} \frac{n}{2} & n \text{ is even} \\ -\frac{n-1}{2} & n\text{ is odd} \end{cases}$$

To show that $\mathbb{Z} \sim \mathbb{N}$ we require $f$ to be bijective.

From the picture above, we can clearly see that $f$ is surjective since $\forall z \in \mathbb{Z}\ \exists n \in \mathbb{N}$ such that $f(n) = z$. Hence we must now show that $f$ is injective.

We need to consider three cases:

  1. $n_1, n_2$ are odd
  2. $n_1, n_2$ are even
  3. $n_1$ is odd and $n_2$ is even

Case 1: \begin{align}f(n_1) &= f(n_2) \\ \implies -\frac{n_1 -1}{2} &= -\frac{n_2 -1}{2} \\ \implies n_1 -1 & = n_2 -1 \\ \implies n_1 &= n_2\end{align}

Case 2: \begin{align}f(n_1) &= f(n_2) \\ \implies \frac{n_1}{2} &= \frac{n_2}{2} \\ \implies n_1 &= n_2\end{align}

I am, however, experiencing some difficulty showing the injective property for the $3^{rd}$ case. Can anyone please give me some assistance with that specific case?

$\endgroup$
2
$\begingroup$

The third case is fairly easy to see intuitively, given that even numbers map to positive numbers and odd numbers map to non-positive ones. However, if you want to solve it, just suppose that, for even $n_1$ and odd $n_2$: $$\frac{n_1}2=-\frac{n_2-1}2$$ we can solve this to $$n_1=-n_2-1$$ $$n_1+n_2=1$$ However, there can be no pair of an even and an odd natural number summing to $1$, thus if $n_1$ and $n_2$ have different parity, it cannot be that $f(n_1)=f(n_2)$.

By the way, your proof gets the right point, but it isn't quite written correctly; you should write, for instance, that $$\begin{align}f(n_1) &= f(n_2) \\ \implies -\frac{n_1 -1}{2} &=-\frac{n_2 -1}{2} \\ \implies n_1 -1 & = n_2 -1 \\ \implies n_1 &= n_2\end{align}$$ where equality is used rather than inequality; $f(n_1)\neq f(n_2)$ implies $n_1\neq n_2$ for all functions - the inverse of the statement is what defines injectivity. (It also looks like you have a typo in your definition of $f$ and switched even and odd cases)

$\endgroup$
1
$\begingroup$

No need to check the third case cause you can see that when $n$ is odd then function is negative and when it's even it's positive so the sides can never be equal in 3rd case.By this I mean $f(n_1)\leq 0,f(n_2)>0$

$\endgroup$

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.