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
    How do you plan to represent the numbers? You can't show infinite decimal representations. So is it roots, polynomials, or what?2012-11-05
  • 4
    A bijection that would be very simple to code up would be one that maps the first $10^{100}$ natural numbers to themselves and then gets started on the rest -- you wouldn't have to worry about the rest for your $50$-minute presentation.2012-11-05
  • 1
    The only reasonable way I see to discuss this is to somehow enumerate all irreducible polynomials and then combine the polynomial with the degree to get the roots (or something like that). I'm not sure how nice is the function which checks whether a polynomial is irreducible, though. That been said, explicit bijections are overrated.2012-11-05
  • 0
    @Ayman Hourieh I was planning to represent the numbers by $0 = \text{minimum polynomial}(f(n))$.2012-11-05
  • 0
    Natural explicit bijection ... seems unlikely to me ... There are explicit injections in both directions, though.2012-11-05
  • 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.