The field of algebraic numbers as a recursive structure

Question

Is the field $\overline{\mathbb{Q}}$ of algebraic numbers in the language $\{+,\cdot,0,1\}$ a recursive structure?

With "recursive structure" I mean the following: There are two recursive functions $\oplus, \odot: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ and two constants $c_0,c_1 \in \mathbb{N}$ such that the structure $(\mathbb{N},\oplus,\odot,c_0,c_1)$ is a field which is isomorphic to $(\overline{\mathbb{Q}},+,\cdot,0,1)$. So, the term "recursive structure" is used in the same way as in Tennenbaum's theorem about models of arithmetic.

Here is my motivation for the question: The Abel-Ruffini theorem states that there are polynomials in $\mathbb{Q}[X]$ whose roots cannot be written as radicals. As a consequence, $\overline{\mathbb{Q}}$ contains elements which cannot be written as radicals. In a rough sense, this can be seen as stating that there is no "obvious" effective system of notation covering all the elements from $\overline{\mathbb{Q}}$. So, my first guess is that the structure isn't recursive and that a proof of non-recursiveness might also involve the Abel-Ruffini theorem. However, it is just a guess. It might well be that there is still an effective system of notation which is not obvious and which bypasses the problem of writing all the elements as radicals...

Answer 1

The field of algebraic numbers is a recursive structure. I give a brief sketch of the (ingredients of the) proof:

1. You can code each real algebraic number as a one-variable polynomial $p$ and a pair of rationals $l < u$ such that $p$ has exactly one root in the interval $[l,u]$.

2. The set of codes for one-variable polynomials with coefficients in $\mathbb{Q}$ is recursively enumerable by a standard argument, so you can encode the data $(p,l,u)$ recursively in a single natural number, and decode it into a triple of natural numbers.

3. By Sturm's theorem (Theorem 2.50 of R1) we can decide recursively which triples of natural numbers $(p,l,u)$ are valid representations of algebraic numbers in the sense that the polynomial represented by $p$ has exactly one root in $[l,u]$.

4. Using standard results on resultants (see R2) and separation bounds on roots of polynomials, we can obtain the following: given $(p_1,l_1,u_1)$ representing the algebraic number $\alpha$ and $(p_2,l_2,u_2)$ representing $\beta$, one can recursive derive some representation $(p,l,u)$ of $\alpha + \beta$ and similarly for $\alpha\beta$, and recursively decide whether $\alpha = \beta$ or not.

5. Now, using bullet point 3, we can fix an enumeration $E$ of all triples of natural numbers that represent algebraic numbers in the sense of bullet point 1. Using the equality test from bullet point 4, we can assume that $E$ is irredundant, in the sense that for each algebraic number $\alpha$ there is a unique $n$ such $E(n)$ represents $\alpha$.

6. Consider two algebraic numbers $(p_1,l_1,u_1)=E(n_\alpha)$ and $(p_2,l_2,u_2)=E(n_\beta)$ representing $\alpha$ and $\beta$ respectively. Using bullet point 4, we can recursively obtain some triple $(p,l,u)$ that represents $\alpha + \beta$. Define $n_\alpha \oplus n_\beta$ as "the least $n$ such that $E(n)$ represents the same number as $(p,l,u)$". This is a recursive definition. Similarly for $\odot$. Choose $c_1$ and $c_0$ appropriately.

7. It's immediate that $(\mathbb{N},\oplus,\odot,c_0,c_1)$ forms a field isomorphic to the field of real algebraic numbers. Since the real and imaginary parts of an algebraic number are themselves algebraic, it's easy to obtain the field of algebraic numbers at this point.

The best resources for the nitty-gritty details: Cyril Cohen's thesis (R2), which has a careful proof on the equality of algebraic Cauchy reals being decidable, and a computer-verified implementation of exact arithmetic with algebraic numbers; and the book Algorithms in Real Algebraic Geometry.

---

R1: Basu, Pollack, Roy: Algorithms in Real Algebraic Geometry

R2: Cohen: Formalization of real algebraic numbers

Answer 2

Responding to the last half of the Question, "an effective system of notation which is not obvious and which bypasses the problem of writing all the elements as radicals"...

You already have one piece of specification: the intended number is a root of some algebraic equation. So a complete specification is the algebraic equation together with some method to uniquely identify which of its roots you mean.

One method of indicating a specific root is to indicate a complex rectangle the contains only one root. Another method is to canonically sort roots and indicate which root in the list is the one you want.

Mathematica, for instance (almost) does this with Root[]s. The minor difference is that complex conjugates are sorted adjacent. So the Mathematica rule seems to be that roots are sorted in lexicographic order by real part, then magnitude of imaginary part, then by sign of imaginary part.