text:
# Effects of the Dzyaloshinskii-Moriya interaction on low energy magnetic excitations in copper benzoate

## Abstract

We have investigated the physical effects of the Dzyaloshinskii-Moriya (DM) interaction in copper benzoate. In the low field limit, the spin gap is found to vary as $`H^{2/3}\mathrm{ln}^{1/6}(J/\mu _BH_s)`$ ($`H_s`$: an effective staggered field induced by the external field $`H`$) in agreement with the prediction of conformal field theory, while the staggered magnetization varies as $`H^{1/3}`$ and the $`\mathrm{ln}^{1/3}(J/\mu _BH_s)`$ correction predicted by conformal field theory is not confirmed. The linear scaling behavior between the momentum shift and the magnetization is broken. We have determined the coupling constant of the DM interaction and have given a complete quantitative account for the field dependence of the spin gaps along all three principal axes, without resorting to additional interactions like interchain coupling. A crossover to strong applied field behavior is predicted for further experimental verification.

Recently some novel magnetic properties were discovered in a variety of quasi-one dimensional materials, such as copper benzoate Cu(C6D5COO)23D2ODen1 ; Den2 , Yb4As3 Kohgi ; Fulde ; Osh2  and BaCu2Si2O7Tsukada . In these materials, the Dzyaloshinskii-Moriya (DM) interactionDyz ; Mor ; Osh1  plays an important role, especially in an applied magnetic field. This has stimulated extensive investigation on the physical properties of the DM interaction. However, this interaction is rather difficult to handle analytically, which has brought much uncertainty in the interpretation of experimental data and has limited our understanding of many interesting quantum phenomena of low-dimensional magnetic materials.

For copper benzoate, Dender et alDen1 ; Den2  found that the spin excitation gap shows a peculiar field dependence, $`\mathrm{\Delta }H^{0.65}`$, in low fields. On the contrary, excitations remain gapless in the S=1/2 Heisenberg model below a critical field. Oshikawa and Affleck (OA) suggested that this field dependence of the gap is due to a staggered magnetic field induced by the DM interaction in addition to the staggered g-factor in a uniform fieldmutter ; Osh1 . However, a satisfactory explanation for the field-dependence of the energy gaps in all three directions is still lackingEss ; lou . It was argued that the inconsistency between the experimental data and theoretical results might be due to the neglect of the interchain coupling and/or anisotropic interaction terms in the low-field effective model used by Oshikawa and Affleck Osh1 ; Ess . We believe this issue can be clarified by a thorough study of the DM interaction and a direct comparison with experiments.

Copper benzoate is a quasi-1D spin-1/2 antiferromagnetic Heisenberg system. The chain direction is the c-axis. It contains two types of alternating and slightly tilted CuO8 octahedra. This leads to two inequivalent Cu++ ions and an alternating DM coupling Date . In an applied field, copper benzoate can be modeled by the following Hamiltonian,

$`\widehat{H}={\displaystyle \underset{i}{}}`$ $`(J\widehat{𝐒}_i\widehat{𝐒}_{i+1}()^i𝐃\widehat{𝐒}_i\times \widehat{𝐒}_{i+1}`$ (1)
$`\mu _B𝐇[𝐠^u+()^i𝐠^s]\widehat{𝐒}_i)`$
where the three terms in the summation are the antiferromagnetic Heisenberg, DM and Zeeman splitting interactions, respectively. The exchange coupling constant $`J`$, determined from the neutron scattering measurements, is about $`1.57\mathrm{meV}`$. The DM interaction is much weaker than the Heisenberg term. The $`𝐃`$-vector, primarily aligned along the $`a^{\prime \prime }`$ axis, will be determined numerically. $`𝐠^u`$ and $`𝐠^s`$ are the uniform and staggered components of the alternating g-tensor as given in Ref. Date,  for copper benzoate.

The DM term can in principle be eliminated by performing a spin rotation about the $`𝐃`$ vector by an angle $`\alpha =\pm \frac{1}{2}\mathrm{tan}^1(D/J)`$ on the alternating sites. This results in a small exchange anisotropy and an effective staggered magnetic field in addition to the $`𝐠^s`$-term in (1). The total effective staggered field is approximately given by

$$𝐇_s\left(𝐠^s\frac{1}{2J}𝐃\times 𝐠^u\right)𝐇$$
(2)
up to the leading order in $`D/J`$. In Ref. Osh1, , OA studied the isotropic Heisenberg model with a staggered field after eliminating the DM term and neglecting all anisotropic terms. They estimated that the DM coupling constant is about $`𝐃=(0.13,0.0,0.02)J`$ from the specific heat, neutron scattering and ESR measurement dataOsh1 ; Den1 .

In order to explore the low-energy properties of copper benzoate, we use density matrix renormalization group (DMRG) white ; peschel  to study directly the Hamiltonian defined by Eq. (1). Since neither the total spin nor its z-component is a good quantum number, the calculation is computer time consuming. Open boundary conditions are used and up to 400 states are retained in our calculation. The convergence of the results is systematically examined and the truncation error is less than $`10^7`$. To obtain the values of gaps and magnetizations in the thermodynamic limit, an extrapolation from the DMRG calculations up to 1000 sites is done.

Figure 1 shows the spin excitation gap as a function of inverse lattice size $`L`$ in different applied fields $`H`$. In zero field, there is no gap in the excitation spectrum in the thermodynamic limit and the gap decreases monotonically with $`L`$ increasing. However, in finite fields, the size dependence of the gap becomes more complicated and changes dramatically with $`H`$ increasing. The oscillations of the gaps are due to the competition between the uniform and staggered magnetic fields. The most pronounced oscillation occurs when the contributions to the Zeeman energy from these two fields become comparable, and the characteristic length scale of the oscillation is inversely proportional to the energy gap. Since the gap along $`a^{\prime \prime }`$-axis is much smaller than other directions, the oscillation looks stronger for $`H=(7,0,0)T`$ than for other cases.

Figure 2 shows the field dependence of the gap with $`𝐃=(0.13,0.0,0.02)J`$. In low fields, we find that the gap is well described by the following equation

$$\mathrm{\Delta }_\alpha =C^\alpha H^{2/3}\mathrm{ln}^{1/6}(J/\mu _BH_s),$$
(3)
as predicted by Oshikawa and Affleck. By fitting the numerical data with the above equation, we find that the coefficient $`C^\alpha `$ is given by $`C=(0.0072,0.059,0.097)`$ for $`𝐃=(0.13,0.0,0.02)J`$. In this system, the gap is finite even in very low field. This is completely different from the pure Heisenberg model whose excitations remain gapless until the spin polarization induced by the applied field becomes saturated. This difference results from the effective staggered magnetic field induced by the alternating g-tensor and the DM interaction. Since this staggered field couples directly to the strongest spin fluctuation mode at $`q=\pi `$, it gives rise to the instability of the ground state and opens a gap in the excitation spectrum. In high fields, the gap varies almost linearly with $`H`$ and its slope is proportional to the corresponding value $`g_{\alpha \alpha }^u`$. In the intermediate field regime, the gap varies non-monotonically with $`H`$ and shows a local minimum around $`H25T`$ in all three directions. This non-monotonic behavior of the gap is also due to the competition between the applied field and the induced staggered field. However, we find that this competition does not lead to a phase transition in the ground state in this crossover regime, since the ground state energy drops continuously and smoothly with $`H`$.

Now let us turn to the issue whether the model (1) is sufficient to describe the low-energy magnetic properties of copper benzoate. In the effective field theory, the critical exponents of the gaps are determined by the relevant and marginal operators in the low field limit. However, as this theory contains only the contribution of the dominant effective staggered field and ignores all other anisotropic terms after eliminating the DM term, it cannot explain the field-dependence of the gaps along all three principal axes. Moreover, since the energy gap is very sensitive to the DM interaction, the value of $`𝐃`$-vector determined from this theory, $`𝐃=(0.13,0.0,0.02)J`$Osh1 , would also be inaccurate.

To determine accurately the value of $`𝐃`$, we have evaluated and analyzed the field dependence of the gaps around $`𝐃=(0.13,0.0,0.02)J`$. By comparison with experimentsDen2 , we find that the gaps for $`𝐃=(0.11,0.0,0.0)J`$ give the best fit to the experimental data in all three directions (Figure 3). It also agrees with the recent ESR data for $`H//c^{\prime \prime }`$Nojiri  as well as the results of Essler for $`H//b`$ and in low fields for $`H//c^{\prime \prime }`$Ess . For this $`𝐃`$ value, our numerical results for the gap ratios $`\mathrm{\Delta }_{a^{\prime \prime }}:\mathrm{\Delta }_b:\mathrm{\Delta }_{c^{\prime \prime }}`$ in low fields are $`1:1.92:3.56`$, in agreement with experiments. However, for $`𝐃=(0.13,0.0,0.02)J`$, the low field gap ratios are $`1:8.2:13.5`$ and the theoretical results agree with the experimental data only along the $`c^{\prime \prime }`$-axis (Figure 3). Therefore the Hamiltonian (1) is indeed an appropriate model for copper benzoate and the discrepancy between the effective field theory and experiments is due to the neglect of the anisotropic terms rather than due to the interchain coupling as previously suggestedOsh1 .

For the S=1/2 Heisenberg model, the momentum of the antiferromagnetic soft mode is shifted from $`\pi `$ to $`\pi \pm \delta q`$ in an applied field. This leads to an incommensurate peak in the longitudinal structure factor. The momentum shift is predicted to be proportional to the magnetization:

$$\delta q=2\pi M(H).$$
(4)
This linear relationship between the momentum shift and the magnetization was examined by Dender at al for copper benzoateDen2 . They found that the momentum shifts at $`H=3.5,5,7T`$ for $`𝐇//b`$ were consistent with the theoretical results for the pure Heisenberg model Muller  with $`g=2.059`$ and $`J=1.57`$meV. However, as the excitation spectrum of copper benzoate is fully gaped even in an arbitrarily small field, unlike in the pure Heisenberg model, this issue needs also to be reexamined. To do this, we have calculated the spin-spin correlation functions

$`S_q^{\alpha \alpha }={\displaystyle \frac{1}{N}}{\displaystyle \underset{ij}{}}\left(S_i^\alpha S_i^\alpha \right)\left(S_j^\alpha S_j^\alpha \right)e^{iq\left(R_iR_j\right)}.`$
The momentum shift $`\delta q`$ can be determined from the peak position of $`S_q^{\alpha \alpha }`$. From our calculations, we find that $`S_q^{\alpha \alpha }`$ behaves differently along the three principal axes. $`S_q^{bb}`$ shows a weak incommensurate peak. However the peaks of $`S_q^{a^{\prime \prime }a^{\prime \prime }}`$ and $`S_q^{c^{\prime \prime }c^{\prime \prime }}`$ are pinned at $`q=\pi `$. With $`H`$ increasing, the heights of these peaks are suppressed in all three directions.

Figure (4) shows the field dependence of the magnetization $`M(H)`$ and the momentum shift $`\delta q`$ for $`𝐇//b`$. For comparison, the magnetization curve for the pure Heisenberg model and the experimental data for $`\delta q`$ are also shown in the figure. As seen from the figure, our numerical values of $`\delta q`$ agree quantitatively with the experimental data Den2 . However, we find that Eq. (4) is not valid for copper benzoate. In particular, in contrast to $`M(H)`$, $`\delta q`$ varies non-monotonically with $`H`$. We believe this non-monotonic variation of $`\delta q`$ with $`H`$ can be detected by neutron scattering measurements. In addition, the magnetization is gradually saturated for large fields as a direct consequence of the DM interaction. This is different from in the pure Heisenberg model where the spins are fully polarized beyond a critical field $`\mu _BH_c=J`$, at which the two magnetization curves differ mostly.

When $`𝐇//b`$, spins are polarized ferromagnetically along the $`b`$axis and antiferromagnetically along the other two directions. Figure (5) shows the staggered magnetization as a function of $`H`$ for $`𝐃=(0.11,0,0)J`$. At low fields, both $`M_{a^{\prime \prime }}^s`$ and $`M_{c^{\prime \prime }}^s`$ behave as $`H^{1/3}`$. This field dependence of the staggered magnetization above $`2T`$ deviates from the $`H^{1/3}\mathrm{ln}^{1/3}(J/\mu _BH_s)`$ behavior predicted by the effective field theory Osh1  and is not sensitive to the D-vector. It may well be that the range of the validity of the leading approximation in the effective field theory is narrower for the staggered magnetization than that for the gap. We should also mention that the numerical accuracy is lower when $`H`$ is below 0.5T. In intermediate fields, both $`M_{a^{\prime \prime }}^s`$ and $`M_{c^{\prime \prime }}^s`$ vary non-monotonically with $`H`$, in analogy with the field dependence of energy gaps. In the large $`H`$ limit, $`M_s`$ tends to approach zero. This means that the staggered field $`H_s`$ induced by the external field is overwhelmed by the uniform field $`H`$ in the high field limit, although $`H_s`$ is approximately proportional to $`H`$.

The above results show that the DM interaction affects strongly the properties of low-lying excitations although this term is much smaller than the Heisenberg exchange interaction. In particular, the staggered magnetic field induced by this term opens a gap in the spin excitations and leads to an antiferromagnetic long range order to accompany the ferromagnetic long range order induced by the applied field, shown in Fig.6. The coexistence of orthogonal ferromagnetic and antiferromagnetic long range orders in an external field is a characteristic feature of quantum spin systems with DM interactions.

In conclusion, we have shown that the microscopic model (1) including two inequivalent lattice sites and the DM interaction is a very good description of available experimental data. It can reproduce correctly the gap values in all three directions as well as the shift of the incommensurate peaks, without resorting to any additional interaction like interchain coupling. The crossover to strong field behavior and the breakdown of the relation between the momentum shift and the magnetization call for further experimental studies. Finally, we would point out that although the DM interaction is generally small, its effects could be very important for real materials. In particular, for metallic materials, e.g. Yb4As3Kohgi , one could use external fields to modulate the magnetic transport properties which is one of the focal points for the spintronics.

We wish to thank D.C. Dender and C. Broholm for correspondence and I. Affleck, C. F. Chen, F. Essler, H. Nojiri, M. Oshikawa and K. Ueda for fruitful discussions. This work is supported in part by the Special Funds for Major State Basic Research Projects of China and by the National Natural Science Foundation of China.


format: text

text:
# The isomorphism problem for classes of computable fields

## 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 ). There is also a well-developed theory for classes of countable structures, which uses Borel reducibility. This theory was developed by Friedman and Stanley , Becker, Hjorth, Kechris, Louveau, and others .

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 $`\mathrm{}_0`$-categorical, but whose class of models is non-classifiable in the Shelah sense because for any uncountable $`\kappa `$ there are $`2^\kappa `$ non-isomorphic models of size $`\kappa `$. 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.

We work only with structures which have for their universe a subset of $`\omega `$, 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`$ 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^\mathrm{}_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 .

###### Definition 1.2.

The isomorphism problem, denoted $`E(K)`$, is the set

$$\{(a,b)|𝒜_a,𝒜_bK\text{, and }𝒜_a𝒜_b\}$$

If the set of indices for computable members of $`K`$, denoted $`I(K)`$, is hyperarithmetical, then $`E(K)`$ is $`\mathrm{\Sigma }_1^1`$. Intuitively, in the worst case, where $`E(K)`$ is $`\mathrm{\Sigma }_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  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 , Goncharov and Knight , Morozov , and Nies .

###### Theorem 1.3.

If $`K`$ is the set of computable members of any of the following classes, then $`E(K)`$ is $`\mathrm{\Sigma }_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 .

###### 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 $`\mathrm{\Sigma }_1^1`$ complete:

1. Rings
2. Distributive lattices
3. Nilpotent groups
4. 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 .

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  and , shows that the isomorphism problem for the class of computable directed graphs is $`_1^1`$ complete. Friedman and Stanley  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 , Nies , and Rabin and Scott  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=\nu _1=\mathrm{}`$.

Step $`6s`$: We will go a bit farther on connecting the Archimedean point to the vertices. In particular, for the first $`xV_{s1}`$, if any, such that $`1GxD(G)_{6s1}`$ set $`D(G)_{6s}=D(G)_{6s1}\{1Gx\}`$. If there is no such $`x`$, set $`D(G)_{6s}=D(G)_{6s1}`$.

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_sdom(\nu _{s1})`$). 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_{s1}\{y\}`$ and $`\nu _s=\nu _{s1}\{(n_s,y)\}`$. If necessary, act similarly for $`m_s`$. Now since $`T`$ is computable, we can check whether $`n_sTm_s`$. If we find that there is such a connection, and if $`(n_s,m_s)C_{3s1}`$ we find the least $`x_0,\mathrm{},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_{3s1}\{(n_s,m_s)\}`$. Otherwise, set $`D(G)_{6s+1}=D(G)_{6s}`$ and $`C_{3s}=C_{3s1}`$.

Step $`6s+2`$: In the next two steps we will make sure that for any atomic sentence $`\varphi `$, either $`\varphi `$ or $`\neg \varphi `$ 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 $`\neg xGy`$ is in the diagram so far. Now set

$$\psi =\{\begin{array}{cc}xGy\hfill & \text{if }yGxD(G)_{6s+1}\text{ or if }\{x,y\}=\{1,\nu _s(r)\}\text{ for some }r\hfill \\ \neg xGy\hfill & \text{otherwise}\hfill \end{array}$$

and $`D(G)_{6s+2}=D(G)_{6s+1}\{\psi \}`$.

Step $`6s+3`$: If $`n_s=\nu _s(c)`$ and $`m_s=\nu _s(d)`$ and $`c=dD(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_{s1}\{(n_s,m_s)\}`$. Otherwise, set $`D(G)_{6s+3}=D(G)_{6s+2}\{\neg 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 $`qTt`$ 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 $`rTt`$ 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)=\underset{s\omega }{}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_1T_2`$ induces an isomorphism from $`G_1`$ to $`G_2`$, which maps $`\nu (x)\nu (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_1G_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 :

###### 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  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\omega }`$, 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 $`q`$th root where $`q`$ is relatively prime to $`p`$ both in this construction and throughout the following argument. This function $`L:GraphsFields`$ is both a Borel measurable function under the usual product topology , 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 $`ij`$), 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 , and others still by Abhyankar  and Shapiro . 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 $`ij`$.

###### 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}=\underset{k=1}{\overset{n}{}}a_kb_k$$

where $`a_k`$ is algebraic over $`(X_i)`$, and $`b_k`$ is algebraic over $`(X_j)`$. That is, $`\underset{k=1}{\overset{n}{}}a_kb_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)}\times \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)}\{\text{these finitely many “bad points” of }p_i\text{, say }e_t\}$$

and

$$\overline{(X_t)}\{\text{finitely many “bad points” of }p_j\text{, say }f_t\}$$

Thus the expression $`\underset{k=1}{\overset{n}{}}a_kb_k`$ can be continuously defined on the relevant covering space of $`\overline{(X_i)}\{e_t\}\times \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 $`\underset{k=1}{\overset{n}{}}a_kb_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{\underset{k=1}{\overset{n}{}}a_kb_k}{\underset{k=1}{\overset{n}{}}c_kd_k}$$

we could simply write

$$(\sqrt{X_i+X_j})(\underset{k=1}{\overset{n}{}}c_kd_k)=\underset{k=1}{\overset{n}{}}a_kb_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}=\underset{s=1}{\overset{n}{}}\underset{t=1}{\overset{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\gamma }\}`$. Those used in the composition of $`f_{st}`$ may be collected as $`\{d_{st\gamma }\}`$. 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 $`\widehat{x}`$ be a point of $`X_i+X_j=0`$, and let $`N`$ be a ball around it of positive radius. Use $`M_\delta `$ to denote the (finitely many) hyperplanes $`X_q=e_{q\gamma }`$, $`X_t=d_{st\gamma }`$, and $`X_j+X_k=0`$. Now $`M_\delta ^c`$ (the complement of $`M_\delta `$) is open, so $`N(\underset{\delta }{}M_\delta )`$ is a neighborhood containing a point of $`X_i+X_j=0`$ and no point of any $`M_\delta `$. 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{\underset{s=1}{\overset{n}{}}\underset{t=1}{\overset{m_s}{}}a_{st}}{\underset{s=1}{\overset{n}{}}\underset{t=1}{\overset{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_k0`$ but which is the identity on $`\{X_{\mathrm{}}\}_\mathrm{}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}=\underset{s=1}{\overset{n}{}}\underset{t=1}{\overset{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 $`AB`$ if and only if $`\overline{(A)}=\overline{(B)}`$. If $`XX_i`$ and $`YX_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_iX_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}=\underset{s=1}{\overset{n}{}}\underset{t=1}{\overset{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_iL(R)`$ is mapped to some $`Y_iX_jL(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_nX_p`$ and $`Y_MX_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 $`RS`$. ∎

### 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$`)_1E(`$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   .

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\omega }`$, 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 $`\stackrel{~}{M}`$ be the set of all $`(a,s)`$ where $`aF_s^{}F_{s1}^{}`$. It is clear that the reduct of $`\stackrel{~}{M}`$, with the operations $`(a,s)+_M(b,t):=(a+_Gb,r)`$ and $`(a,s)_M(b,t):=(a_Gb,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 , 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 $`\mathrm{\Pi }_3^0`$ complete.

###### Proof.

To see that the problem is $`\mathrm{\Pi }_3^0`$, we first note that $`I(K)`$ is $`\mathrm{\Pi }_2^0`$, since the class can be axiomatized with $`\mathrm{\Pi }_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 $`\mathrm{\Pi }_2^0`$. We will formulate a sentence to say that $`𝒜_a`$ and $`𝒜_b`$ have the same dimension. The statement

$$D_n=(x_1,\mathrm{},x_n)\underset{\overline{a}0}{}(\underset{i=1}{\overset{n}{}}a_ix_i0)$$

(which is $`\mathrm{\Sigma }_2^0`$) states that there are at least $`n`$ linearly independent elements. Now we can write

$$n[𝒜_aD_n𝒜_bD_n]$$

(which is $`\mathrm{\Pi }_3^0`$), and the conjunction of this statement with $`a,bI(K)`$ defines $`E(a,b)`$.

To see that the problem is $`\mathrm{\Pi }_3^0`$ complete, we will take a known $`\mathrm{\Pi }_3^0`$ complete set $`S`$, and construct a uniformly computable sequence of vector spaces $`(V(n))_{n\omega }`$ such that $`V(n)V^{\mathrm{}}`$ if and only if $`nS`$, where $`V^{\mathrm{}}`$ is an infinite dimensional vector space. This will show that if $`e`$ is the index of $`V^{\mathrm{}}`$, $`E(a,e)`$ is $`\mathrm{\Pi }_3^0`$ complete.

Define $`Cof=\{e|W_e`$ is cofinite$`\}`$, where $`W_e`$ is the domain of the $`e`$th 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 $`\mathrm{\Pi }_3^0`$ complete .

We begin by letting $`\{a_i\}_{i\omega }`$ be a basis for a computable copy of $`V^{\mathrm{}}`$, and by considering a set $`\{b_i\}_{i\omega }`$. Let $`\lambda _i`$ enumerate the linear combinations of $`b_i`$. We will construct $`f`$ and $`D(V(n))`$ to meet the following conditions:

| $`P_e^1`$ : | $`\lambda _e=0D(V(n))`$ or $`\neg \lambda _e=0D(V(n))`$ |
| --- | --- |
| $`P_e^2`$ : | $`b_edom(f)`$ |
| $`Q_e`$ : | $`f(b_e)`$ is linearly independent of $`b_0,\mathrm{}b_{e1}`$ if and only |
|  | if $`eW_n`$ |

Thus, $`im(f)`$ will be a subspace of $`V^{\mathrm{}}`$ which we will call $`V(n)`$, and will have the desired properties. We say that $`P_e^1`$ requires attention at stage $`s`$ if $`\lambda _e=0D(V(n))_s`$ and $`\neg \lambda _e=0D(V(n))_s`$ and $`i<\frac{s}{2}`$ wherever $`b_i`$ is included in $`\lambda _e`$. $`Q_e`$ requires attention at stage $`s`$ if $`eW_{n,s}`$ and $`Q_e`$ has not received attention previously. Let $`f_0`$ be the homomorphism induced by taking $`b_ia_i`$, and $`D(V(n))_0=\mathrm{}`$.

At stage $`2s`$, let $`\mathrm{}_s`$ be the first $`e`$ such that $`P_e^1`$ requires attention. We can then find whether $`f_s(\lambda _\mathrm{}_s)=0`$. If so, let $`D(V(n))_{2s+1}=D(V(n))_{2s}\{\lambda _\mathrm{}_s=0\}`$. Otherwise, add $`\neg \lambda _\mathrm{}_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 $`\delta _s(b_1,\mathrm{},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 $`\widehat{a}_{x_s}Cl(a_0,a_1,\mathrm{},a_{x_s1})`$ such that $`V^{\mathrm{}}\delta _s(f_s(b_0),f_s(b_1),\mathrm{},f_s(b_{x_s1}),\widehat{a}_{x_s},f_s(b_{x_s+1}),\mathrm{},f_s(b_N))`$. We then define

$$f_{s+1}(b_i)=\{\begin{array}{cc}\widehat{a}_{x_s}\hfill & \text{if }i=x_s\hfill \\ f_s(b_i)\hfill & \text{otherwise}\hfill \end{array}$$

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 ($`eW_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 $`\mathrm{\Pi }_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,\mathrm{}x_n)(\underset{i=1}{\overset{2^n}{}}(\underset{j=0}{\overset{n}{}}x_j^{p_{ij}})0)$$

where the conjunction is taken over all $`\{p_{ij}\}_{1i2^n,1jn}`$ 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[𝒜_aT_n𝒜_bT_n]$$

in conjunction with $`a,bI(K)`$ for $`E(a,b)`$. Note that $`I(K)`$ is $`\mathrm{\Pi }_2^0`$.

We will build a uniformly computable sequence $`(F(n))_{n\omega }`$ 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\omega }`$ be a transcendence base for a computable copy of $`F^{\mathrm{}}`$ (the algebraically closed field of infinite transcendence degree), and by considering a set $`\{b_i\}_{i\omega }`$. Let $`\lambda _i`$ enumerate the polynomial combinations of $`b_i`$. We will construct $`f`$ and $`D(F(n))`$ to meet the following conditions:

| $`P_e^1`$ : | $`\lambda _e=0D(F(n))`$ or $`\neg \lambda _e=0D(F(n))`$ |
| --- | --- |
| $`P_e^2`$ : | $`b_edom(f)`$ |
| $`Q_e`$ : | $`f(b_e)`$ is algebraically independent of $`b_0,\mathrm{}b_{e1}`$ if and only if we |
|  | have $`eW_n`$ |

Thus, $`im(f)`$ will be a subset of $`F^{\mathrm{}}`$ which we will call $`F(n)`$, and will have the desired properties. We say that $`P_e^1`$ requires attention at stage $`s`$ if $`\lambda _e=0D(F(n))_s`$ and $`\neg \lambda _e=0D(F(n))_s`$ and $`i<\frac{s}{2}`$ wherever $`b_i`$ is included in $`\lambda _e`$. $`Q_e`$ requires attention at stage $`s`$ if $`eW_{n,s}`$ and $`Q_e`$ has not received attention previously. Let $`f_0`$ be the homomorphism induced by taking $`b_ia_i`$, and $`D(F(n))_0=\mathrm{}`$.

At stage $`2s`$, let $`\mathrm{}_s`$ be the first $`e`$ such that $`P_e^1`$ requires attention. We can then find whether $`f_s(\lambda _\mathrm{}_s)=0`$. If so, let $`D(F(n))_{2s+1}=D(F(n))_{2s}\{\lambda _\mathrm{}_s=0\}`$. Otherwise, add $`\neg \lambda _\mathrm{}_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 $`\delta _s(\overline{b})`$ be the (finite) conjunction of all sentences in $`D(F(n))_{2s+1}`$. Again using strong minimality, there is some $`\widehat{a}_{x_s}`$ in the closure of the set of $`a_i`$ for $`i<X_s`$ such that

$$F^{\mathrm{}}\delta _s(f_s(b_0),f_s(b_1),\mathrm{},f_s(b_{x_s1}),\widehat{a}_{x_s},f_s(b_{x_s+1}),\mathrm{},f_s(b_N))$$

We then define

$$f_{s+1}(b_i)=\{\begin{array}{cc}\widehat{a}_{x_s}\hfill & \text{if }i=x_s\hfill \\ f_s(b_i)\hfill & \text{otherwise}\hfill \end{array}$$

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 ($`eW_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 $`\mathrm{\Pi }_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 $`\mathrm{\Pi }_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\widehat{x},\widehat{z}\underset{q}{}[(𝒜_aqx𝒜_bq\widehat{x})]$$

$$\underset{q}{}[(𝒜_bqz𝒜_aq\widehat{z})]$$

defines the relation $`𝒜_a𝒜_b`$, showing that it is, at worst, $`\mathrm{\Pi }_3^0`$.

###### Lemma 5.2.

There exists a uniformly computable sequence $`\{a_i\}_{i\omega }`$ of real numbers which are algebraically independent.

###### Proof.

Lindemann’s theorem, a known result, states (in one form) that if $`\lambda _1,\lambda _2,\mathrm{},\lambda _k`$ are algebraic numbers linearly independent over the rationals, then $`e^{\lambda _1},\mathrm{},e^{\lambda _k}`$ are algebraically independent . Further, it is well known that the set $`\{\sqrt{2},\sqrt{3},\sqrt{5},\mathrm{}\}`$ is linearly independent (a proof may be found in ). ∎

Now consider the language $`(+,,0,1,\{a_i\}_{i\omega })`$, 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,+,,0,1,,\{a_i\}_{i\omega })`$ where $`M`$ is the real closure of $`\{a_i\}_{i\omega }`$.

We are now ready to prove the completeness part of the theorem. We will start with a set $`\{b_{ij}\}_{i,j\omega }`$, $`D_1=\mathrm{}`$, a list $`\lambda _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|ijzR(i,j,z,n)\}`$ be an arbitrary $`\mathrm{\Pi }_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)`$ exactly when $`nS`$. Set $`m_{t,s}=0`$ and $`I_{s,1}=D_1=\mathrm{}`$ for all $`(t,s)`$. We wish to meet the following requirements:

| $`P_e^1`$ : | $`\lambda _e=0D`$ or $`\neg \lambda _e=0D`$ |
| --- | --- |
| $`P_e^2`$ : | $`b_{i,j}dom(f)`$ |
| $`Q_e`$ : | For each $`i`$, if $`nS`$ 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 $`\lambda _iD_{s1}`$ and $`\neg \lambda _iD_{s1}`$. Without loss of generality say that $`\lambda _i`$ is of the form $`p(b_{j_0},\mathrm{},b_{j_n})Q0`$ where $`Q`$ is $`=`$ or $``$. Now if $`p(f_{s1}(b_{j_0}),\mathrm{},f_{s1}(b_{j_n}))Q0`$ then set $`D_s=D_{s1}\{\lambda _i\}`$. Otherwise, $`D_s=D_{s1}\{\neg \lambda _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,(t1)}`$ and $`m_{t,(s+1)}=m_{t,s}`$. Otherwise set $`m_{t,(s+1)}=\mathrm{min}\{k>m_{t,s}|b_{tk}_{q<s}I_q`$ and $`b_{tk}=b_{tm_{t,s}}D_s\}`$. Now let $`\delta _s(\stackrel{}{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 $``$ 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,(t1)}\{(t,m_{t,s},r_{t,m_{t,s}}\}\{(t,k,r_{t,m_{t,s}})|D_sb_{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{array}{cc}\widehat{r}\hfill & \text{if }(i,j,\widehat{r})I_s\hfill \\ f_{s1}(b_{ij})\hfill & \text{otherwise}\hfill \end{array}$$

Let $`D(F(n))=_{s\omega }D_s`$, and we will call the structure whose diagram this is $`F(n)`$. Now if $`nS`$, 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)`$. 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 $`\mathrm{\Sigma }_1^1`$ complete.

###### Proof.

We will say that $`ab`$ exactly when $`a^nb`$ for some $`n\omega `$. We say that $`ab`$ ($`a`$ is comparable to $`b`$) if $`ab`$ and $`ba`$. 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)^{}=(\overline{R},+,,0,1,,\{X_i\}_{i\omega })`$, an expansion of a real closed field, in which $`X_iX_j`$ if and only if $`i_Lj`$, 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<_Li\}`$, 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 $`\stackrel{~}{R}G`$ containing exactly the elements algebraic over $`\{X_i\}_{i\omega }`$. From an index for $`L`$, we can effectively find an index $`e(L)`$ for the function enumerating $`\stackrel{~}{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,bR(L_1)`$, $`ab`$ 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 $`\stackrel{~}{h}`$, where if $`h`$ maps the class of $`X_i`$ to that of $`X_j`$, then $`\stackrel{~}{h}:ij`$. 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=\underset{q}{}a_qX^q`$, where $`a_qK`$ and $`a_q=0`$ except for $`q`$ in some well-ordered set. There is an isomorphism $`rcl(K(x))K((X^{}))`$ mapping $`xX^1`$. Now suppose that $`yK((X^{}))`$, and $`y=\underset{q}{}b_qX^q`$. Further, suppose that for all $`xK`$, we have $`y>x`$ (that is, $`y`$ is an infinite element over $`K`$). Let $`\widehat{q}`$ be the least such that $`b_{\widehat{q}}0`$. I claim that $`\widehat{q}<0`$. If $`\widehat{q}0`$, then $`yb_0+1`$, but $`b_0+1K`$, giving a contradiction. So $`\widehat{q}<0`$. Now $`X^{\widehat{q}1}>y`$; that is, $`(X^1)^{1\widehat{q}}>y`$, so $`yt^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)=\underset{I}{}rcl(R(\{X_i\}_{iI}))`$ where $`I`$ is a finite subset of $`\omega `$. 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.