1
$\begingroup$

I'm doing a presentation on Godel's paper "What Is Cantor's Continuum Problem?", and would like to include a computational demonstration of the countability of the algebraic numbers.

I'm looking for an explicit bijection $f : \mathbb{N} \rightarrow \mathbb{A}$ from the natural to algebraic numbers (preferably such that $f(n)$ is relatively swiftly computable).

The plan is to code up an algorithm based on this bijection and run it during the talk, spewing out a non-repeating sequence of algebraic numbers for 50 minutes. It's of course not a proof of countability, just a demo. I'm assuming that it will be similar in construction to the "zig-zag" bijection $\mathbb{N} \rightarrow \mathbb{Q}$.

Thanks in advance!

  • 0
    For the purposes of this talk, surjectivity is more important than injectivity (I can add a quick check that tosses out repeats). Basically I just want to be able to claim that the output of the algorithm approaches $\mathbb{A}$ as $n \rightarrow \infty$.2012-11-05

2 Answers 2

2

Given any polynomial $f(x) \in \mathbb{Z}[x]$, write $f(x) = a_1 + a_2 x + a_3 x^2 + \cdots + a_{n+1} x^n$.

Let $p(n)$ denote the $n$th prime.

Then we can map $f(x)$ to $\prod_{k = 1}^{n+1} {p_k}^{a_k} \in \mathbb{N}$.

You can also see how the reverse mapping would work.

For example, the natural number $63 = 3^2 \cdot 7^1$ would map to the polynomial $g(x) = 2x + x^3$.

So you could find a mapping from each natural number to a polynomial, then compute that polynomial's roots, then list them. Then repeat the process for the next natural number, tossing out any repeats of roots. This will give you a list of all the algebraic numbers.

Remark: Since finding a polynomial's roots exactly is a rather difficult task (for polys of degree greater than $4$) I think giving the above argument would be better than having a code spew something out. Just my personal preference, though.

2

There are finitely many polynomials with integer coefficients such that the degree plus the sum of the absolute values of the coefficients is equal to $n$ for each natural number $n$. You can enumerate the roots of these polynomials for $n=1,2,3,\ldots$, skipping numbers you've already seen if you really need an injective function. Every algebraic number appears in this enumeration.