55
$\begingroup$

A complex number $z$ is said to be algebraic if there are integers $a_0, ..., a_n$, not all zero, such that $a_0z^n+a_1z^{n-1}+...+a_{n-1}z+a_n=0$. Prove that the set of all algebraic numbers is countable. The Hint is: For every positive integer $N$ there are only finitely many equations with $n+|a_0|+|a_1|+...+|a_n|=N$.

Here is a proof I have. The problem though, is that I did not use the hint provided in the text, so maybe this proof is invalid or that there is an alternate (simpler) proof? Please help me out here. Thanks in advance.

Proof:

The set of integers is countable, we have this following theorem:

Let $A$ be a countable set, and let $B_n$ be the set of all n-tuples $(a_1,...,a_n)$, where $a_k \in A, k=1,...,n,$ and the elements $a_1,...,a_n$ need not be distinct. Then $B_n$ is countable.

So by this theorem, the set of all $(k+1)$-tuples $(a_0,a_1,...,a_k)$ with $a_0 \neq 0$ is also countable.

Let this set be represented by $\mathbb Z ^k$. For each a $a \in \mathbb Z ^k$ consider the polynomial $a_0z^k+a_1z^{k-1}+...+a_k=0$.

From the fundamental theorem of algebra, we know that there are exactly $k$ complex roots for this polynomial.

We now have a series of nested sets that encompass every possible root for every possible polynomial with integer coefficients. More specifically, we have a countable number of $\mathbb Z^k s$, each containing a countable number of $(k + 1)$-tuples, each of which corresponds with $k$ roots of a $k$-degree polynomial. So our set of complex roots (call it $R$) is a countable union of countable unions of finite sets. This only tells us that $R$ is at most countable: it is either countable or finite.

To show that $R$ is not finite, consider the roots for $2$-tuples in $\mathbb Z^1$. Each $2$-tuple of the form $(-1, n)$ corresponds with the polynomial $-z + n = 0$ whose solution is $z = n$. There is clearly a unique solution for each $n \in \mathbb Z$, so $R$ is an infinite set. Because $R$ is also at most countable, this proves that $R$ is countable.

$\endgroup$
  • 4
    $\begingroup$ Your proof is fine, and you don't even need the fundamental theorem of algebra: It is sufficient to know that there are at most $k$ distinct roots. $\endgroup$ – Hagen von Eitzen Sep 10 '13 at 5:54
  • 4
    $\begingroup$ This is a better proof than the one suggested by the hint (which is, I believe, the proof in, say, Rudin). There are obviously infinitely many algebraic numbers (consider $\mathbb{Q}$!), but there are at most countably many of them since there are only countably many coefficients, each of these contributing finitely many roots. $\endgroup$ – Alex Youcis Sep 10 '13 at 5:55
  • 3
    $\begingroup$ You used "a countable union of countable sets is countable" which in its general form requires AC, though that can be dispensed with in this case. The proof suggested by the hint has a (somewhat) more constructive character. But yours is a good proof. $\endgroup$ – André Nicolas Sep 10 '13 at 5:59
  • $\begingroup$ Does this proof not imply that the power set of the integers is countable? If you are taking the union of all n-tuples of any integers, is that not just the set of all subsets of the integers? $\endgroup$ – Miles Johnson Feb 26 '18 at 7:22
  • $\begingroup$ See also: How do we prove the existence of uncountably many transcendental numbers? $\endgroup$ – Martin Sleziak May 21 '18 at 13:12
4
$\begingroup$

Yes, you're correct; if you want to be more formal, you're using Cantor-Schroeder-Bernstein in your last step http://en.wikipedia.org/wiki/Cantor-Schroder-Bernstein_theorem , in concluding, from the existence of an injection between the set of all roots and the collection of polynomials and an injection between the pairs ($(1,n)$ and the set of all possible roots, that the collection of roots (i.e., the algebraic numbers) is countably-infinite.

$\endgroup$
4
$\begingroup$

Your proof is correct. It skips over a few small details, for example about the fact that you can ask $a_0 \neq 0$ in your $(k + 1)$-tuples, but depending on how nitpicky your grader is I wouldn't worry about that. The only thing I would do is explain, when you say you have a series of nested sets, exactly what those sets are and then be explicit about the theorem you are using to get that their union is countable.

$\endgroup$
3
$\begingroup$

You can express the set of algebraic numbers as a countable union of finite sets. You just have to take, for each nonnegative integer n, the set of roots of the polynomials for which k + |a_0| + ... + |a_k| = n, where k is the degree of the polynomial. For every n you only have finitely such polynomials and each polynomial has only finitely many roots.

$\endgroup$

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.