# Problems regarding countable sets.

I am required to prove that the set of algebraic numbers is countable.

My understanding of an algebraic number is the following.

(1) A solution $z$ to the equation $a_nz^n+a_{n-1}z^{n-1}+...a_1z+a_0=0$ where $a_i \in \Bbb Z$ and $z \in \Bbb C$ is said to be $\mathbf {algebraic}$ .

(2) $\mathbf {countable}$ means that the set is finite or there exists a bijection between $\Bbb Z$.

(3) An set of an n-tuple $B_n = \{(a_1,a_2,...,a_n)|a_i \in A \}$ where set A is countable, is countable.

These are what I think I know.

The hint to this problem is to use the fact that $\forall N \in \Bbb Z^+, n + |a_n|+ ... |a_0|=N$ only has finitely many solutions.

I have no idea how to proceed from here.

-
Do you also know that a union of countably many countable sets is countable? –  Gerry Myerson May 5 '13 at 7:36
Yes I do. Sorry, forgot to mention that. –  hyg17 May 5 '13 at 8:15
I like this way of doing it: tricki.org/article/A_quick_way_of_recognising_countable_sets –  Jacob H May 5 '13 at 10:24

Here's one way to do it (without using the hint):

There's a 1-1 correspondence between polynomials $a_nz^n+a_{n-1}z^{n-1}+\cdots+a_1z+a_0$ and elements of $B_{n+1}=\{{\,(a_0,a_1,\dots,a_n)|a_i{\rm\ in\ }{\bf Z}\,\}}$, and you know $B_{n+1}$ is countable.

So there's a 1-1 correspondence between all integer polynomials and the union of all the $B_i$, a countable union of countable sets, hence countable.

And each polynomial has a finite set of roots, so the set of all algebraic numbers is a countable union of finite sets, hence, countable.

-
To be honest, I like your method best because I am much more comfortable with my 2 years knowledge of abstract algebra compared to my 1 month knowledge of analysis (basic topology in this case, I guess). Anyhow, your answer made most sense. Thank you. –  hyg17 May 11 '13 at 22:36

Let $\overline{\mathbb{Q}}$ be the set of algebraic numbers, i.e. complex numbers satisfying monic polynomial equation with rational coefficients. Given $n\geq 1$, set $\overline{\mathbb{Q}}(n):=\{\alpha\in\overline{\mathbb{Q}}: \alpha$ is a root of a monic polynomial with rational coefficients $f(x)$ of degree $\leq n$, such that, if $f(x)=a_0+a_1x+\ldots+x^m$, with $a_i=\frac{b_i}{c_i},b_i,c_i\in\mathbb{Z}, \gcd(b_i,c_i)=1$, then $|b_i|\leq n$ and $|c_i|\leq n$}.

Observe that:

1)$\ \overline{\mathbb{Q}}=\displaystyle\bigcup_{n\geq 1}\overline{\mathbb{Q}}(n)$

2) if $n\leq n'$ then $\overline{\mathbb{Q}}(n)\subseteq\overline{\mathbb{Q}}(n')$

3) $\overline{\mathbb{Q}}(n)$ is finite $\forall n$ (because there are only finitely many polynomials appearing in the definition of $\overline{\mathbb{Q}}(n)$, each of which with finitely many roots.)

Hence $\overline{\mathbb{Q}}$ is a countable union of finite sets, hence is countable.

You can explicitely exhibit a bijection $\overline{\mathbb{Q}}\longrightarrow \mathbb{N}$, for example noticing that $\overline{\mathbb{Q}}=\displaystyle\bigcup_{n\geq 1}\overline{\mathbb{Q}}(10^n)$

-
That was very helpful ! Thank you. one question, though. In my boot $\overline{\Bbb Q}$ would represent the closure of $\Bbb Q$. Is your notation suggesting that the closure of $\Bbb Q$ is the set of algebraic numbers ? Or is it just traditionally expressed as you did ? –  hyg17 May 11 '13 at 22:35
It's the closure of the rationals, but it's the algebraic closure, rather than the closure in the sense of metric spaces. –  Gerry Myerson May 11 '13 at 23:04