- #1
quasar_4
- 290
- 0
Homework Statement
Prove that the set of algebraic numbers is countable using ONLY the following information:
- We consider algebraic numbers to be the root of a polynomial with integer coefficients
- The height of a polynomial of degree n of the form a0 + a1x + ... + an*x^n
is given by h(P(x)) = n + a0 + |a1| + ... + |an| where a0>0 and an is not zero.
- Show that the set Nk of the zeros of all polynomials of height k is finite.
Homework Equations
Listed above...
The Attempt at a Solution
I can think of at least two other ways to prove this, but our professor requires us to use this method. The part I'm worried about is showing that the set Nk is countable. It seems like it would have to be an induction proof all of its own, but my professor insists I just have to argue "carefully". I'm not sure what that means; any feedback from anyone would be great so that I'll know if I'm meeting the right mark!
Here's what I have:
Consider the set Pk of all polynomials with integer coefficients that are of height k. Let us define the set Nk = {a in R| a is a root of some Pn(x) in Pk}. Now for any fixed value of k and polynomial Pn(x) in Pk, the value of k is constrained by the equation
k >= n + a0 + |an| since a0 >0 and an is non-zero [the other coefficients could be zero].
[this next bit is the handwaving part]
Thus for any height k, the number of polynomials in the set Pk is constrained and is at most countable (or finite). Furthermore, by the zero theorem we have that each Pn(x) in Pk has at most n real roots. Thus for fixed k the number of elements of Nk is at most countable (or finite).
[next is the simple conclusion]
Now the set of algebraic numbers A consists of the set of all zeros of all polynomials with integer coefficients [this is our text's definition], so A = [tex]\bigcup[/tex]Nk . Since each of the Nk is at most countable, we have a union of at most countable sets. By theorem 2.9 [in our text] the union of countable sets is countable, so it follows that A is a countable set.
Ok - please help with the handwaving bit. I'm apparently not allowed to prove a lemma that the set of all polynomials are countable, nor use sequences, it has to be the height thing and Nk being countable, without using induction anywhere...