# Rudin 2.2: Prove the set of algebraic numbers is countable.

Similar to Proving that the set of algebraic numbers is countable without AC "A complex number $z$ is said to be algebraic if there are integers $a_0,\dots,a_n$, not all zero, such that $$a_0 z^n + a_1 z^{n-1} + \cdots + a_{n-1}z + a_n = 0.$$ Prove that the set of algebraic numbers is countable. Prove that there are real numbers which are not algebraic. Note: you can assume that a polynomial of degree $n$ over a field has at most $n$ roots in the field."

I'm not familiar with Axiom of Choice so I'll attempt to proof it without. Any feedback about my proof would be appreciated as I'm still inexperienced with proofs in general.

Proof:
Let $A$ be the set of all integers. From a previous example (in the textbook) $A$ is countable. Then the values of $(a_0, \dots, a_n)$ forms an $n$-tuple, where $a_k \in A(k=1,\dots ,n)$. Then it suffices to prove that the set of all possible $n$-tuples, $B$ is countable as the set of all algebraic sets is a subset of $B$. $$\textbf{Theorem: }\text{Every infinite subset of a countable set A is countable.}$$ So to prove that any subset of a countable set is also countable, then we want to show that any finite subset of a countable set is also countable. But this is obvious from the definition as all finite sets are also countable. Then the set of algebraic numbers is countable.

Now if $z \in \mathbb{R}$ then algebraic numbers satisfy the polynomial with roots in $\mathbb{R}$. Suppose $\forall z \in \mathbb{R}$, $z$ is algebraic. Then for any $r \in \mathbb{R}$, the above equation evaluates to $0$ for $z=r$. Then $r$ is a root for the polynomial $a_0 r^n + a_1 r^{n-1} + \cdots a_{n-1} r + a_n$. If $\mathbb{R}$ is a field, then a polynomial of degree $n$ over $\mathbb{R}$ has at most $n$ roots. Instead of proving all of the field axioms for $\mathbb{R}$ we cite a theorem from the previous chapter: $$\textbf{Theorem: }\text{There exists an ordered field R which has the least-upper-bound property.}$$ Then there are an infinite number of roots for the polynomial $a_0 r^n + a_1 r^{n-1} + \cdots a_{n-1} r + a_n$. Contradiction.

-
Proving that the set of polynomials with integer coefficients is a countable set gets one pretty close to the end. That has not been proved above. –  André Nicolas Sep 10 '12 at 20:10
The set all all algebraic "sets" is not a subset of $B$. For example, $\frac{1}{2}$ is algebraic (it satisfies $2x - 1 = 0$), but is not in any ordered n-tuple of integers for any $n$, because it is not an integer. –  Jason DeVito Sep 10 '12 at 20:10
I meant to say that the set of algebraic numbers maps into the set of $n$-tuples. @AndréNicolas: Would it be appropriate to say that the set of $n$-tuples maps to the set of all polynomial with degree $n$? Thanks for the quick responses! –  Andrew C Sep 10 '12 at 20:27
@AndrewC: Still kind of vague. There is no sense in my giving an answer to the countability question, since the question is answered in the post you linked to. The point is that if we are careful about a couple of traps, we can enumerate the polynomials with integer coefficients, and then for each one list its roots in increasing "order", where we define "order" carefully. –  André Nicolas Sep 10 '12 at 20:34