Elementary Foundations: An introduction to topics in discrete mathematics

In case $A$ is finite, the statement is precisely that of Fact 12.2.1. So assume $A$ is infinite, in which case a sequence of the type described in the statement must also be infinite. Technically, an infinite sequence from $A$ is a function $\mathbb{N}\to A\text{.}$ The “each element of $A$” property is the same as saying the function is surjective, and the “exactly once” property is the same as saying the function is injective. So a sequence of the described kind is exactly the same as bijection $\mathbb{N}\to A\text{,}$ which is what is required for $A$ to be the same size as $\mathbb{N}$ (i.e. countably infinite).

We have already constructed a bijection $\mathbb{N}\to \mathbb{Z}$ in Example 12.3.5, which shows that $\mathbb{Z}$ is countable.

To show that $\mathbb{Q}$ is countable, we will use Fact 13.1.2 and construct an infinite sequence which contains each element of $\mathbb{Q}$ exactly once. First, construct an infinite grid which contains all positive rational numbers. By zig-zagging through the grid, we obtain an infinite sequence which contains each positive element of $\mathbb{Q}$ at least once, though there are duplicates because an element of $\mathbb{Q}$ can have many different representations as a fraction.

We will show that no sequence of numbers from $\mathcal{C}$ can contain every element of $\mathcal{C}\text{.}$

Now we have $a_k\ne r$ for every $k\in \mathbb{N}\text{,}$ since $r$ and $a_k$ differ in the ${(k+1)}^{\mathrm{th}}$ decimal place. Furthermore, $r\in \mathcal{C}$ because it is between $0$ and $0.2$ and its decimal expansion involves only digits $0$ and $1\text{.}$ Therefore, sequence $\{a_k\}$ does not contain every element of $\mathcal{C}$ because it does not contain $r\text{.}$