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<p_1<\cdots 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


Leave a comment

Filed under Set theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s