Basis for the Algebraic numbers over the rationals Is there an explicit basis for the algebraic numbers as a vector space over the rationals?
 A: Let me offer a formulation of your question, using ideas of
computable model theory, which make it both interesting and
nontrivial. Given that there is a computable presentation
of the field $\mathbb{A}$ of algebraic numbers, meaning
the algebraic closure of $\mathbb{Q}$, the natural
questions would seem to be:


*

*Is there a computable presentation of $\mathbb{A}$
in which there is a computable subset forming a basis for
it as a vector space over $\mathbb{Q}$?

*Does every computable presentation of $\mathbb{A}$
admit such a computable basis?
So my proposal is to interpret "explicit" as computable,
inside a computable presentation of the algebraic numbers.
Note that Kevin's comment, which is closely related to
Cantor's argument that the collection of algebraic numbers
is countable, doesn't provide a computable basis. At each
stage of his construction, he is asking a negated
existential question "is this number not in the span of the
earlier numbers?", which we cannot expect to answer
computably in finite time. Thus, the basis that he provides
has on its face complexity $\Pi^0_1$, or co-c.e., and may
not be computable. This is the same complexity as the
complement of the halting problem, and is less explicit
than one might hope to achieve.
I don't know if there is a computable basis or not, but I
suspect there isn't. In this case, perhaps Kevin's sort of
solution is the most explicit possible, and
it may even be true that every basis is complete for
$\Pi^0_1$, and therefore Turing equivalent to the halting
problem. But I offer two observations.
First, the answer cannot depend
on the presentation of the field. That is, the answers to the
two questions above must be the same. The reason (as
Russell Miller just reminded me) is that the algebraic
closure of $\mathbb{Q}$ is computably categorical, meaning
that all computable presentations of it are isomorphic by a
computable isomorphism. Such an isomorphism would preserve
the Turing degree of any subset. So there would be a
computable basis for one if and only if there is a
computable basis in the other.
Second, if there is a c.e. basis, then it must be computable. The reason is that if we can enumerate the elements of a basis $B$, then we can also enumerate the complement of $B$, since a number $u$ is in the complement of $B$ if it is expressible as a rational linear combination of objects in $B$ other than $u$, and this we can find by searching if it is true. 
It doesn't seem to change the problem much to consider the
real algebraic numbers. Here, one has computable
categoricity as an ordered real-closed field.
Meanwhile, we wait for the computable model theorists to
show up with the answer...
A: Every computable field which is an algebraic extension of the rationals $\mathbb{Q}$ has a computable basis (as a vector space over $\mathbb{Q}$).  The idea is to build up this basis by recursion:  let $F_0 = \mathbb{Q}$, with basis $B_0=$ {$1$}, and, given a basis for $F_s$ over $\mathbb{Q}$, find the least element $x$ of $F$ whose minimal polynomial over $F_s$ has degree $d > 1$.  This can be done because $F_s$ has a splitting algorithm, enabling one to recognize irreducible polynomials in $F_s[X]$, uniformly in $s$.  Then $C_s=${$ 1, x, x^2, x^3,...x^{d-1}$} is a basis for $F_{s+1}=F_s[x]$ over $F_s$, and a basis $B_{s+1}$ for $F_{s+1}$ over $\mathbb{Q}$ is given by all products of one element of $C_s$ with one element of the basis $B_s$ for $F_s$ over $\mathbb{Q}$.  Since $1$ lies in $C_s$, we have $B_s \subset B_{s+1}$, and the union (over $s$) of all these $B_s$ will be a basis $B$ for $F$ over $\mathbb{Q}$.  The same construction would work with any finite field in place of $\mathbb{Q}$, and indeed over every c.e. ground field which has a splitting algorithm.
However, when $F$ is transcendental over $\mathbb{Q}$ (especially when it has infinite transcendence degree), this can no longer be done.  In this case a computable vector-space basis follows if there exists a computable transcendence basis for $F$ over $\mathbb{Q}$, but not all computable field extensions of $\mathbb{Q}$ have computable transcendence bases.  Metakides and Nerode produced a computable field of infinite transcendence degree over $\mathbb{Q}$ which has no computable vector-space basis over $\mathbb{Q}$.  One could probably also build a computable field $\mathbb{Q}$ with computable vector-space basis over $\mathbb{Q}$, but with no computable transcendence basis over $\mathbb{Q}$.
A discussion of splitting algorithms, over $\mathbb{Q}$ and over finitely generated extensions, appears in Harold Edwards' book Galois Theory.  Fried & Jarden is another good source.
