= Solution
A set is <countable set> if it is finite or admits an enumeration by natural numbers. If $A_n$ are countable, choose enumerations $a_{n,m}$. Since $\mathbb N^2$ is countable by diagonal enumeration, the array $(n,m)\mapsto a_{n,m}$ enumerates $\bigcup_nA_n$ after repetitions are removed. This proves that a <countable union of countable sets> is countable.
The integers are countable, so $\mathbb Z\times\mathbb N_{>0}$ is countable. Mapping $(p,q)$ to $p/q$ surjects onto $\mathbb Q$, hence $\mathbb Q$ is countable. The same diagonal argument shows that $A\times B$ is countable whenever $A,B$ are.
Finally, if the reals in $(0,1)$ had decimal expansions $x_1,x_2,\ldots$, choose a decimal whose $n$th digit differs from the $n$th digit of $x_n$, avoiding digits $0$ and $9$ to remove expansion ambiguity. This number differs from every listed number. The <Cantor diagonal argument> proves that $\mathbb R$ is uncountable.
Back to article page
