# Proving that the set of algebraic numbers is countable without AC

A complex number $z$ is said to be algebraic if there is a finite collection of integers $\{a_i\}_{i\in n+1}$, not all zero, such that $a_0z^n + … + a_n = 0$.

Then can I prove the set of all algebraic numbers is countable without AC? I can only prove this by assuming 'countable union of countable sets is countable'. I guess and hope there's a way to prove this in ZF. Help.

-
Why does the standard argument for showing that a countable union of countable sets is countable fail without AC? – KReiser Aug 3 '12 at 0:09
Not sure about proving that there are only countably-many algebraic numbers in ZF. However, I do know that a countable union of countable sets need not be countable in ZF. – Cameron Buie Aug 3 '12 at 0:10
@KReiser I thought i could prove that a week ago and posted a question. 'countable union if countable set is countable' is weaker than ZFC but stronger than ZF. – Katlus Aug 3 '12 at 0:12
But by the usual argument you only have a countable union of finite sets (each of which has a well-order as a finite subset of $\mathbb{C} \cong \mathbb{R}^2$ with the lexicographical order). That should be enough to get a definite enumeration of the algebraic numbers, no? – t.b. Aug 3 '12 at 0:56
Countability of algebraic numbers does not require AC, indeed standard (Cantor) proof does not use AC. – André Nicolas Aug 3 '12 at 1:00

You do not need AC to prove the result because you can explicitly define an enumeration of the algebraic numbers within ZF. To do so, we start with any of the standard enumerations of the set $\bigcup_{n \in \omega} (\omega \times \mathbb{Z}^{n+1})$. This set consists of all sequences of the form $(k, a_0, \ldots, a_n)$ where $k \in \omega$ and $(a_0, \ldots, a_n)$ is a nonempty tuple of integers. We will use this as a starting point to define an enumeration of the algebraic numbers.

First, suppose that $w, z$ are two roots of the same nonzero polynomial $p(x) \in \mathbb{Z}[x]$. Say that $w <_{p(x)} z$ if either $|w| < |z|$ or else if $|w| = |z|$ and $\operatorname{arg}(w) < \operatorname{arg}(z)$. So $<_{p(x)}$ is a well ordering of the finite set of roots of $p(x)$ for every nonzero $p(x) \in \mathbb{Z}[x]$, and this ordering is uniformly definable with the tuple of coefficients of $p(x)$ as a parameter.

We form an enumeration of the algebraic numbers as follows. Say that a finite tuple of integers $(k, a_0, \ldots, a_n)$ represents a complex number $w$ if $w$ is a root of $p(x) = a_0 + a_1 x + \cdots + a_n x^n$, and $p(x)$ is not identically zero, and $k \in \omega$, and there are exactly $k$ other roots $z$ of $p(x)$ with $z <_{p(x)} w$. The relation "$(k, a_0, \ldots, a_{n})$ represents $w$" is definable in ZF, and ZF proves that for every algebraic $z$ there is at least one tuple that represents $z$, and every complex number that is represented is algebraic. Therefore, we can enumerate the algebraic numbers in the same order that they are represented by tuples, using the enumeration of the tuples from above.

Thus ZF proves that there is a surjection from $\omega$ to the set of algebraic numbers. Because $\omega$ is well ordered already, ZF can turn this into a bijection $f$ from $\omega$ to the set of algebraic numbers (namely, $f(n)$ is the $n$th distinct algebraic number to appear in the enumeration). Hence ZF can prove the set of algebraic numbers is countable.

-
This is correct if by "the algebraic numbers" you mean the algebraic closure of $\mathbb{Q}$ contained in $\mathbb{C}$. However, Hodges has shown that ZF does not prove that this is the only algebraic closure of $\mathbb{Q}$. In particular, since ZF proves that any two countable algebraic closures of $\mathbb{Q}$ are isomorphic, there is a very wild model of ZF where $\mathbb{Q}$ has an uncountable algebraic closure!!! – François G. Dorais Aug 3 '12 at 2:06
I wasn't aware of that, but I was using the definition of algebraic from the question. Of course "uncountable" means much less in ZF than ZFC, I suppose. – Carl Mummert Aug 3 '12 at 2:15
Yes, your answer is perfectly correct, my comment was just an addendum. Since I had a chance to look it up, the reference is: Hodges, Läuchli's algebraic closure of $\mathbb{Q}$, Math. Proc. Cambridge Philos. Soc. 79 (1976), 289-297. ams.org/mathscinet-getitem?mr=422022 – François G. Dorais Aug 3 '12 at 2:21
And yes, countable means $\leq \aleph_0$ and, in particular, infinite Dedekind finite sets are "uncountable" in ZF. So one shouldn't think that "uncountable" means "large" in ZF... – François G. Dorais Aug 3 '12 at 2:25
Your answer and this discussion helped me a lot thank you – Katlus Aug 3 '12 at 2:45