# Proof that the set of algebraic numbers is countable

Let $A$ be the set of algebraic numbers, i.e. numbers $x\in \mathbb{R}$ which are roots of some polynomial with integer coefficients. I want to show that $A$ is countable. I've seem some different proof of this already, but I've done it in a different way and I'd like to see if what I did is correct. I did as follows:

For each $n\in \mathbb{N}$ define $A_n\subset A$ the set of all numbers $x\in \mathbb{R}$ such that

$$a_0+a_1 x +a_2 x^2 +\cdots +a_n x^n = 0,$$

for some $a_k \in \mathbb{Z}$. By definition of $A$, we this allows us to write

$$A = \bigcup_{n\in \mathbb{N}} A_n,$$

in other words, $A$ is a countable union of sets. It remains to show that each $A_n$ is countable.

For that matter, define the relation $\sim$ in $A_n$ by

$$x,y\in A_n, \ x\sim y \Longleftrightarrow \exists \ a_0,\dots,a_n\in \mathbb{Z}, \ \sum_{k=0}^n a_k x^k = \sum_{k=0}^n a_k y^k = 0,$$

in other words $x\sim y$ when they are roots of the same polynomial. In that case it is easy to see that $\sim$ is an equivalence relation. In that case, define $\xi : \mathbb{Z}^{n+1}\to A_n/\sim$ by $\xi(a_0,\dots,a_n)=[x]$ being $x$ such that $\sum_{k=0}^n a_k x^k=0$. It is easy to see that $\xi$ is a surjection. In that case $\# \mathbb{Z}^{n+1} \geq \# A_n/\sim$ and we know this is equivalent to $\# (A_n/\sim) \leq \# \mathbb{Z}^{n+1}$.

From this we deduce there is an injection $\varphi : (A_n/\sim) \to \mathbb{Z}^{n+1}$. But $\mathbb{Z}^{n+1}$ is countable, since it is the finite cartesian product of countable sets. In that case there is an injection $\eta : \mathbb{Z}^{n+1}\to \mathbb{N}$. Defining then $\psi : (A_n/\sim)\to \mathbb{N}$ by $\psi = \eta \circ \varphi$ we get an injection because it is composition of injections. With that we deduce that $A_n/\sim$ is countable.

On the other hand, since a polynomial of degree $n$ has up to $n$ roots, each set $[x]\in A_n/\sim$ is finite, hence countable. With that, recalling that $\sim$ determines a partition of $A_n$ we write

$$A_n = \bigcup_{[x]\in A_{n}/\sim} [x],$$

but since $A_n/\sim$ is countable, this a countable union of countable sets. Hence $A_n$ is countable, and so is $A$.

Is this proof correct? Since this is a little different than what I've found, I was wondering whether or not I got it right.

• You need to revise the definition of $A_n$ so that $n$ is the smallest possible such that $x$ is a root of a polynomial of degree $n$. – Quang Hoang Sep 18 '15 at 15:11
• Why not skip the equivalence relation and just define a surjection (indeed a bijection) from $\mathbb Z^{n+1}$ to the set of all degree $n$ polynomials? – Mathmo123 Sep 18 '15 at 15:13
• @Mathmo123, I thought the following: if I map $\mathbb{Z}^{n+1}$ to $A_n$ I have a problem, because there might be more than one root, and this won't define a function. If, on the other hand, I map $x\in A_n$ to $\mathbb{Z}^{n+1}$ I also have a problem, because a polynomial might have more than one root, and it won't be injective. More than that, if $x$ is root than more than one polynomial it wouldn't define a function. That was my reasoning when I used the equivalence relation. Is anything wrong with this way of thinking? – user1620696 Sep 20 '15 at 1:51
• You can define a function $A_n\to \mathbb Z^{n+1}$ by sending each $x$ to some polynomial that it is a root of, say it's minimal polynomial. You're right that this won't be an injection, but for any polynomial, its pre-image under this function will be finite, since every polynomial has finitely many roots. And the union of all the pre-images is a countable union of finite sets. – Mathmo123 Sep 20 '15 at 1:59
• To clarify, there's nothing wrong with your way of thinking aside from the very slight error that Michael and Quang have pointed out. This way is almost equivalent to your way, but it just shortens the argument a little. – Mathmo123 Sep 20 '15 at 2:01

In $A_4$, I think the root of every quadratic $q_1(x)$ is equivalent to the root of every other quadratic $q_2(x)$ because both are roots of $q_1(x)q_2(x)$. So $[x]\in A_n/\sim$ is not finite.