Tell me more ×
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.
up vote 11 down vote favorite

I am trying to prove that algebraic numbers are countably infinite, and I have a hint to use: after fixing the degree of the polynomial, consider summing the absolute values of its integer coefficients, and setting the sum less than or equal to $m$, for each $m \in \mathbb{N}$. I am also allowed to use the fact that every polynomial has a finite number of roots. I am not sure where to begin... Perhaps after fixing the degree of the polynomials, I could try enumerating them, and after proving countability of the set that contains the roots of all polynomials of a certain degree, I could state that the union of infinitely many ($\bigcup_{n=1}^{\infty}$, $n \in \mathbb{N}$) countably infinite sets is countable, and thus the algebraic numbers are countably infinite, too, but I am not sure if this is a good approach/how to enumerate the polynomials. Thanks!

share|improve this question
3  
+1 for showing your thoughts about the problem - this is unfortunately quite rare. – Zev Chonoles Jul 10 '11 at 17:28
2  
An alternative approach to showing that polynomials with integer coefficients are countable: consider the bijection $\phi: \mathbb{Z}[x] \rightarrow \mathbb{N}$ that sends the polynomial $a_0 + a_1x + a_2x^2 + \ldots + a_nx^n$ to the natural number $2^{b_0}3^{b_1}5^{b_2}\cdots p_n^{b_n}$ (notation: $p_i$ is the $i$-th prime number and $b_i$ is the image of $a_i$ under any bijection from the integers to the natural numbers). – Elliott Jul 10 '11 at 18:05

3 Answers

up vote 5 down vote accepted

The hint pretty much tells you what to do.

First, consider the polynomials of degree $1$ in which the sum of the absolute value of the coefficients is $1$; there's only finitely many of them, each with finitely many roots. (Think of this collection as corresponding to the pair $(1,1)$, the first $1$ giving the degree, the second $1$ giving the sum of the absolute value of the coefficients).

Then, consider the polynomials of degree $2$ whose sum of the absolute value of the coefficients is $1$; again, only finitely many, each with finitely many roots; make this set correspond to $(2,1)$.

Then, the polynomials of degree $1$ whose sum of the absolute value of the coefficients is $2$; only finitely many, each with finitely many roots. The set corresponds to the pair $(1,2)$.

Then consider the pair $(3,1)$; then the pair $(2,2)$; then the pair $(1,3)$. Then move on to the pair $(4,1)$, followed by $(3,2)$, followed by $(2,3)$, followed by $(1,4)$. Etc.

This will ensure that you cover each and every polynomial of positive degree with integer coefficients after finitely many steps; many algebraic numbers will occur more than once, but that's not a problem to showing they are at most countable (that they are infinite should be trivial).

share|improve this answer
up vote 4 down vote

That's exactly the right approach! The hint provided to you is about how might you go about enumerating the polynomials over $\mathbb{Z}$. Can you show there are finitely many polynomials over $\mathbb{Z}$ of degree $n$ and with sum-of-absolute-values-of-coefficients less than $m$, for any $m$? How many polynomials of degree $n$ are there over $\mathbb{Z}$, then? How many polynomials over $\mathbb{Z}$ are there, then? How many roots of polynomials over $\mathbb{Z}$ (i.e. algebraic numbers) are there, then?

share|improve this answer
up vote 1 down vote

HINT $\ $ Enumerate the polynomials by "height" := max(degree, max |coefficient|)

share|improve this answer
Maybe I am missing something but this problem seems really easy. For each positive integer $n$ , there are countably many polynomials of degree $n$ with integer coefficients. Each such polynomial has finitely many roots. There are countably many integers. Is that good enough? – Stefan Smith Mar 2 at 1:45
My comment above uses that fact that countable unions of countable sets are countable. I think this requires some form of the Axiom of Choice. Are the proofs above intended to avoid AC? – Stefan Smith Mar 3 at 16:20

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.