I'm doing exercises in Rudin's real analysis, chapter 2. More particularly, I'm making exercise 2 of that chapter. I already noticed there were other threads about this exercise on the site, but in order to not spoil myself, I rather avoid them until I know my solution is correct.

So here's the exercise:

A complex number $z$ is said to be algebraic if there are integers $a_0, a_1, \dots a_n$, not all zero, such that $a_0z^n + a_1z^{n-1} + > \dots + a_{n-1}z + a_n = 0$. Prove that the set $S$ of all algebraic numbers is countable.

Hint: For every positive integer $N$, there are only finitely many equations with $n + |a_0| + |a_1| + \dots + |a_n| = N$

My attempt:

Consider the set $T:= \{(a_0, \dots a_n) \in \mathbb{Z}^{n+1}\}$. For every fixed tupel $(a_0, a_1, \dots a_n)$, the associated polynomial equation, as listed in the exercise, has $n$ (not necessarily distinct) linear factors (fundamental theorem of algebra). As $T$ is the (finite) cartesian product of countable sets, it follows that $T$ is countable, so we obtain a sequence of tupels:

$$t_1,t_2, t_3, \dots$$

that contains all elements of $T$

Call ${l_i}_1,{l_i}_2, \dots {l_i}_n$ the roots of the associated polynomial equation that belongs to $t_i$,

and write the sequence :

$${l_1}_1,{l_1}_2, \dots {l_1}_n, {l_2}_1,{l_2}_2, \dots {l_2}_n, \dots$$

Then, we obtain a sequence that contains all elements of $S$, so there is a surjection $f: \mathbb{N_0}\to S$, and hence there is a subset $T \subset \mathbb{N}: f \vert_T: T \to S$ is bijective, so that $|S| = |T|$. Because $S$ is infinite (this is clear, for example $S$ contains the natural numbers), $T$ is infinite as well, and since an infinite subset of a countable set (here $T \subset \mathbb{N}$) is countable (this is proven in Rudin, theorem 2.8), it follows that $T$ is countable, and therefore also $S$ is countable.


Can someone verify whether this is correct? I know I didn't use the hint.

Also, the following exercises seem easy given this result. Could someone look at these too? (if not I will ask them in a separate question):

Prove there exist real numbers that are not algebraic.

Attempt: If all real numbers would be algebraic, then the real numbers would be countable. A contradiction. (in the theory is proven that the real numbers are uncountable)

Is the set of all irrational real numbers countable?

Attempt: No, if it were, then the real numbers would be countable, as the union of countable sets remains countable. A contradiction .

  • 9
    $\begingroup$ You don't need to use the fundamental theorem of algebra, just that a polynomial of degree $n$ over a field has at most $n$ roots. $\endgroup$ – lhf Jul 21 '17 at 14:53
  • $\begingroup$ I didn't know that result. So in fact I can simplify the proof a bit, but is the proof correct how it stands now? $\endgroup$ – user370967 Jul 21 '17 at 15:19
  • $\begingroup$ @Math_QED You know the Fundamental Theorem of Algebra but not that a non-zero polynomial cannot have more roots than its degree? To me, that's like someone who knows how to compute integrals, but not how to compute the area of a rectangle... $\endgroup$ – José Carlos Santos Jul 21 '17 at 16:26
  • $\begingroup$ I have not proven the fundamental theorem of algebra yet, or anything related. It requires complex analysis to prove it, and I'm only a first year undergrad. $\endgroup$ – user370967 Jul 21 '17 at 16:47
  • $\begingroup$ I'm very confused by your comments. First you say you are proving it with the fundamental theorem of algebra. Then you say you don't know the basic result of the fundamental theorem of algebra. Then you say you havent proven it and can't use it at all. $\endgroup$ – fleablood Jul 21 '17 at 16:56

It's essentially correct, but it can be simplified.

For every $t=(a_0,a_1,\dots,a_n)\in T_n=\mathbb{Z}^{n+1}\setminus\{(0,\dots,0)\}$, consider $$ R(t)=\{z\in\mathbb{C}:a_0+a_1z+\dots+a_nz^n=0\} $$ Then the set $R(t)$ is finite and consists of algebraic numbers. Since every algebraic number belongs to $R(t)$ for some $t\in T_n$ and some $n>0$, the set of algebraic numbers is $$ \bigcup_{n>0}\,\bigcup_{t\in T_n}R(t) $$ For every $n$, the set $$ A_n=\bigcup_{t\in T_n}R(t) $$ is the countable union of finite sets, so it's countable. Therefore the set $A$ of algebraic numbers is $$ A=\bigcup_{n>0}A_n $$ hence a countable union of countable sets.

Note: $A_n$ might in principle be finite (actually it isn't), but this wouldn't invalidate the proof. Read “countable” as “finite or countable”.

  • 1
    $\begingroup$ But $n$ is fixed in the above, so we need a final union over $n.$ $\endgroup$ – zhw. Jul 21 '17 at 16:12
  • $\begingroup$ @zhw. Yes, that's right. I'll amend. $\endgroup$ – egreg Jul 21 '17 at 16:26
  • $\begingroup$ Is an infinite union of countable sets countable? $\endgroup$ – user370967 Jul 21 '17 at 17:02
  • $\begingroup$ @Math_QED Countable union of countable sets: yes. $\endgroup$ – egreg Jul 21 '17 at 17:03
  • $\begingroup$ I actually don't see the need to take the union over $n$. If you prove it for a fixed $n \in \mathbb{N}$, you have proven it for all polynomials, since you can take $n$ as large as you want (and hence to take polynomials of lower degree, you can consider tuples $(0,0, ..., a_m, a_m+1, ..., a_n))$ $\endgroup$ – user370967 Jul 21 '17 at 17:11

Your Answer

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