Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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)$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.