THE ISOMORPHISM PROBLEM FOR CLASSES OF COMPUTABLE FIELDS

WESLEY CALVERT

Abstract. Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out several examples. One motivation is to see whether some classes whose set of countable members is very complex become classifiable when we consider only computable members.

We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from nonclassifiable. For arbitrary fields — even real closed fields — we show that the isomorphism problem is Σ_{1}^{1} complete (the maximum possible), and for others we show that it is of relatively low complexity. We show that the isomorphism problem for algebraically closed fields, Archimedean real closed fields, or vector spaces is Π_{3}^{0} complete.

1. Introduction

We will consider a notion of “classification” for classes of computable structures. For some classes, there is a “classification,” or “structure theorem” of some kind. For instance, the classification of algebraically closed fields states that a single cardinal (the transcendence degree) completely determines the structure up to isomorphism. For other classes (graphs, for example, or arbitrary groups) such a result would be surprising, and when we introduce the necessary rigor we can prove that there is none to be found. They simply have more diversity than any structure theorem could describe.

A theory of classification should tell us which classes fall into which of these two categories. Such a theory, originating in the work of Shelah, has long been in use for elementary classes (see [20, 12]). There is also a well-developed theory for classes of countable structures, which uses Borel reducibility. This theory was developed by Friedman and Stanley [6], Becker, Hjorth, Kechris, Louveau, and others [3, 11].

Shelah’s theory of classifications considers structures of arbitrary cardinality. The Borel reducibility notion focuses on countable structures only. This difference is exemplified by the theory of dense linear orders, which is ℵ_{0}-categorical, but whose class of models is non-classifiable in the Shelah sense because for any uncountable κ there are 2^{κ} non-isomorphic models of size κ. However, in some classes which are non-classifiable in the Shelah sense, the complexity is in some way so intrinsic to the theory that it shows up even in the countable case, in the form of high Borel complexity.

The author was partially supported by NSF Grants DMS 9970452 and DMS 0139626. The author wishes to thank J. F. Knight for many helpful comments on this article.

We work only with structures which have for their universe a subset of ω, and identify structures with their atomic diagrams. Thus, for instance, a structure is computable if and only if its atomic diagram is computable as a set of Gödel numbers of sentences. Alternatively, we could use the quantifier-free diagram instead of the atomic diagram. Similarly, a structure is associated with the index of a Turing machine which enumerates its atomic diagram (assuming its universe is computable). In this paper I will write A_{a} for the computable structure with atomic diagram W_{a} and will consider only classes K of structures which have only computable members. Question 1.1. Are there some classes where this high complexity is apparent even in the class of computable models?

The answer is not immediately apparent. Any class of countable structures with high Borel complexity has 2^{ℵ_{0}} members up to isomorphism. It might seem that if we restrict to only countably many – and at that the most tangible members, the computable ones – we might have required so much regularity that the enormous complexity we saw before would be forbidden. It often happens that there is some structural characterization of which members of a class admit a computable structure, and perhaps such results (known and unknown) should mean that the set of computable members of some class cannot be too complicated.

Surprising or not, it turns out that we can still distinguish at the computable level between some “very complicated” classes and some “quite simple” ones. It is easy to tell whether two algebraically closed fields are isomorphic, and it is difficult to do the same for arbitrary fields, even if we only consider the computable models of each theory.

We are now prepared to make precise what I have meant by the terms “simple” and “complicated.” The following formalization was recently proposed by Goncharov and Knight [8]. Definition 1.2. The isomorphism problem, denoted E(K), is the set

{(a, b)|A_{a}, A_{b} ∈ K, and A_{a} ≃ A_{b}}

If the set of indices for computable members of K, denoted I(K), is hyperarithmetical, then E(K) is Σ_{1}^{1}. Intuitively, in the worst case, where E(K) is Σ_{1}^{1} complete, the easiest way to say that two members of K are isomorphic is to say, “There exists a function which is an isomorphism between them.” Often there are easier ways to check isomorphism, such as counting basis elements of vector spaces. Such a “shortcut” is a classification. As is discussed more fully in [8] and in section 3 of the present paper, this notion is closely related to more common understandings of classification, such as the production of a “nice” list of isomorphism types.

Several classes are well-known to have maximally complicated isomorphism problems. The following theorem summarizes several classical results. Proofs may be found in articles by Rabin and Scott [18], Goncharov and Knight [8], Morozov [15], and Nies [16]. Theorem 1.3. If K is the set of computable members of any of the following classes, then E(K) is Σ_{1}^{1} complete:

(1) Undirected graphs

(2) Linear orders

(3) Trees

(4) Boolean algebras (5) Abelian p-groups The following additions to the list follow easily from recent work by Hirschfeldt,

Khoussainov, Shore, and Slinko [9]. Theorem 1.4 (Hirschfeldt – Khoussainov – Shore – Slinko). If K is the set of computable members of any of the following classes, then E(K) is Σ_{1}^{1} complete:

6. Rings

7. Distributive lattices

8. Nilpotent groups

9. Semigroups This part of the paper will focus on calculating the complexity of the isomorphism

problem for classes of fields. We will make use of the example of undirected graphs, so in section 2 this example is worked out. Section 3 contains a proof that for the class of arbitrary computable fields, the isomorphism problem is maximally complicated. In section 4, we concentrate on algebraically closed fields, where the isomorphism problem is quite simple, just as we would expect. The example of vector spaces is a comfortable warm up for algebraically closed fields, so it is also included in this section. Section 5 treats real closed fields, both Archimedean (where the isomorphism problem is rather simple) and arbitrary (where it is ∑_{1}^{1} complete). In a later paper, I will consider certain classes of Abelian groups [5].

The goal of this paper is twofold. On one hand, the isomorphism problem gives us considerable insight into these classes and the great diversity possible among, for example, computable fields. On the other hand, these classes serve as benchmarks to show that the complexity of the isomorphism problem gives the “right” answers to distinguish between classifiable and non-classifiable classes.

2. Undirected Graphs

An older result, of which proofs are given in [15] and [8], shows that the isomorphism problem for the class of computable directed graphs is ∑_{1}^{1} complete. Friedman and Stanley [6] state as well-known the fact that the isomorphism problem for countable undirected graphs is Borel complete. It is also known that the isomorphism for undirected graphs is ∑_{1}^{1} complete. Morozov [15], Nies [16], and Rabin and Scott [18] each give a proof. Below, we give a slightly simplified version of Nies’s proof. The idea of the construction is that if there is a directed edge from n to m in our directed graph, we should have a connection between them in the undirected graph which is labeled in a particular way: n is connected to a triangle, which is connected to a pentagon, which is connected to m. Since we can distinguish the triangle from the pentagon, we can determine the direction of the connection.

The difficulty is in distinguishing which points are the actual “vertices” and which are the edge labels. This will be done by having an “Archimedean point” to which all of the “vertices” are connected, but none of the edge-labeling points. If the original directed graph was completely disconnected, then the Archimedean point will be the only one connected to infinitely many others. Otherwise, it will be the only point x where the pattern x-y-triangle-pentagon-z-x occurs. The “vertex” points are exactly those points which are directly connected to the Archimedean point. I do not mean to say that this information may be obtained effectively; only that it is isomorphism invariant.

Theorem 2.1. When K is the class of computable undirected graphs, E(K) is ∑_{1}^{1} complete.

Proof. The class of graphs (irreflexive, symmetric binary relations) is characterized by ∏_{1}^{0} axioms, so I(K) is ∏_{2}^{0} (identifying a set as the atomic diagram of some structure is ∏_{2}^{0} complete). Given a directed graph T, we will produce an undirected graph G, as described above. This construction will be uniformly computable in T, and will be injective on isomorphism types. We will use 1 for the Archimedean point, and we start with D(G)_{−1} = P_{−1} = C_{−1} = V_{−1} = ν_{−1} = ∅.

Step 6s: We will go a bit farther on connecting the Archimedean point to the vertices. In particular, for the first x ∈ V_{s−1}, if any, such that 1Gx ∉ D(G)_{6s−1} set D(G)_{6s} = D(G)_{6s−1} ∪ {1Gx}. If there is no such x, set D(G)_{6s} = D(G)_{6s−1}.

Step 6s + 1: In this step, we will check a connection from T, and if necessary, represent it in G. Let g(s) = (n_{s}, m_{s}) be a pairing function. First we should check whether n_{s} and m_{s} are already represented as vertices (i.e. if n_{s}, m_{s} ∈ dom(ν_{s−1})). If not, suppose n_{s} is not represented. Then find the least y not occurring in the diagram so far, and set V_{s} = V_{s−1} ∪ {y} and ν_{s} = ν_{s−1} ∪ {(n_{s}, y)}. If necessary, act similarly for m_{s}. Now since T is computable, we can check whether n_{s}T m_{s}. If we find that there is such a connection, and if (n_{s}, m_{s}) ∉ C_{3s−1} we find the least x_{0}, …, x_{7} which do not occur in the (finite) diagram so far, and which are not equal to 1. We then add to the D(G)_{6s+1} sentences giving the connections including the triangle and pentagon configuration. We should also mark this connection as being made, so let C_{3s} = C_{3s−1} ∪ {(n_{s}, m_{s})}. Otherwise, set D(G)_{6s+1} = D(G)_{6s} and C_{3s} = C_{3s−1}.

Step 6s+2: In the next two steps we will make sure that for any atomic sentence ϕ, either ϕ or ¬ϕ will occur in D(G). We find the first two elements x and y occurring in any sentence of D(G)_{6s+1} for which neither xGy nor ¬xGy is in the diagram so far. Now set

ψ = \{ \begin{matrix}xGy & if yGx ∈ D(G)_{6s+1} or if \{x, y\} = \{1, ν_{s}(r)\} for some r \\ ¬xGy & otherwise \end{matrix}

and D(G)_{6s+2} = D(G)_{6s+1} ∪ {ψ}.

Step 6s + 3: If n_{s} = ν_{s}(c) and m_{s} = ν_{s}(d) and c = d ∈ D(T), then we’ll have to say that n_{s} = m_{s} in G, as well. In that case, set D(G)_{6s+3} = D(G)_{6s+2} ∪ {n_{s} = m_{s}}, and set P_{s} = P_{s−1} ∪ {(n_{s}, m_{s})}. Otherwise, set D(G)_{6s+3} = D(G)_{6s+2} ∪ {¬n_{s} = m_{s}}.

Step 6s + 4: Now we need two steps to be careful about the equalities we have just declared, to make sure that our construction is well-defined on isomorphism types. In particular, we will have to make sure that any pair that is equal has all the same connections. At this step, for all (q, r) ∈ P_{s} and for all t < s, if qT t and (r, t) ∉ C_{3s}, then find the first available elements, and list the sentences necessary to form the triangle-pentagon pattern in them, as in step 6s + 1. Collect all such sentences as J_{s}, and set D(G)_{6s+4} = D(G)_{6s+3} ∪ J_{s} and C_{3s+1} = C_{3s} ∪ {(r, t)}.

Step 6s + 5: (This step is symmetric to 6s + 4.) For all (q, r) ∈ P_{s} and for all t < s, if rT t and (q, t) ∉ C_{3s}, then find the first available numbers, and list the sentences necessary to form the triangle-pentagon pattern in them, as in step 6s + 1. Collect all such sentences as J_{s}, and set D(G)_{6s+5} = D(G)_{6s+4} ∪ J_{s} and C_{3s+2} = C_{3s+1} ∪ {(q, t)}.

Let D(G) = ⋃_{s∈ω} D(G)_{s}. Now D(G) is the diagram of the graph we wanted

to build. If T_{1} and T_{2} are isomorphic directed graphs and we use this procedure to code them in undirected graphs G_{1} and G_{2} respectively, then an isomorphism f : T_{1} → T_{2} induces an isomorphism from G_{1} to G_{2}, which maps ν(x) ↦ ν(f(x)), elements connecting x and y to those connecting f(x) and f(y), and which is otherwise the identity. Conversely, suppose that G_{1} and G_{2} are products of this procedure, perhaps the outputs given directed graphs T_{1} and T_{2}, respectively, and that G_{1} ≃ G_{2}. Then the isomorphism (we could call it h) must preserve the Archimedean point, and as a result must map vertex points to vertex points. Also, for any two vertex points u_{1} and u_{2}, the subgraph u_{1}-triangle-pentagon-u_{2} occurs in G_{1} if and only if the sequence h(u_{1})-triangle-pentagon-h(u_{2}) occurs in G_{2}. Thus, there is also an isomorphism of the directed graphs T_{1} and T_{2}. □

3. Arbitrary Computable Fields

Intuition and experience tell us that the class of computable fields is quite complicated, perhaps so much that no classification could ever capture it. Previous work by Kudinov focused on existence of a computable “Friedberg enumeration”. Definition 3.1. A Friedberg enumeration of K up to isomorphism is a list of numbers, each of which is an index for a member of K, such that each isomorphism type from K occurs exactly once in the list. The enumeration is said to be computable (or hyperarithmetical), when this list is.

Goncharov and Knight had asked whether there was a computable Friedberg enumeration up to isomorphism of computable fields of fixed characteristic. Kudinov announced the following result: Theorem 3.2 (Kudinov). There is no computable Friedberg enumeration of the computable fields of characteristic 0.

Knowing the complexity of the isomorphism problem for a class can tell us about the existence of Friedberg enumerations. The following is in [8]: Proposition 3.3 (Goncharov-Knight). If I(K) is hyperarithmetical and there is a hyperarithmetical Friedberg enumeration of K up to isomorphism, then E(K) is hyperarithmetical.

The idea of the proof is that if E(K) is ∑_{1}^{1} (which it must always be) and there is a hyperarithmetical Friedberg enumeration of K up to isomorphism, then E(K) is also ∏_{1}^{1}.

We can prove the following: Theorem 3.4. When K is the class of computable fields of some fixed characteristic, E(K) is ∑_{1}^{1} complete.

Then we have the following strengthening of Kudinov’s result: Corollary 3.5. For any p, prime or zero, there is no hyperarithmetical Friedberg enumeration up to isomorphism of computable fields of characteristic p.

3.1. Borel Completeness for Fields: The Friedman-Stanley Embedding. In 1989, Friedman and Stanley [6] showed that the class of countable fields of characteristic 0 is Borel complete, the maximal level of complexity in their sense. They proved this by constructing an embedding from graphs into fields (a Borel embedding is a Borel measurable function which is well-defined and injective on isomorphism types).

Friedman and Stanley assume that they are given a graph whose connectedness relation is R. From this they construct a field. We will use \overline{F} to indicate the algebraic closure of F, and (S) for the smallest field containing S.

Consider {X_{i}}_{i∈ω}, algebraically independent over ℚ. Let F_{0} be the composite of all of the \overline{(ℚ(X_{i}))}, and define the extension

L(R) = F_{0}(\{\sqrt{X_{i} + X_{j}}|iRj\})

To deal with positive characteristic, we could replace ℚ with 𝔽_{p} and the square root with the qth root where q is relatively prime to p both in this construction and throughout the following argument. This function L : Graphs → F ields is both a Borel measurable function under the usual product topology [10], and well-defined on isomorphism classes. The difficulty is in showing that Proposition 3.6. L is injective on isomorphism classes.

Proof. In particular, it is difficult to show that \sqrt{X_{m} + X_{n}} cannot be expressed as a rational function of the various X_{i} and \sqrt{X_{j} + X_{k}} where \{j, k\} ≠ \{m, n\}. The main difficulties appear when we consider only the composite of \overline{(ℚ(X_{i}))} and \overline{(ℚ(X_{j}))} (where i ≠ j), and ask whether it contains \sqrt{X_{i} + X_{j}}. I am grateful to W. Dwyer for the proof of the following lemma. A different proof is given in the paper by Friedman and Stanley [6], and others still by Abhyankar [1] and Shapiro [19]. In any case, proving the following lemma in positive characteristic is quite difficult.

Lemma 3.7. \sqrt{X_{i} + X_{j}} ∉ (\overline{ℚ(X_{i})} ∪ \overline{ℚ(X_{j})}), where i ≠ j.

Proof. A polynomial p of degree n in \overline{(ℚ(X_{i}))} gives a branched n-sheeted covering where the fiber over any point a in \overline{(ℚ(X_{i}))} is the set of roots of p = a, and branch points represent the multiple roots (a Riemann surface). A continuous function to find the roots of the polynomial may be defined on this covering with branch points deleted, but not in any neighborhood including the branch points themselves. We first consider the possibility

\sqrt{X_{i} + X_{j}} = ∑_{k=1}^{n} a_{k}b_{k}

where a_{k} is algebraic over ℚ(X_{i}), and b_{k} is algebraic over ℚ(X_{j}). That is, ∑_{k=1}^{n} a_{k}b_{k}

gives one of the square roots.

Now for simplicity we can say that there is a single polynomial p_{i}(Z) over ℚ(X_{i}) of which all the a_{k} are roots, and similarly one p_{j} over ℚ(X_{j}) of which all the b_{k} are roots. We can view the composite field (\overline{ℚ(X_{i})} ∪ \overline{ℚ(X_{j})}) as \overline{ℚ(X_{i})} × \overline{ℚ(X_{j})}. Since p_{i} and p_{j} will each have only finitely many multiple roots and at most finitely many points at which the coefficients are not defined, we can define continuous functions giving a_{k} and b_{k} on the relevant covering spaces of

\overline{ℚ(X_{i})} \ \{these finitely many “bad points” of p_{i}, say e_{t}\}

and

\overline{ℚ(X_{t})} \ \{finitely many “bad points” of p_{j}, say f_{t}\}

Thus the expression ∑_{k=1}^{n} a_{k}b_{k} can be continuously defined on the relevant covering

space of \overline{ℚ(X_{i})} \ \{e_{t}\} × \overline{ℚ(X_{j})} \ \{f_{t}\}). We can view this as a plane with finitely many vertical and horizontal lines deleted. Since the multiple roots of Z^{2} = X_{i}+X_{j} lie along the antidiagonal X_{i} + X_{j} = 0, there is clearly a neighborhood in which

we can define ∑_{k=1}^{n} a_{k}b_{k} as a continuous function, but which contains points of the

antidiagonal, so we cannot define \sqrt{X_{i} + X_{j}} as a continuous function. Thus the two cannot be equal. To make the difference more transparent, we could say that anywhere on this neighborhood we stay on the same branch of the right-hand side, but move from one branch to another on the left-hand side.

In the more general case that

\sqrt{X_{i} + X_{j}} = \frac{∑_{k=1}^{n} a_{k}b_{k}}{∑_{k=1}^{n} c_{k}d_{k}}

we could simply write

(\sqrt{X_{i} + X_{j}})(∑_{k=1}^{n} c_{k}d_{k}) = ∑_{k=1}^{n} a_{k}b_{k}

and again the right-hand side can be defined continuously where the left-hand side cannot. □

There does not seem to be a way to modify this proof to cover the positive characteristic case. There is no apparent topology to replace the metric topology on the affine space, which we used here in declaring functions continuous or not. Also, while we could talk about the number of values of the “root function” and the right-hand-side “function,” there are points in the proof at which it is not obvious that values will not collapse.

If we simply add more X_{i}, then more dimensions are added to the picture, but nothing really changes, since the diagonal for \sqrt{X_{i} + X_{j}} is still in the same plane, and we can still find a neighborhood containing some point of it which contains no point of any line parallel to an axis. The next real problem comes up when we allow some square roots to be added. To simplify the task of visualization, and also to simplify the notation necessary, we will restrict the geometrical argument to a space whose F_{0}-dimension is the least possible to account for all X_{i} used in the expression. This allows us to refer to codimension, allowing an economical way to describe the higher-dimensional generalizations of the fact that lines intersect in points, planes intersect in lines, and so forth.

Lemma 3.8. Let F_{0} be as above. Then

\sqrt{X_{i} + X_{j}} ∉ F_{0}(\sqrt{X_{j} + X_{k}})

where i, j, and k are distinct.

Proof. Suppose not. First we will suppose again the simpler case where

\sqrt{X_{i} + X_{j}} = ∑_{s=1}^{n} ∏_{t=1}^{m_{s}} a_{st}

where each a_{st} is algebraic over a single X_{q} or is f_{st}\sqrt{X_{j} + X_{k}} for some f_{st} ∈ F_{0}. Since there are only a finite number of such X_{q} involved in the expression, let us collect, as before, polynomials p_{q}, one to account for all a_{st} algebraic over a single X_{q}. The multiple roots of p_{q} may be collected, as before, as {e_{qγ}}. Those used in the composition of f_{st} may be collected as {d_{stγ}}. The multiple roots corresponding to \sqrt{X_{i} + X_{j}} still form the diagonal (now a hyperplane, i.e. an algebraic surface of codimension 1) X_{i} + X_{j} = 0. Let x̂ be a point of X_{i} + X_{j} = 0, and let N be a ball around it of positive radius. Use M_{δ} to denote the (finitely many) hyperplanes X_{q} = e_{qγ}, X_{t} = d_{stγ}, and X_{j} + X_{k} = 0. Now M_{δ}^{c} (the complement of M_{δ}) is open, so N ∩ (⋂_{δ} M_{δ}) is a neighborhood containing a point of X_{i} + X_{j} = 0 and no point

of any M_{δ}. Thus, there is a neighborhood in which we stay on a single branch of the right-hand side of the supposed equation, but cross a branch point of the left hand side.

Just as before, the extension to the more general case,

\sqrt{X_{i} + X_{j}} = \frac{∑_{s=1}^{n} ∏_{t=1}^{m_{s}} a_{st}}{∑_{s=1}^{n} ∏_{t=1}^{m_{s}} b_{st}}

is quite easy. We clear the denominator and still have regions which are entirely fine for the right side of the equation but that the left finds unmanageable. □

Alternately, we could consider a homomorphism

F_{0}(\sqrt{X_{j} + X_{k}}) → F_{0}(\sqrt{X_{j} + X_{k}})

which sends X_{k} ↦ 0 but which is the identity on ℚ ∪ {X_{ℓ}}_{ℓ≠k}. If the lemma failed, this homomorphism would show that \sqrt{X_{i} + X_{j}} ∈ F_{0}, contrary to the previous lemma. A similar alternate proof is possible for the following lemma.

Similarly, one can establish

Lemma 3.9. Let F_{0} be as above. Then \sqrt{X_{i} + X_{j}} ∉ F_{0}(\{\sqrt{X_{m} + X_{n}}|\{m, n\} ≠ {i, j}}).

Proof. Suppose that the lemma fails. Then we suppose

\sqrt{X_{i} + X_{j}} = ∑_{s=1}^{n} ∏_{t=1}^{m_{s}} a_{st}

where each a_{st} is algebraic over a single X_{q} or is f_{st}\sqrt{X_{n} + X_{m}} for some f_{st} ∈ F_{0} and some {m, n} ≠ {i, j}. Acting just as before, we denote by p_{q} the polynomial accounting for all a_{st} which are roots of some polynomial over X_{q}. The left-hand side of the equation still gives us multiple roots along the hyperplane X_{i} + X_{j} = 0, the roots of the p_{q} still form hyperplanes parallel to the axes, just as before. The only difference from the previous case is that there are more hyperplanes of diagonal type (X_{m} + X_{n} = 0), but there is still a neighborhood in which the right side of the equation works, and the left does not. By this point, the usual extension to the more general form of a member of

F_{0}(\{\sqrt{X_{m} + X_{n}}|\{m, n\} ≠ \{i, j\}\})

is obvious. □

We will need an additional fact. If two fields of this kind are isomorphic, the isomorphism will move X_{i} to something interalgebraic with some X_{j}, since they are the elements whose algebraic closure is included. The change of X_{i} to X_{j} is clearly tolerable, since it merely corresponds to a permutation of the names of the vertices of a graph. However, we need to verify that the isomorphism does not foul up information on the connectedness relation.

Lemma 3.10. Let A ∼ B if and only if \overline{ℚ(A)} = \overline{ℚ(B)}. If X ∼ X_{i} and Y ∼ X_{j} then \sqrt{X + Y} ∉ (\overline{ℚ(X_{i})} ∪ \overline{ℚ(X_{j})}).

Proof. The proof of this lemma is trivial. If \sqrt{X + Y} ∈ (\overline{ℚ(X_{i})} ∪ \overline{ℚ(X_{j})}), then it is also in the (exactly equal) set (\overline{ℚ(X)} ∪ \overline{ℚ(Y)}), in contradiction to the previous lemma. □

Lemma 3.11. If Y_{i} ∼ X_{i} for all i, then

\sqrt{Y_{i} + Y_{j}} ∉ F_{0}(\{\sqrt{X_{m} + X_{n}}|\{m, n\} ≠ \{i, j\}\})

Proof. This proof is an almost equally obvious extension of earlier results. Let F_{1} denote the composite field of all the \overline{ℚ(Y_{i})}. The field

F_{0}(\{\sqrt{X_{m} + X_{n}}|\{m, n\} ≠ \{i, j\}\})

is equal to the field

F_{1}(\{\sqrt{X_{m} + X_{n}}|\{m, n\} ≠ \{i, j\}\})

We should note that each X_{i} is the root of some polynomial over Y_{i}. Now suppose

\sqrt{Y_{i} + Y_{j}} = ∑_{s=1}^{n} ∏_{t=1}^{m_{s}} a_{st}

where each a_{st} is algebraic over a single Y_{i} or is f_{st}\sqrt{X_{m} + X_{n}} for some f_{st} ∈ F_{1} and some {m, n} ≠ {i, j}. Let p_{q} again denote the polynomial accounting for all a_{st} algebraic over Y_{q}. The left-hand side still gives the same diagonal hyperplane Y_{i} + Y_{j} = 0. On the right-hand side, we have a finite union of hyperplanes parallel to the axes (the multiple roots of p_{q}), and also some more exotic hypersurfaces. These hypersurfaces are those of the form X_{m} + X_{n} = 0. However, these are not equal to Y_{i} + Y_{j} = 0, so for each such hypersurface P (of only finitely many) there is some neighborhood containing a point of Y_{i} + Y_{j} = 0 but no point of P. Thus, we can still find the necessary neighborhood in which the right-hand side of the equation is continuous and the left-hand side is not. The more general element works as always. □

We can now prove Proposition 3.6. Suppose that R and S are two graphs, and that L(R) ≃ L(S). Now by this isomorphism, each X_{i} ∈ L(R) is mapped to some Y_{i} ∼ X_{j} ∈ L(S). Certainly if nRm then \sqrt{X_{n} + X_{m}} ∈ L(R) and thus \sqrt{Y_{n} + Y_{m}} ∈ L(S). By the last lemma, if Y_{n} ∼ X_{p} and Y_{M} ∼ X_{q}, the last statement implies that \sqrt{X_{p} + X_{q}} ∈ L(S), so by the previous lemma pSq (since \sqrt{X_{p} + X_{q}} ∉ F_{0}(\{\sqrt{X_{m} + X_{n}}|\{m, n\} ≠ \{i, j\}\}) (that is, X_{p} + X_{q} only had a square root if we put one in to account for a connection of p and q in S). Similarly, we can argue that if nSm, then the corresponding elements are connected in R. Thus R ≃ S. □

3.2. Computable Construction of the Friedman-Stanley Embedding. It will turn out that a similar embedding produces computable fields from computable graphs, amounting to a reduction E(Graphs) ≤_{1} E(Fields). This will complete the proof. The only real modification necessary is to guarantee that if we start with a computable graph, we end up with a computable field. Important background work on computable fields may be found in [7] [14] [17].

We should note that since the class of fields of given characteristic has ∏_{2}^{0} axioms (stating that it is a commutative ring, plus the condition that for any element there exists a multiplicative inverse), I(K) is ∏_{2}^{0}. Given a computable directed graph with connectedness relation R, consider {X_{i}}_{i∈ω}, algebraically independent over ℚ. Let G_{0} be a computable field isomorphic to the composite of all of the \overline{ℚ(X_{i})}, and let M(R) be the extension G_{0}(\{\sqrt{X_{i} + X_{j}}|iRj\}). It remains to verify Proposition 3.12. M(R) has a computable copy, whose index can be obtained effectively from that of R.

Proof. Consider the language of fields, plus countably many constants X_{i}, with the theory of algebraically closed fields of characteristic 0 and the sentences stating that the X_{i} are algebraically independent. This theory is complete and decidable (since the theory of algebraically closed fields alone proves quantifier elimination), and so it has a computable model. Call this computable model G.

Once we have G, there is a c.e. G_{0}^{∗} ⊆ G which contains exactly those members of G which are algebraic over a single X_{i}. Further, there is a c.e. R^{∗} ⊆ G consisting of exactly \{\sqrt{X_{i} + X_{j}}|iRj\}. With these two sets, we can enumerate the elements of the smallest subfield containing G_{0}^{∗} ∪ R^{∗}, and we will call this F^{∗} ⊆ G. Note that F^{∗} has c.e. universe. Let e(R) be the index of the function with which we enumerate D(F^{∗}), and note that we can find it effectively in a uniform way from an index for D(R). Now by padding, we can replace the c.e. field F^{∗} by a field whose universe is computable. Let M̃ be the set of all (a, s) where a ∈ F_{s}^{∗} \ F_{s−1}^{∗}. It is clear that the reduct of M̃, with the operations (a, s) +_{M} (b, t) := (a +_{G} b, r) and (a, s) ·_{M} (b, t) := (a ·_{G} b, r) is a computable field isomorphic to M(R), where in each case r is the least such that the desired elements are in F_{r}^{∗}. It is also clear that an index for the function with which we enumerate this field is effectively obtained from e(R) in a uniform way. This completes the proof both of the proposition and of Theorem 3.4 in the case of characteristic zero. □

4. Algebraically Closed Fields and Vector Spaces

While arbitrary computable fields could be expected to be difficult to classify, the algebraically closed fields ought to be much simpler, since isomorphism can be checked by just comparing transcendence degree. Vector spaces, interesting in their own right, give us a glimpse of the methods to be used on algebraically closed fields while using simpler notation and being more intuitively accessible.

Vector spaces are classified by their dimension. A bijection of bases of vector spaces induces an isomorphism of the spaces. Since it is computationally not too hard to find a basis [13], we should expect that the isomorphism problem will be rather simple. Theorem 4.1. Fix an infinite computable field F, and let K be the class of computable vector spaces over F. Then E(K) is Π_{3}^{0} complete.

Proof. To see that the problem is Π_{3}^{0}, we first note that I(K) is Π_{2}^{0}, since the class can be axiomatized with Π_{1}^{0} axioms declaring that the structure is an additive Abelian group and a module, and since the statement “a is the index of some structure” is Π_{2}^{0}. We will formulate a sentence to say that A_{a} and A_{b} have the same dimension. The statement

D_{n} = ∃(x_{1}, ..., x_{n}) ⋀_{ā≠0} ⋀(∑_{i=1}^{n} a_{i}x_{i} ≠ 0)

(which is Σ_{2}^{0}) states that there are at least n linearly independent elements. Now we can write

∀n[A_{a} ⊧ D_{n} ↔ A_{b} ⊧ D_{n}]

(which is Π_{3}^{0}), and the conjunction of this statement with a, b ∈ I(K) defines E(a, b).

To see that the problem is Π_{3}^{0} complete, we will take a known Π_{3}^{0} complete set S, and construct a uniformly computable sequence of vector spaces (V (n))_{n∈ω} such that V (n) ≃ V^{∞} if and only if n ∈ S, where V^{∞} is an infinite dimensional vector space. This will show that if e is the index of V^{∞}, E(a, e) is Π_{3}^{0} complete.

Define Cof = {e|W_{e} is cofinite}, where W_{e} is the domain of the eth partial recursive function, and take S = \overline{Cof}. Now V (n) will be a vector space with dimension the same as card(\overline{W_{n}}). Note that Cof is Π_{3}^{0} complete [21].

We begin by letting {a_{i}}_{i∈ω} be a basis for a computable copy of V^{∞}, and by considering a set {b_{i}}_{i∈ω}. Let λ_{i} enumerate the linear combinations of b_{i}. We will construct f and D(V (n)) to meet the following conditions:

P_{e}^{1} : λ_{e} = 0 ∈ D(V (n)) or ¬λ_{e} = 0 ∈ D(V (n))
P_{e}^{2} : b_{e} ∈ dom(f)
Q_{e} : f(b_{e}) is linearly independent of b_{0}, ...b_{e−1} if and only
if e ∉ W_{n}

Thus, im(f) will be a subspace of V^{∞} which we will call V (n), and will have the desired properties. We say that P_{e}^{1} requires attention at stage s if λ_{e} = 0 ∉ D(V (n))_{s} and ¬λ_{e} = 0 ∉ D(V (n))_{s} and i < \frac{s}{2} wherever b_{i} is included in λ_{e}. Q_{e} requires attention at stage s if e ∈ W_{n,s} and Q_{e} has not received attention previously. Let f_{0} be the homomorphism induced by taking b_{i} ↦ a_{i}, and D(V (n))_{0} = ∅.

At stage 2s, let ℓ_{s} be the first e such that P_{e}^{1} requires attention. We can then find whether f_{s}(λ_{ℓ_{s}}) = 0. If so, let D(V (n))_{2s+1} = D(V (n))_{2s} ∪ {λ_{ℓ_{s}} = 0}. Otherwise, add ¬λ_{ℓ_{s}} = 0.

At stage 2s + 1, we will work on Q_{e}. Let x_{s} be the least e such that Q_{e} requires attention. Let δ_{s}(b_{1}, ..., b_{N}) be the (finite) conjunction of all sentences in D(V (n))_{2s+1}. Because the theory of vector spaces is strongly minimal and the closure of any set except zero is infinite, there is some â_{x_{s}} ∈ Cl(a_{0}, a_{1}, ..., a_{x_{s}−1}) such that V^{∞} ⊧ δ_{s}(f_{s}(b_{0}), f_{s}(b_{1}), ..., f_{s}(b_{x_{s}−1}), â_{x_{s}}, f_{s}(b_{x_{s}+1}), ..., f_{s}(b_{N})). We then define

f_{s+1}(b_{i}) = \{ \begin{matrix}â_{x_{s}} & if i = x_{s} \\ f_{s}(b_{i}) & otherwise \end{matrix}

and let D(V (n))_{2s+2} = D(V (n))_{2s+1}.

Now it is clear that for any e, there is some stage at which P_{e}^{1} will receive attention, after which it will never again be injured. Further, P_{e}^{2} is never injured.

Finally, Q_{e} will either be satisfied at every stage (e ∉ W_{n}), or it will receive attention at some stage, after which it will never be injured again. □

Theorem 4.2. The isomorphism problem for the class of computable algebraically closed fields of fixed characteristic is Π_{3}^{0} complete.

Proof. The construction is very similar to the previous one, except that dimension is replaced by transcendence degree, and F -linear combinations are replaced by polynomial combinations. The sentence

T_{n} = ∃(x_{0}, ...x_{n}) ⋀ ⋀(∑_{i=1}^{2^{n}}(∏_{j=0}^{n} x_{j}^{p_{ij}}) ≠ 0)

where the conjunction is taken over all {p_{ij}}_{1≤i≤2^{n},1≤j≤n} states that the field has transcendence degree at least n. Note that even in positive characteristic, this conjunction is necessarily infinite, since there is at least one irreducible polynomial in every degree. Now we can write

∀n[A_{a} ⊧ T_{n} ↔ A_{b} ⊧ T_{n}]

in conjunction with a, b ∈ I(K) for E(a, b). Note that I(K) is Π_{2}^{0}.

We will build a uniformly computable sequence (F (n))_{n∈ω} of algebraically closed fields such that F (n) will have transcendence degree equal to the cardinality of \overline{W_{n}}. Just as before, this will establish the theorem.

We begin by letting {a_{i}}_{i∈ω} be a transcendence base for a computable copy of F^{∞} (the algebraically closed field of infinite transcendence degree), and by considering a set {b_{i}}_{i∈ω}. Let λ_{i} enumerate the polynomial combinations of b_{i}. We will construct f and D(F (n)) to meet the following conditions:

P_{e}^{1} : λ_{e} = 0 ∈ D(F (n)) or ¬λ_{e} = 0 ∈ D(F (n))
P_{e}^{2} : b_{e} ∈ dom(f)
Q_{e} : f(b_{e}) is algebraically independent of b_{0}, ...b_{e−1} if and only if we
have e ∉ W_{n}

Thus, im(f) will be a subset of F^{∞} which we will call F (n), and will have the desired properties. We say that P_{e}^{1} requires attention at stage s if λ_{e} = 0 ∉ D(F (n))_{s} and ¬λ_{e} = 0 ∉ D(F (n))_{s} and i < \frac{s}{2} wherever b_{i} is included in λ_{e}. Q_{e} requires attention at stage s if e ∈ W_{n,s} and Q_{e} has not received attention previously. Let f_{0} be the homomorphism induced by taking b_{i} ↦ a_{i}, and D(F (n))_{0} = ∅.

At stage 2s, let ℓ_{s} be the first e such that P_{e}^{1} requires attention. We can then find whether f_{s}(λ_{ℓ_{s}}) = 0. If so, let D(F (n))_{2s+1} = D(F (n))_{2s} ∪ {λ_{ℓ_{s}} = 0}. Otherwise, add ¬λ_{ℓ_{s}} = 0.

At stage 2s + 1, we will work on Q_{e}. Let x_{s} be the least e such that Q_{e} requires attention. Let δ_{s}(\overline{b}) be the (finite) conjunction of all sentences in D(F (n))_{2s+1}. Again using strong minimality, there is some â_{x_{s}} in the closure of the set of a_{i} for i < X_{s} such that

F^{∞} ⊧ δ_{s}(f_{s}(b_{0}), f_{s}(b_{1}), ..., f_{s}(b_{x_{s}−1}), â_{x_{s}}, f_{s}(b_{x_{s}+1}), ..., f_{s}(b_{N}))

We then define

f_{s+1}(b_{i}) = \{ \begin{matrix}â_{x_{s}} & if i = x_{s} \\ f_{s}(b_{i}) & otherwise \end{matrix}

and let D(F (n))_{2s+2} = D(F (n))_{2s+1}.

Again it is clear that for any e, there is some stage at which P_{e}^{1} will receive attention, after which it will never again be injured. Further, P_{e}^{2} is never injured. Finally, Q_{e} will either be satisfied at every stage (e ∉ W_{n}), or it will receive attention at some stage, after which it will never be injured again. □

5. Real Closed Fields

Knowing that algebraically closed fields are very simple, but having the suspicion that fields in general will be more complicated, it would be interesting to know about other restrictions of fields. K. Manders suggested the example of real closed fields, whose model theory is reasonably well-behaved, but which is unstable. The complexity is all in the infinite elements. Theorem 5.1. If K is the class of Archimedean real closed fields, then E(K) is Π_{3}^{0} complete.

Proof. Recall that a real closed field is an ordered field satisfying the additional condition that each odd-degree polynomial has a root. Thus, the class of real closed fields can be axiomatized by a computable infinitary Π_{2} sentence, as can the class of Archimedean real closed fields (by adding the sentence that for each element x, some finite multiple of 1 is greater than x). Archimedean real closed fields are classified simply by the cuts that are filled, so the statement

∀x, z ∃x̂, ẑ ⋀_{q∈ℚ} ⋀[(A_{a} ⊧ q ≤ x ⇔ A_{b} ⊧ q ≤ x̂)]∧

∧ ⋀_{q∈ℚ} ⋀[(A_{b} ⊧ q ≤ z ⇔ A_{a} ⊧ q ≤ ẑ)]

defines the relation A_{a} ≃ A_{b}, showing that it is, at worst, Π_{3}^{0}.

Lemma 5.2. There exists a uniformly computable sequence {a_{i}}_{i∈ω} of real numbers which are algebraically independent.

Proof. Lindemann’s theorem, a known result, states (in one form) that if λ_{1}, λ_{2}, …, λ_{k} are algebraic numbers linearly independent over the rationals, then e^{λ_{1}}, …, e^{λ_{k}} are algebraically independent [2]. Further, it is well known that the set \{\sqrt{2}, \sqrt{3}, \sqrt{5}, … \} is linearly independent (a proof may be found in [4]). □

Now consider the language (+, ·, 0, 1, {a_{i}}_{i∈ω}), and the theory consisting of the axioms of real closed fields and the set A. This is a complete decidable theory, and so has a computable model. The set of elements algebraic over the set of a_{i} is c.e. and by padding we can find a computable structure M = (M, +, ·, 0, 1, ≤, {a_{i}}_{i∈ω}) where M is the real closure of {a_{i}}_{i∈ω}.

We are now ready to prove the completeness part of the theorem. We will start with a set {b_{ij}}_{i,j∈ω}, D_{−1} = ∅, a list λ_{i} of all (positive) atomic sentences in the language of ordered fields with constants b_{ij}, and a function f_{−1} : b_{ij} ↦ a_{i}. Let S = {n| ∀i∃j∀zR(i, j, z, n)} be an arbitrary Π_{3}^{0} set. The proof will be similar to the proof for algebraically closed fields in that we will construct a uniformly computable sequence F (n) of real closed fields such that F (n) ≃ M exactly when n ∈ S. Set m_{t,s} = 0 and I_{s,−1} = D_{−1} = ∅ for all (t, s). We wish to meet the following requirements:

P_{e}^{1} : λ_{e} = 0 ∈ D or ¬λ_{e} = 0 ∈ D
P_{e}^{2} : b_{i,j} ∈ dom(f)
Q_{e} : For each i, if n ∈ S there exists some b_{ij} which fills the same

cut in F (n) that a_{i} fills in M. Otherwise there is no such b_{ij}.

At stage 2s, find the least i such that λ_{i} ∉ D_{s−1} and ¬λ_{i} ∉ D_{s−1}. Without loss of generality say that λ_{i} is of the form p(b_{j_{0}}, …, b_{j_{n}})Q0 where Q is = or ≤. Now if M ⊧ p(f_{s−1}(b_{j_{0}}), …, f_{s−1}(b_{j_{n}}))Q0 then set D_{s} = D_{s−1} ∪ {λ_{i}}. Otherwise, D_{s} = D_{s−1} ∪ {¬λ_{i}}.

At stage 2s + 1, for each t < s we will check whether for all z < s we have R(t, m_{t,s}, z, n). If this holds, set I_{s,t} = I_{s,(t−1)} and m_{t,(s+1)} = m_{t,s}. Otherwise set m_{t,(s+1)} = min{k > m_{t,s}|b_{tk} ∉ ⋃_{q<s} I_{q} and b_{tk} = b_{tm_{t,s}} ∉ D_{s}}. Now let δ_{s}(b⃗, x) be the conjunction of all sentences in D_{s} true on b_{tm_{t,s}}, and note that the set it defines contains an interval, since everything in it must be true in M of a_{t}. There is some rational r_{t,m_{t,s}} in this interval, which we can find effectively, and we set I_{s,t} = I_{s,(t−1)} ∪ {(t, m_{t,s}, r_{t,m_{t,s}}} ∪ {(t, k, r_{t,m_{t,s}})|D_{s} ⊢ b_{tk} = b_{tm_{t,s}}}. Note that this last addition can be made effectively, since only finitely many b_{tk} will have been mentioned, and since the theory of real closed fields is decidable. Let I_{s} = ⋃_{t<s} I_{s,t}. Now we change the function:

f_{s}(b_{ij}) = \{ \begin{matrix}r̂ & if (i, j, r̂) ∈ I_{s} \\ f_{s−1}(b_{ij}) & otherwise \end{matrix}

Let D(F (n)) = ⋃_{s∈ω} D_{s}, and we will call the structure whose diagram this is F (n). Now if n ∈ S, for each i there will eventually be some j such that we always leave b_{ij} ↦ a_{i}, so the cut corresponding to a_{i} is filled, and F (n) ≃ M. Otherwise, for some i, each b_{ij} will be mapped to some rational, and the isomorphism will fail. □

When we add positive infinite elements, however, we have a great deal of freedom in the structure of the field.

Theorem 5.3. If K is the class of real closed fields, then E(K) is Σ_{1}^{1} complete.

Proof. We will say that a ⪯ b exactly when a^{n} ≤ b for some n ∈ ω. We say that a ≈ b (a is comparable to b) if a ⪯ b and b ⪯ a. The proof will depend on realizing an arbitrary computable linear order as the order type of the comparability classes of infinite elements.

Lemma 5.4. Given a computable linear order L, there is a computable structure R(L)^{∗} = (R̄, +, ·, 0, 1, ≤, {X_{i}}_{i∈ω}), an expansion of a real closed field, in which X_{i} ⪯ X_{j} if and only if i ≤_{L} j, whose index is computable from an index for L.

Consider the language of ordered fields, plus infinitely many constants X_{i}, with the theory of real closed fields, and the sentences for each i stating that X_{i} is greater than any polynomial in {X_{j}|j <_{L} i}, and that all are greater than polynomials in 1. This is a complete, decidable theory, and thus has a computable model G. There is a c.e. subset R̃ ⊆ G containing exactly the elements algebraic over {X_{i}}_{i∈ω}. From an index for L, we can effectively find an index e(L) for the function enumerating R̃. Again we can pad to find an isomorphic structure R(L)^{∗} with computable universe, as claimed. Let R(L) denote the reduct of R(L)^{∗} to the language of ordered fields.

So we have encoded arbitrary linear orders into real closed fields, and all that remains is to make sure that this operation is well-defined and injective on isomorphism types. The well-definedness is clear, since an isomorphism of linear orders would just amount to a permutation of the labels for the X_{j}. It is also clear that if h is an isomorphism h : R(L_{1}) → R(L_{2}), then for a, b ∈ R(L_{1}), a ⪯ b if and only if h(a) ⪯ h(b), but it requires some verification to see that for a in the comparability class of some X_{i}, h(a) must be in the comparability class of some X_{j}. Once this is shown, h will induce an isomorphism of orders h̃, where if h maps the class of X_{i} to that of X_{j}, then h̃ : i ↦ j. I am grateful to L. van den Dries for suggesting the proof of the following lemma.

Lemma 5.5. Let F be R(L) for some linear order L. Let C be a positive infinite comparability class of elements of F. Then C is the comparability class of one of the X_{i}.

Proof. Suppose we have a real closed field K, and we add a single positive infinite element x > K. Let K((X^{ℚ})) denote the set of formal series f = ∑_{q∈ℚ} a_{q}X^{q}, where

a_{q} ∈ K and a_{q} = 0 except for q in some well-ordered set. There is an isomorphism rcl(K(x)) ≃ K((X^{ℚ})) mapping x ↦ X^{−1}. Now suppose that y ∈ K((X^{ℚ})), and y = ∑_{q∈ℚ} b_{q}X^{q}. Further, suppose that for all x ∈ K, we have y > x (that is, y is an

infinite element over K). Let q̂ be the least such that bq̂ ≠ 0. I claim that q̂ < 0. If q̂ ≥ 0, then y ≤ b_{0} + 1, but b_{0} + 1 ∈ K, giving a contradiction. So q̂ < 0. Now X^{q̂−1} > y; that is, (X^{−1})^{1−q̂} > y, so y ≈ t^{−1}. Thus, rcl(K(x)) has exactly one more comparability class than K.

Given this, the lemma is relatively easy. Using the previous paragraph as an induction step, it is easy to show that for L a finite linear order, the lemma holds. Further, since any element in R(L) is algebraic over finitely many X_{i}, R(L) = ⋃_{I} rcl(R({X_{i}}_{i∈I})) where I is a finite subset of ω. This completes the proof of both

the lemma and the theorem. □

□

It is worthwhile to note that Theorem 5.3 implies the characteristic 0 case of Theorem 3.4. This proof is certainly simpler. However, the earlier proof covers positive characteristic and stresses the relationship with Borel complexity. Also, it offers an opportunity to simplify, at least for positive characteristic, the difficult argument of the Friedman–Stanley paper.

References

1. S. Abhyankar, On the compositum of algebraically closed subfields, Proc. Amer. Math. Soc. 7 (1956), 905–907.

2. A. Baker, Transcendental number theory, Cambridge University Press, 1975.

3. H. Becker and A. S. Kechris, The descriptive set theory of polish group actions, London Mathematical Society Lecture Note Series, vol. 232, Cambridge University Press, 1996.

4. A. S. Besicovitch, On the linear independence of fractional powers of integers, J. London Math. Soc. 15 (1940), 3–6.

5. W. Calvert, The isomorphism problem for classes of computable Abelian groups, preprint, 2003.

6. H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, J. Symbolic Logic 54 (1989), 894–914.

7. A. Frolich and J. C. Sheperdson, Effective procedures in field theory, Philos. Trans. Roy. Soc. London. Ser. A 248 (1956), 407–432.

8. S. S. Goncharov and J. F. Knight, Computable structure and non-structure theorems, Algebra and Logic 41 (2002), 351–373.

9. D. Hirschfeldt, B. Khoussainov, R. Shore, and A. M. Slinko, Degree spectra and computable dimensions in algebraic structures, Ann. Pure Appl. Logic 115 (2002), 71–113.

10. G. Hjorth, Classification and orbit equivalence relations, American Mathematical Society, 1999.

11. G. Hjorth, A. S. Kechris, and A. Louveau, Borel equivalence relations induced by actions of the symmetric group, Annals of Pure and Applied Logic 92 (1998), 63–112.

12. W. Hodges, What is a structure theory?, Bull. London Math. Soc. 19 (1987), 209–237.

13. G. Metakides and A. Nerode, Recursively enumerable vector spaces, Ann. Math. Logic 11 (1977), 146–171.

14. , Effective content of field theory, Ann. Math. Logic 17 (1979), 289–320.

15. A. S. Morozov, Functional trees and automorphisms of models, Algebra and Logic 32 (1993), 28–38.

16. A. Nies, Undecidable fragments of elementary theories, Algebra Universalis 35 (1996), 8–33.

17. M. O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360.

18. M. O. Rabin and D. Scott, The undecidability of some simple theories, preprint.

19. D. B. Shapiro, Composites of algebraically closed fields, J. Algebra 130 (1990), 176–190.

20. S. Shelah, Classification of first order theories which have a structure theorem, Bull. Amer. Math. Soc. (N.S.) 12 (1985), 227–232.

21. R. I. Soare, Recursively enumerable sets and degrees, Springer-Verlag, 1987.

Department of Mathematics, 255 Hurley Hall, University of Notre Dame, Notre Dame, Indiana 46556

   E-mail address: wcalvert@nd.edu