6
$\begingroup$

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.

  • 2
    Why does the standard argument for showing that a countable union of countable sets is countable fail without AC?2012-08-03
  • 2
    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.2012-08-03
  • 0
    @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.2012-08-03
  • 0
    Oops I just misunderstood your comment2012-08-03
  • 2
    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?2012-08-03
  • 2
    Countability of algebraic numbers does not require AC, indeed standard (Cantor) proof does not use AC.2012-08-03
  • 0
    @André Nicolas: that "standard proof" as I know it uses the fact that a countable union of finite sets is countable, which would not work in ZF, but if we take care we can exploit some uniformity to make things work.2012-08-03
  • 0
    @Carl: I think the uniformity you mention is what I meant: each of the finite sets of roots has a definite total order (hence a well-order) it inherits from $\mathbb{C}$, either by your trick or by ordering lexicographically and thus an enumeration involves no choice. Thanks for the warning.2012-08-03
  • 0
    @t.b.: yes, I agree completely.2012-08-03
  • 0
    @KReiser: the intuitive reason that principle fails is that although each set in the sequence is assumed to be countable, there may be no uniform way to pick simultaneously pick well orderings for all the sets in the sequence. The key point is that "countable" has a hidden existential quantifier saying "there exists a bijection". The formal proof that ZF cannot prove every countable union of countable sets is countable is more technical, but it's standard and is taught in introductory graduate courses in set theory.2012-08-03
  • 0
    @Cameron, KReiser: to add on what that was said here, a countable union of *enumerated* countable sets (sets which come with an enumeration) is countable in ZF.2012-08-03
  • 0
    I don't undestand anything, in fact I believe that algebraic numbers are NOT countable. As I am an idiot, could you make an argument for silly people as me, and show me a concrete bijection between algebraics (on any order ) and naturals? Thanks, and peace,2013-02-16

1 Answers 1

11

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.

  • 3
    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!!!2012-08-03
  • 0
    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.2012-08-03
  • 3
    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. http://www.ams.org/mathscinet-getitem?mr=4220222012-08-03
  • 1
    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...2012-08-03
  • 0
    Your answer and this discussion helped me a lot thank you2012-08-03