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 $\bar\mathbb{Q}$ of algebraic numbers, meaning the algebraic closure of $\mathbb{Q}$, the natural questions would seem to be:

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

• Does every computable presentation of $\bar\mathbb{Q}$ 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.

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 for which one might hope, and it may even be true that every basis is complete for $\Pi^0_1$, and therefore Turing equivalent to the halting problem.

One thing I know, however, is that the answer cannot depend on the presentation of the field. Thus, 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.

Another thing I know is that 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 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...

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...

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 $\bar\mathbb{Q}$ of algebraic numbers, meaning the algebraic closure of $\mathbb{Q}$, the natural questions would seem to be:

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

• Does every computable presentation of $\bar\mathbb{Q}$ 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.

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 for which one might hope, and it may even be true that every basis is complete for $\Pi^0_1$, and therefore Turing equivalent to the halting problem.

What I do know, however, is that the answer cannot depend on the presentation of the field. Thus, 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.

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...

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 $\bar\mathbb{Q}$ of algebraic numbers, meaning the algebraic closure of $\mathbb{Q}$, the natural questions would seem to be:

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

• Does every computable presentation of $\bar\mathbb{Q}$ 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.

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 for which one might hope, and it may even be true that every basis is complete for $\Pi^0_1$, and therefore Turing equivalent to the halting problem.

One thing I know, however, is that the answer cannot depend on the presentation of the field. Thus, 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.

Another thing I know is that 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 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...