Proving that the natural numbers are countable, stuck.

[jack476]

Homework Statement

[/B]
I'm working through a problem in Abott's Understanding Analysis, second edition, the statement of the problem being:

"Fix a member n of the natural numbers and let A_n be the algebraic numbers obtained as roots of polynomials with integer coefficients that have degree n. Using the fact that every polynomial has a finite number of roots, show that A_n is countable."

Homework Equations

None given, but possibly helpful are:

Theorem (given as 1.5.8): The union of a possibly infinite collection of countable sets is countable

Definition: A set is countable if a bijection exists between the given set and the natural numbers.

The Attempt at a Solution

I've been struggling endlessly on this problem but I think I'm getting somewhere. My approach is that I first want to show that each configuration of n coefficients can be represented by an ordered n-tuple, and that each such n-tuple is related bijectively to only one set of roots.

Then I want to show that the set of coefficient n-tuples is countable, and that's where I'm really stuck, I get the gist of it, that since each coefficient is an integer and therefore a member of a countable set, and there are as many possible coefficient n-tuples as there are n * the cardinality of Z, (which would therefore be countable) but I'm not sure how to make that into a proof. Could I use the theorem that we proved in an example problem in the chapter that for a collection of countable sets, their union is countable?

Anyway, what I'm hoping that would result in is a bijection between N and the coefficient n-tuples and a bijection between the coefficient n-tuples and the roots of their corresponding polynomials (ie the algebraic numbers) and therefore composition of these two bijections would result in a function relating N to the algebraic numbers.

Or am I just going about this completely the wrong way?

 

[S.G. Janssens]

Here are some remarks.

1. The title of this topic is a bit odd, because clearly the natural numbers are countable, by definition. In your text you discuss a different problem, on which I will focus now.
2. The theorem you cite as 1.5.8 should be "The union of a countably infinite collection of countable sets is countable."
3. I think you are making the proof more complicated than necessary. Are you allowed to use that the finite product of countable sets is countable? If so, you can write $A_n$ as a union over the index set $\mathbb{Z}^{n+1}$. Which sets should appear in this union? Now use Theorem 1.5.8.

Edit: Incidentally, if you now take the union over $n \in \mathbb{N}$ and use again Theorem 1.5.8, you may conclude that the set of algebraic numbers is countable. Since $\mathbb{R}$ is uncountable, this allows you to infer that there are uncountably many transcendental numbers.

 

[jack476]

Here are some remarks.

1. The title of this topic is a bit odd, because clearly the natural numbers are countable, by definition. In your text you discuss a different problem, on which I will focus now.

My bad, I meant the "algebraic" numbers. How do I change this?

3. I think you are making the proof more complicated than necessary. Are you allowed to use that the finite product of countable sets is countable? If so, you can write $A_n$ as a union over the index set $\mathbb{Z}^{n+1}$. Which sets should appear in this union? Now use Theorem 1.5.8.

I actually just looked that up and realized that that was exactly what I was trying to do with my first approach to the problem before I came up with what I'm trying to do now. Thanks!

Though now for curiosity's sake, I still would like to know whether the relationship between ordered sets of polynomial coefficients and roots is a bijection, because I feel like that might be useful to know.

 

[S.G. Janssens]

Though now for curiosity's sake, I still would like to know whether the relationship between ordered sets of polynomial coefficients and roots is a bijection, because I feel like that might be useful to know.

If I understand you correctly, I don't think this is true without some additional constraints on the $n$-tuples of coefficients, because if $(a_0,a_1,\ldots,a_n) \in \mathbb{Z}^{n+1}$ with $a_n \neq 0$ is such an ordered $n$-tuple that gives rise to a polynomial of degree $n \in \mathbb{N}$, then you can easily construct many more $n$-tuples that give rise to a polynomial with the same roots. Do you see how? So the map from $n$-tuples to sets of roots is many-to-one.

 

[S.G. Janssens]

In fact, I think that it is easy to come up with such additional constraints when you allow complex roots, but I believe it is not so easy when you restrict yourself to real roots only.

 

[andrewkirk]

If we allow complex roots, a necessary and (I'm pretty sure also )sufficient condition for it to be a bijection would be for the set of polynomials to only include polynomials for which the greatest common factor of their coefficients is 1.

For real roots that doesn't work because the polynomials $(x^2+1)(x-1)$ and $(x^2+2)(x-1)$ have different coefficients but share the same, unique real root, which is 1.

So for real roots, the condition is necessary but not sufficient. Something extra is needed.

 

[S.G. Janssens]

A necessary and (I'm pretty sure also )sufficient condition for it to be a bijection would be for the set of polynomials to only include polynomials for which the greatest common factor of their coefficients is 1.

Yes, when you allow complex roots, I agree. When you restrict yourself to real roots, it's different. Consider $p(x) = x(x^2 + 1)$ and $q(x) = x(x^2 + 2)$. The greatest common factor of their coefficients equals one. Their only and common real root is zero. Of course this is not essential, but it shows that when OP defines his map from a subset of the $n$-tuples to the collection of sets of roots, the field matters.

 

[andrewkirk]

Jinx!

 

[jack476]

Yes, when you allow complex roots, I agree. When you restrict yourself to real roots, it's different. Consider $p(x) = x(x^2 + 1)$ and $q(x) = x(x^2 + 2)$. The greatest common factor of their coefficients equals one. Their only and common real root is zero. Of course this is not essential, but it shows that when OP defines his map from a subset of the $n$-tuples to the collection of sets of roots, the field matters.

Complex numbers can be algebraic (according to the Wikipedia, which has an amazingly trippy picture that is supposed to be generated by the algebraic numbers, somehow), and I'm not specifically told the roots must be real.

OTOH, this might be overcomplicating things like you said. Your suggestion was much better than what I initially was trying to do.