Questions on Isomorphisims

Question

$\mathbb{N}$, the set of natural numbers is set theoretically isomorphic to $\mathbb{Z}$,the set of integer. But my questions is why it is isomorphic to $\mathbb{Q}$, the set of rational numbers but not isomorphic to $\mathbb{R}$, the set of real numbers ?

Answer 1

It is easy to see that $\mathbb{N} \cong \mathbb{Z}$. Just consider

\begin{align} \Phi: \mathbb{N} &\rightarrow \mathbb{Z} \\ x &\mapsto \begin{cases} \frac{x}{2} & x \;\text{is even} \\ -\frac{x+1}{2} & x \;\text{is uneven} \end{cases} \end{align}

The proof of $\mathbb{N} \cong \mathbb{Q}$ is pretty descriptive. Consider the following sequence:

$$ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{2}{2}, \frac{1}{3}, \dots $$

Do you see how the pattern goes? First, you consider all the fractions where numerator and denominator add up to $2$. Then all fractions where they add up to $3$ and so on.

Now, you need to cross out all the fractions that are not fully shortend like $\frac{2}{2}$.

You get a new sequence $$ (a_n) = \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{3}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \dots $$

and you can map

\begin{align} \Phi: \mathbb{N} &\rightarrow \mathbb{Q^+} \\ n &\mapsto a_n \end{align}

The argument is not complete but you should now be able to find an isomorphism between $\mathbb{N}$ and $\mathbb{Q}$.

When we want to proof that $\mathbb{N} \ncong \mathbb{R}$, we can also proof that $[0, 1]$ is uncountable. This proof is a bit lengthy and you can do it with nested intervals or Cantor's second diagonal argument.

You might also want to watch the following video for this: https://www.youtube.com/watch?v=fRhdpyaOhEo