I am starting a new class of theory of computation (you know, where we talk about the turing machine, etc etc) and I am having some difficulties to understand that $|\mathbb N| = |\mathbb Z|$ (they are the same infinite). Before I started this class my intuition always said that $|\mathbb N| < |\mathbb Z|$. Can some one here with your own words explain to me why are $\mathbb N$ and $\mathbb Z$ the same infinite?
Thanks!
The smallest cardinality is called countable or listable. These are the sets which you can write out as a list. For example
$$\mathbb{N} = \{0, 1, 2, 3, 4, \ldots \}$$
and
$$\mathbb{Z} = \{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \}$$
are both lists. One of them happens to be bidirectional.
It turns out that if you can list a set with a bidirectional list, then you can list it with a monodirectional list. The way to do this is essentially to fold the list in half and zipper the two halves together. That is,
$$ \mathbb{Z} = \{ 0, 1, -1, 2, -2, 3, -3, \ldots \}. $$
If you can write a a set $S$ as a monodirectional list $S = \{s_0, s_1, s_2, \dots\}$ in this way, you get a bijection between that set and the natural numbers by sending $s_n$ to $n$.