# A countability argument

Here is a countability argument that I like because it relies on almost nothing. Let $A$ be a ring.

Theorem. If $A$ is countable, then the polynomial ring $A[X]$ is countable.

Proof. Since $A$ is countable, there is an injection $f:A\to\mathbb N$. Let $p_0 be prime numbers and consider the map

\begin{aligned}g:A[X]&\to\mathbb N\\ a_0+a_1X+\cdots+a_nX^n&\mapsto p_0^{f(a_0)}p_1^{f(a_1)}\cdots p_n^{f(a_n)}.\end{aligned}

By unique factorisation in $\mathbb N$ it follows that $g$ is an injection. Thus $A[X]$ is countable. $\square$

We can use this to prove in a rather simple manner that

Corollary 1. The set $\mathbb A$ of all algebraic numbers is countable.

Proof. It follows from the above that $\mathbb Z[X]$ is countable. Let $\alpha\in\mathbb A$ be a root of some minimal polynomial $f_\alpha\in\mathbb Z[X]$. We can assign to each $\alpha\in\mathbb A$ a unique element $f\in\mathbb Z[X]$ as follows: if $\alpha_1(=\alpha),\dots,\alpha_n$ are the zeros of $f_\alpha\in\mathbb Z[X]$, assign $jf_\alpha$ to $\alpha_j$. This gives an injection from $\mathbb A$ to $\mathbb Z[X]$, as desired. $\square$

More generally,

Corollary 2. A countable union of countable sets is countable.

Proof. Let $A_0,A_1,\dots$ be countable sets. Then there are injections $A_i\to X^i\mathbb Z$ for $i=0,1,\dots$. Hence we have an injection

$\displaystyle\bigcup_{i=0}^\infty A_i\to \bigcup_{i=0}^\infty X^i\mathbb Z\subseteq\mathbb Z[X]$,

showing that $\bigcup_{i=0}^\infty A_i$ is countable. $\square$