For fixed $n \in \mathbb{N}$, let $A_n$ be he set of all algebraic numbers obtained as roots of polynomials with integer coefficients that have degree $n$. Proof that $A_n$ is countable. (Hint: For each $m \in \mathbb{N}$, consider polynomials with $\sum_{i=0}^n |a_i| \leq m$.

My main problem is that I don't understand why $\sum_{i=0}^n |a_i|$ should be $\leq m$ and not equal to $m$. I would go as follows:

Let $m \in \mathbb{N}$. Then there are only finitely many polynomials of degree $n$ having integer coefficients satisfying $\sum_{i=0}^n |a_i| = m$, because there are only finitely many ways how the coefficients can be chosen. Hences, let $n_m$ be the number of these polynomials, and let $S^m_i$ be the set of solutions of the $i$th of such polynomials, $1 \leq i \leq n_m$. Since a polynomial of degree $n$ has at most $n$ solutions, $S^m_i$ is finite for all $m \in \mathbb{N}$ and all $1 \leq i \leq n_m$. Then, $S^m = \cup_{i=1}^{n_m} S^m_i$ is finite. Because each polynomial with integer coefficients falls in exactly one class for the sum of the absolute values of its coefficients, $A_n = \cup_{m=1}^{\infty} S^m$, and since the countable union of finite sets is countable, $A_n$ is countable.

  • $\begingroup$ Your argument is correct, but it would still be correct if you replaced the first $=$ by $\le$ and replaced "exactly one" by "at least one". So the hint is right, but you are right too $\ddot{\smile}$. $\endgroup$ – Rob Arthan Jul 8 '15 at 20:13
  • $\begingroup$ See Cantor's first uncountability proof. $\endgroup$ – Lucian Jul 8 '15 at 21:40

You can prove it either way. If you restrict either $\sum|a_i|=m$ or $\sum|a_i|\leq m$, you'll end up with a finite number of polynomials in your set. In the case of $\sum|a_i|\leq m$ you'll end up overcounting polynomials. However, either way you'll prove there is at MOST countably many, and since the naturals are all algebraic there are at LEAST countably many, so overcounting shouldn't worry you. And you'll be overcounting the algebraic numbers no matter what, even if you don't overcount polynomials. since different polynomials will end up having roots in common.

  • $\begingroup$ Thanks' for your answer. I was wondering why restricting it with $\leq m$ should be meaningful, because then the resulting set will include all polynomials restricted by $\leq m-1$, $\leq m-2$ etc. ? $\endgroup$ – NoBackingDown Jul 8 '15 at 20:31
  • $\begingroup$ That's exactly what it means. If $S_m$ denotes the set of polynomials $\leq m$, the following relation will be true: $S_1\subset S_2 \subset ... \subset S_{m-1}\subset S_m \subset S_{m+1}\subset ...$. But every set $S_m$ is still finite, which is all you need for your proof. $\endgroup$ – Jahan Claes Jul 8 '15 at 21:58
  • $\begingroup$ Does that make sense? $\endgroup$ – Jahan Claes Jul 9 '15 at 1:24
  • $\begingroup$ Thank you, it makes sense, I just had the feeling that placing the polynomials into disjoint classes is somehow more straightforward or nicer. But I agree that having a nested sequence of sets should also be fine. I'm just starting to learn analysis. $\endgroup$ – NoBackingDown Jul 9 '15 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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