Functions - 7
Countable Sets
A set that is either finite or has the same cardinality as $\mathbb{N}$ is called countable.
$\mathbb{Z}$
For a set $\mathbb{Z}$ you can count it by starting at zero and then jumping from item to item by the way of a function. In this way you can produce the following mapping: $\mathbb{Z}\rightarrow\mathbb{N}$.
$\mathbb{Q}$
Consider an infinite table like so:
| $\frac{1}{1}$ | $\frac{1}{2}$ | $\frac{1}{3}$ | $\ldots$ |
|---|---|---|---|
| $\frac{2}{1}$ | $\frac{2}{2}$ | $\frac{2}{3}$ | $\ldots$ |
| $\frac{3}{1}$ | $\frac{3}{2}$ | $\frac{3}{3}$ | $\ldots$ |
| $\ldots$ | $\ldots$ | $\ldots$ | $\ddots$ |
In this table each number is represented infinitely many times due to equivalencies.
Start counting in the top left corner. Then count from the first diagonal from top to bottom. For equivalent elements there is no need to count them as the set only includes the most simplified fraction.
From this you can conclude that the cardinality of the set of rational numbers is a bijection of the set of natural numbers. This means that it is countable.