Can someone tell me if this is rigorous enough?

[quasar_4]

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 = \bigcupNk . 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...

 

[HallsofIvy]

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).

Any polynomial in Pk is defined by its k+ 1 coefficients. Thus Pk can be thought of as the Cartesian product of Z with itself k+1 times. You should have already proven that a Cartesian product if a finite number of countable sets is countable (the fact that the set of rational number is countable, for example, is from the fact that it is a subset of Z x Z).
That proves that Pk is countable. Each polynomial in Pk has, at most, k real roots (not "n").

[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 = \bigcupNk . 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.

You have a union of a countable number of countable sets.

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...

I'm not sure why you say you are not allowed to uses lemmas but you certainly could write such a lemma, then just "patch" that proof into the place in the main proof where you use the lemma!

 

[quasar_4]

thanks for the comments!

mathematically it is completely ok to use lemmas. It's just that for some weird reason, our professor wants us to do this problem this way. If I do it any other way I don't get credit. Kinda odd in my opinion, as the goal should be to construct proofs that are reasonable, not just memorizing a single method!

our text also makes this big difference between "countable" and "at most countable", and at the moment it isn't clear to me which statement I'm supposed to be using here... I guess countable, since the sets aren't necessarily finite... :shy:

 

[HallsofIvy]

In many texts, "countable" means "countably infinite". "At most countable" includes the possibility that the set may be finite.