Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Wikipedia : In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with rational (or equivalently, integer) coefficients.

  • Question : Show that the Set of algebraic number in $\mathbb{C}$ is countable ?

  • Hint : if $\mathbb{F(z) = a_ 0 + a_1z + .... + a_nz^n}$ we denote the Height of a polynomial as : $\mathbb{h = |a_0| + |a_1| + ...... + |a_n| + n}$

PS : i have already solve it , i am looking for different way to solve it ;)

share|improve this question
2  
How big is the set of polynomials of a given degree with integer coefficients? –  Gunnar Magnusson Jan 2 '11 at 19:48
2  
Enumerate the polynomials with integer coefficients. –  Arturo Magidin Jan 2 '11 at 19:48
    
You first need the fact that every algebraic number,$t$, corresponds to a "minimal polynomial". ie a monic polynomial with integer coeficients, having $t$ as a root, whose degree is as small as posible. Show that the set of such polynomials is countable. –  user3180 Jan 2 '11 at 20:03
3  
Is this a homework assignment? I mean, I just wrote this exact question in a problem set yesterday. –  Asaf Karagila Jan 2 '11 at 20:03
1  
@Tony K. You right. We don't really need minimal polynomials The fact that $Z[x]$ is countable is good enough. I just find it easier to consider a specific polynomial for each algebraic number. –  user3180 Jan 2 '11 at 20:39
show 2 more comments

1 Answer

To solve this elegantly I think one needs the following steps:

  • Define an equivalence relation on the algebraic numbers: $x\sim y$ if and only if they have the same irreducible polynomial, that is the polynomial of minimal degree which has the leading coefficient (the highest power) as $1$. (E.g. $i$ and $-i$ are equivalent, while $\sqrt{2}$ and $\sqrt{3}$ are not)
  • Prove the fact that in each equivalence class there are only finitely many elements
  • Show that there is a simple injection from the equivalence classes into the polynomials over $\mathbb{Q}$ (namely $[x] \mapsto irr(x)$ (the irreducible polynomial of $x$ over the rationals)
  • Show that there are only countably many polynomials (that is, the number of finite sequences from a countable set is countable)
  • Use the fact that finitely many elements in each equivalence class, times countably many classes result in at most countably many elements.

All in all, you have an injection from algebraic numbers into a countable set, and since all the natural numbers are in particular algebraic it is also clear that there are infinitely many of those.

This proof does not require the axiom of choice, as Andres remarked well in his comment. All the enumerations mentioned above can be done explicitly (or with the CSB theorem, which also does not require the axiom of choice).

share|improve this answer
1  
You could add that no use of the axiom of choice is needed here, because there is an explicit way of enumerating each (finite) equivalence class. –  Andres Caicedo Jan 2 '11 at 20:24
1  
@Andres: Yes, I could, and if you assume negation of choice then I also have to - since there will be no choice otherwise. ;-) –  Asaf Karagila Jan 2 '11 at 20:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.