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.
QED
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 .
Best Answer
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”.