Comparing classes of finite structures

W. Calvert, D. Cummins, J. F. Knight, and S. Miller

February 4, 2004

1 Introduction

In many branches of mathematics, there is work classifying a collection of objects, up to isomorphism or other important equivalence, in terms of nice invariants. In descriptive set theory, there is a body of work using a notion of “Borel embedding” to compare the classification problems for various classes of structures (fields, graphs, groups, etc.) [8], [3], [12], [13], [14]. In this work, each class consists of structures with the same countable universe, say ω, and with the same language, usually finite. For a given finite language L, the class of all L-structures with universe ω has a natural topological structure, and the other classes of L-structures being considered are normally Borel subclasses of these.

A Borel embedding of one class K into another class K′ is a Borel function from K to K′ that is well defined and 1−1 on isomorphism types. The notation K ≤_{B} K′ indicates that there is such an embedding. If K ≤_{B} K′, then the classification problem for K reduces to that for K′. If K′ has nice invariants, then we may describe A ∈ K, up to isomorphism, by determining the corresponding B ∈ K′ and giving its invariants. If there is no nice classification for K, then the same must be true for K′.

Example: Friedman and Stanley [8] described an embedding of the class of undirected graphs in the class of fields of characteristic 0. The edge relation on an undirected graph is assumed to be irreflexive. For an undirected graph G, the corresponding field is obtained by first taking an algebraically closed field of characteristic 0, with a transcendence base G, identified with the set of graph elements, and then restricting to the subfield that is generated by the algebraic closures of the single elements b ∈ G, and the elements \sqrt{b_{1} + b_{2}}, where b_{1}, b_{2} are joined by an edge in G.

In the present paper, our goal is to compare classes of structures using a notion of computable embedding. Like the relation ≤_{B}, our relation ≤_{c} is a partial order on classes of structures. We focus mainly, but not exclusively, on classes of finite structures. We have some “landmark” classes—finite prime fields, finite linear orders, finite dimensional vector spaces over the rationals, and arbitrary linear orders—forming a strictly increasing sequence. If we restrict our attention to classes of finite structures, then the class of finite linear orders lies on top, along with the class of finite cyclic groups and the class of finite undirected graphs. There are many incomparable classes below the class of finite prime fields, and between that and the class of finite linear orders. If we allow classes that contain infinite structures, then the class of undirected graphs lies on top. The Friedman-Stanley embedding can be turned into a computable embedding, showing that the class of fields of characteristic 0 is also on top. There are many incomparable classes between the class of finite linear orders and the class of finite dimensional vector spaces, and between this class and the class of all linear orders.

In the remainder of the present section, we give some conventions and definitions. In Section 2, we discuss various natural examples of classes. We show that any class of finite structures can be computably embedded in the class of finite undirected graphs, and this can be computably embedded in the class of finite linear orders. In Section 3, we characterize the classes that can be computably embedded in the finite prime fields, and those that can be computably embedded in the finite linear orders. In Section 4, we show that the class of finite dimensional vector spaces over the rationals lies strictly above the class of finite linear orders. Using notions related to immunity, we construct families of 2^{ℵ_{0}} incomparable classes in various intervals. We also produce infinite increasing chains of classes. Finally, in Section 5, we state some open problems.

1.1 Conventions

We begin with some conventions. The structures that we consider all have a finite relational language, and all have universe a subset of ω. The classes that we consider all consist of structures for a single language. Moreover, all classes are closed under isomorphism, modulo the restriction that each structure has universe a subset of ω. We will sometimes identify a structure A with its atomic diagram D(A). We will also identify finite sequences, sentences, etc., with their Gödel numbers. Thus, we may say that a structure is computable, meaning that the set of codes for sentences in D(A) is computable. All finite structures are computable, but the infinite structures that we consider may or may not be computable.

1.2 Basic definitions

There are several possible notions of computable transformation from one class of structures to another. The one that we have chosen is essentially uniform enumeration reducibility. Recall that for A, B ⊆ ω, B is enumeration reducible to A if there is a computably enumerable (c.e.) set Φ of pairs (α, b), where α is a finite subset of ω and b ∈ ω, such that

B = {b|(∃α ⊆ A) (α, b) ∈ Φ} .

For a given Φ and A, the set B is unique, and we may denote it by Φ(A). (For more on enumeration reducibility, see Rogers [20].)

Here is the definition of computable transformation that we shall use.

Definition 1. Let K and K′ be classes of structures, and let Φ be a c.e. set of pairs (α, φ), where α is a subset of the atomic diagram of a finite structure for the language of K, and φ is an atomic sentence, or the negation of one, in the language of K′. We say that Φ is a computable transformation from K to K′ if for all A ∈ K, Φ(D(A)) has the form D(B), for some B ∈ K′. We may write Φ(A) = B (identifying the structures with their atomic diagrams).

Note that in this definition, the output D(B) depends only on the input D(A), not on the order in which it is examined.

Proposition 1.1. Let K, K′ be classes of structures, and let Φ be a computable transformation from K to K′. If A, A′ ∈ K, where A ⊆ A′, then Φ(A) ⊆ Φ(A′).

Proof. Let B = Φ(A), and let B′ = Φ(A′). If φ ∈ D(B), then there is a finite set α ⊆ D(A) such that (α, φ) ∈ Φ. Then since α ⊆ D(A′), we have φ ∈ D(B′).

It follows from Proposition 1.1 that if K contains an infinite strictly increasing chain of structures (increasing under the substructure relation), then so does K′. More generally, we have the following.

Corollary 1.2. Let K, K′ be classes of structures such that there is a computable transformation from K to K′. If K contains a strictly increasing chain of structures having order type ρ, then so does K′.

We are interested in computable transformations that respect isomorphism, mapping K/≅ into K′/≅ in a 1 − 1 way.

Definition 2. Let K, K′ be classes of structures.

1. A computable embedding of K in K′ is a computable transformation Φ from K to K′ such that for all A, A′ ∈ K, A ≅ A′ iff Φ(A) ≅ Φ(A′).

2. If there is a computable embedding of K in K′, then we write K ≤_{c} K′.

The following proposition is obvious, but useful.

Proposition 1.3. Let K_{1}, K_{2}, K′_{1}, K′_{2} be classes of structures, with K′_{1} ⊆ K_{1} and K′_{2} ⊇ K_{2}. If K_{1} ≤_{c} K_{2}, via Φ, then K′_{1} ≤_{c} K′_{2}, via the same Φ.

To illustrate what a computable embedding actually looks like, we return to the motivating example.

Proposition 1.4 (Friedman and Stanley). If K is the class of undirected graphs, and K′ is the class of fields of characteristic 0, then K ≤_{c} K′.

Sketch of proof. We describe the computable embedding Φ. First, let F be a computable algebraically closed field of characteristic 0, with a computable sequence (b_{k})_{k∈ω} of elements that are algebraically independent. For an undirected graph G (with universe a subset of ω), let F(G) be the subfield of F generated by the elements that are either in the algebraic closure of b_{k}, for some graph element k, or else have the form \sqrt{b_{i} + b_{j}}, where i, j are distinct graph elements joined by an edge. Now, let Φ consist of the pairs (α, φ), where α is the atomic diagram of some finite undirected graph G and φ is a sentence in the atomic diagram of F(G). Clearly, Φ is c.e. For any A ∈ K, Φ(A) = F(A). Therefore, Φ is a computable transformation from K to K′. The fact that Φ is 1−1 on isomorphism types takes some effort. (It must be shown that for i, j ∈ G, if i, j are not joined by an edge, then \sqrt{b_{i} + b_{j}} is not present in F(G).)

Notation: We write C for the set of all classes of structures satisfying our conventions, and FC for the restriction to classes of finite structures. The relation ≤_{c} is a partial order on C (i.e., the relation is transitive and reflexive on the set). As always, we get an equivalence relation ≡_{c}, where K ≡_{c} K′ iff both K ≤_{c} K′ and K′ ≤_{c} K. The equivalence classes under ≡_{c} are called c-degrees. The relation ≤_{c} on C induces a partial order on c-degrees, which we denote also by ≤_{c}. We write C for the degree structure (C/_{≡_{c}}, ≤_{c}), and we write FC for the restriction of C to the c-degrees that contain elements of FC.

1.3 Alternative definitions

Effective transformations between classes of structures, of one kind or another, occur in many places in the literature. We mention only a sample. First, there are notions that involve interpretation, in which the universe and basic relations of a structure A ∈ K are defined, in a uniform way, in the corresponding structure B ∈ K′. This approach has been used to show that certain theories are undecidable—see, for example, the unpublished typescript of Rabin and Scott [19], or the more recent paper of Nies [18]. Sometimes, it is necessary to have the interpretation go both ways. This happens, for example, in the paper of Hirschfeldt, Khoussainov, Shore, and Slinko [11], with results on “computable dimension” (the number of isomorphic members not isomorphic by a computable function) and “degree spectra” (the set of possible degrees of a relation in isomorphic copies of a computable structure). Some of our computable embeddings involve interpretations, but others do not.

Another kind of effective transformation, which is used in connection with computable structures, is a partial computable function taking indices for computable members of one class K to indices for computable members of another class K′. This approach occurs, for example, in the usual proof that the set of computable indices for computable well orderings is Π_{1}^{1} complete (see Rogers [20]). More recently, the approach is used in [4], [5], in results on the complexity of the isomorphism relation. We deal directly with structures, not with indices, and the infinite structures that we consider are not necessarily computable.

We state two alternative notions of computable transformation that we tried working with, and then discarded in favor of the one in Definition 1. In the definition below, enumeration reducibility is replaced by Turing reducibility.

Definition 1′: Let K, K′ be classes of structures. Then Φ = φ_{e} (the computable operator given by oracle machine e) is a computable transformation of K into K′ if for all A ∈ K, φ_{e}^{D(A)} is the characteristic function of D(B), for some B ∈ K′.

Definition 1′ would be equivalent to Definition 1 if our structures all had universe ω. However, for most structures, there will be numbers not in the universe. Definition 1′ would have us use information about these numbers, which strikes us as not “structural”.

The other alternative definition has the feature that for a given input structure A, the output structure B depends not just on D(A), but on the order in which we look at the information.

Definition 1′′: Let K, K′ be classes of structures. An effective transformation of K into K′ is a partial computable function f such that for all A ∈ K, and all chains (α_{s})_{s∈ω} of finite sets such that D(A) = ∪_{s}α_{s}, there is a structure B ∈ K′ such that D(B) is the union of a corresponding chain (β_{s})_{s∈ω} of finite sets, where β_{0} = ∅, and for all s, β_{s+1} = f(β_{s}, α_{s}).

From Definition 1′, and also from Definition 1′′, we obtain obvious alternative versions of Definition 2, and we get further partial orders on C and FC. Using Definition 1′′, we would produce transformations that respect isomorphism by guessing at the “global” structure. Definition 1′′ may be interesting from the point of view of computability theory, especially for classes of infinite structures. There is a great deal of guessing at global structure in known arguments showing that the set of indices of computable copies of various structures is Σ_{1}^{1} complete or Π_{α}^{0}-complete (see [4], [5]). We chose Definition 1 as representing a more direct computable transformation of one structure into another, based on “local” structure. Proposition 1.1 seems intuitively right to us, and it fails for the alternative definitions.

1.4 Related reducibilities

There is quite a lot of work on the Medvedev lattice and Medvedev degrees (see [17], [23], [21]). The setting resembles ours in some ways. In both cases, the basic objects are classes, and the reducibility takes members of one class to members of another in a uniform effective way. Our reducibility relation is uniform enumeration reducibility, while Medvedev reducibility is uniform Turing reducibility. Dyment developed a variant of the Medvedev lattice based on enumeration reducibility (see [23],[7]). In the Medvedev lattice, the points are classes of functions, while we consider classes of structures, closed under isomorphism. Moreover, our computable reductions are supposed to be well defined and 1 − 1 on isomorphism types. This makes our setting quite different. It will be shown in [15] that C is not a lattice.

2 Examples

Having defined the notion of a computable embedding from one class of structures into another, we will now investigate some natural examples of classes of structures. If we restrict our attention to classes of finite structures, we find that there are two c-degrees into which almost all natural examples of classes of finite structures fall. The first of these contains the class of finite prime fields (which we call P F), along with the class of finite cyclic graphs. The second contains the class of finite linear orders (which we call F LO), along with the class of all finite undirected graphs, the class of all finite fields, the class of finite cyclic groups, and the class of finite simple groups. We prove that these these are in fact different c-degrees:

Proposition 2.1. P F ⪇_{c} F LO (i.e., P F ≤_{c} F LO and F LO ≰_{c} P F).

Proof. To show P F ≤_{c} F LO, we construct a computable embedding Φ. For each n, let L_{n}, be the the usual linear order on the first n elements of the natural numbers. Let Φ be the set of pairs (α, φ) such that, for some n, α is the atomic diagram of a field of size p_{n} (where p_{n} is the nth prime), and φ ∈ D(L_{n}). This set of pairs is clearly c.e. Note that, for all A, A′ ∈ P F, we have A ≅ A′ iff Φ(A) ≅ Φ(A′). Therefore, P F is computably embedded in F LO.

To show that F LO ≰_{c} P F, assume for a contradiction that F LO ≤_{c} P F. Say Φ is a computable embedding. Let A, A′ be two nonisomorphic members of F LO. Suppose A has fewer elements than A′. Then A is clearly isomorphic to a substructure of A′. We may suppose that A ⊆ A′. By Proposition 1.1, Φ(A) ⊆ Φ(A′). We also know from Definition 2 that Φ(A) ≇ Φ(A′). Since no prime field is a substructure of another, nonisomorphic prime field, we conclude that F LO ≰_{c} P F.

We note that in the proof of Proposition 2.1 above, showing F LO ≰_{c} P F only used the fact that F LO contains two nonisomorphic finite linear orders. The same proof yields the following.

Corollary 2.2. If K is a class containing two nonisomorphic finite linear orders, then K ≰_{c} P F.

We have seen that there are at least two distinct c-degrees in FC. Most natural examples of classes of finite structures fit into one of these two c-degrees, but before we discuss some of these examples, it will be convienent to prove that, for classes of finite structures, the c-degree of F LO is the maximum element of FC. We first prove the following lemma.

Lemma 2.3. For any class of structures K in a finite relational language, K ≤_{c} UG, where UG is the class of undirected graphs. Moreover, if K consists of finite structures, then K ≤_{c} F UG, where F UG is the class of finite undirected graphs.

Proof. For each finite relational language L, we describe a computable embedding Φ of the class of all L-structures into UG. Thus, for an arbitrary class of

[figure: g(1); g(2); g(3)]

Figure 1: Representing the elements 1, 2, 3

[figure: g; g(1); g(2); g(3)]

Figure 2: Representing R(1, 2, 3), where R corresponds to 5

L-structures whose universes are subsets of the natural numbers, Φ embeds the given class in UG. The embedding Φ will have the feature that if A is a finite L-structure, then Φ(A) is also finite.

We begin by describing a large undirected graph G, with finite subgraphs that represent possible elements of L-structures, and further finite subgraphs that represent sentences R(a_{1}, …, a_{r}) which may occur in the atomic diagrams of L-structures. The graph G will be computable.

Subgraphs representing possible elements

For each a ∈ ω, we put into G a 3-cycle T_{a}. We arrange that the cycles T_{a} are all disjoint, and we can pass effectively from a to T_{a}. Let g(a) be the least element of T_{a}. (Figure 1 shows T_{1}, T_{2}, and T_{3}.)

Subgraphs representing possible atomic sentences

We assign to the relation symbols of L distinct numbers greater than 3. Suppose R is assigned the number k. Then for each atomic sentence of the form ρ = R(a_{1}, …, a_{r}), we put into G a subgraph G_{ρ} consisting of a k-cycle together with some connecting chains. Say g is the least element of the k-cycle. We connect g to g(a_{1}) by a chain of length 1, adding just an edge. We connect g to g(a_{2}) by a chain of length 2, adding an intermediate point, and, in general, we connect g to a_{i} by a chain of length i, adding i − 1 intermediate points.

All of the points that we have described as making up the subgraph G_{ρ} are distinct, and for distinct ρ, the subgraphs G_{ρ} are disjoint, except possibly for the elements g(a) (in the 3-cycles. We arrange the construction so that we can pass effectively from an atomic sentence ρ to the subgraph G_{ρ}. (Figure 2 gives a sample G_{ρ}.)

The graph G is generated by the two families of subgraphs described above. For each L-structure A, there is a corresponding graph G(A) ⊆ G, generated by the subgraphs T_{a}, where a ∈ A, and G_{ρ}, where ρ is a sentence in D(A) of the form R(a_{1}, …, a_{n}). We note that if A is finite, then G(A) is also finite. Now, we are ready to define the computable embedding Φ. This consists of the pairs (α, φ) such that for some finite L-structure A, α = D(A) and φ ∈ D(G(A)).

The set Φ is c.e. For any L-structure A, Φ(A) = G(A). It should be clear that if A ≅ A′,then Φ(A) ≅ Φ(A′). Conversely, ifΦ(A) ≅ Φ(A′), then the 3cycles in Φ(A) must correspond to the 3-cycles in Φ(A′). So, the isomorphism from Φ(A) onto Φ(A′) induces a 1−1 function from A onto A′. Moreover, if for some atomic sentence ρ = R(a_{1}, …, a_{r}), the 3-cycles in Φ(A) corresponding to a_{1}, …, a_{r} are attached to the subgraph G_{ρ}, indicating that A ⊧ R(a_{1}, …, a_{r}), then the corresponding 3-cycles in Φ(A′) are attached to a copy of G_{ρ}, indicating that A′ ⊧ R(f(a_{1}), …, f(a_{r})). It follows that A ≅ A′. Therefore, Φ is a computable embedding of the class of all L-structures into UG.

Definition 3.

1. A computable enumeration of a class K is a c.e. set E of pairs (n, φ) where n ∈ ω and φ is an atomic sentence or the negation of one, and

(a) for each n, {φ|(n, φ) ∈ E} = D(A_{n}), for some A_{n} ∈ K,

(b) for each A ∈ K, there is some n such that A_{n} ≅ A.

We may write (A_{n})_{n∈ω} instead of E for the enumeration, indicating that it really is a list.

2. An enumeration (A_{n})_{n∈ω} of a class K is Friedberg if each isomorphism type in K is represented just once on the list.

The following lemma says that F UG has a computable Friedberg enumeration of a special kind.

Lemma 2.4. There is a computable Friedberg enumeration (G_{n})_{n∈ω} of F UG with the feature that if G ≅ G_{m} and G′ ≅ G_{n}, where G′ is a proper extension of G, then m < n.

Proof. To prove the lemma, we first define a partial order on the class of finite undirected graphs as follows. One graph is greater than another if it has more vertices than the other. If two graphs have the same number of vertices, but one has more edges than the other, the one with more edges is greater. Two graphs are said to be equivalent if they agree in number of vertices and in number of edges—equivalent graphs need not be isomorphic. Since, for a given set number of vertices and set number of edges, there will only be a finite number of different ways to arrange the edges, it is obvious that any equivalence class on this partial order will only have a finite number of members. Also, since the number of edges a graph may contain is bounded by the number of pairs of vertices the graph contains, for graphs of a given number of vertices, there will only be a finite number of equivalence classes.

To build the Friedberg enumeration, we run through the equivalence classes, in increasing order, and within a given equivalence class, we choose a single representative of each isomorphism type to put into our list. Since, for each equivalence class, we have only a finite number of possible edge arrangements, we can do this effectively. Since every finite undirected graph falls into one of the equivalence classes, our enumeration will include every isomprphism type of finite undirected graphs. It is a Friedberg enumeration since if two members of F UG are isomorphic, they will be in the same equivalence class, and for each equivalence class we included just one representative of each isomorphism type.

Using Lemma 2.4, we can prove the following.

Theorem 2.5. F UG ≡_{c} F LO

Proof. We must define a computable embedding Φ of F UG into F LO. Take the computable Friedberg enumeration (G_{n})_{n∈ω} of F UG with the special feature in Lemma 2.4. For each n, let L_{n} be the usual linear ordering of {0, 1, 2...n − 1}. Let Φ be the set of pairs (α, φ) such that for some n, α is the atomic diagram of a copy of G_{n} and φ ∈ D(L_{n}). This set of pairs is clearly c.e. For each G ∈ F UG, there is a unique n such that G ≅ G_{n}. Then we have Φ(G) = L_{n}—here we are using the special feature of our Friedberg enumeration, which guarantees that if G′ ⊆ G, where G′ ≅ G_{m}, then m ≤ n. It follows that Φ is well defined and 1 − 1 on isomorphism types. We have shown that F UG ≤_{c} F LO. We get the fact that F LO ≤_{c} F UG directly from Lemma 2.3.

Having shown that the c-degree of F LO is at the top of FC, we go on to show that there are further c-degrees (containing classes of infinite structures) that lie above that of F LO.

Theorem 2.6. The class F V S of finite dimensional vector spaces over the rationals lies strictly above F LO; that is, F LO ⪇ F V S.

Proof. Before proving the result, we should specify the language we are using for vector spaces. It is L = {V, F, 0_{F} , 1_{F} , +_{F} , ∗_{F} , 0_{V}, +_{V}, ∗_{V}}, where 0_{F}, 1_{F}, +_{F}, ∗_{F} are zero, one, addition and multiplication in the rationals, and 0_{V}, +_{V}, and ∗_{V} are the zero vector, vector addition, and multiplication of a scalar by a vector, respectively. Inlcuding the field symbols in our language allows us to avoid including a separate symbol for multiplication by each scalar (a common approach). Thus, our language is finite. We make it relational by thinking of the binary operations and constants as relations.

To prove that F LO ≤_{c} F DS, let V be a computable vector space over the rationals, with a computable sequence of basis elements b_{1}, b_{2}, . . .. For each n, let V_{n} be the subspace of V with basis {b_{1}, …, b_{n}}. Let Φ be the set of pairs, (α, φ) such that for some n, α is the atomic diagram of a linear ordering of size n and φ ∈ D(V_{n}). The set Φ is clearly c.e. Note that, for all A, A′ ∈ F LO, A ≅ A′ iff Φ(A) ≅ Φ(A′). Only the number of elements in A was considered in the construction of Φ, so Φ will map every member of a given isomorphism type of F LO to the same member of F DS.

To prove that F DS ≰_{c} F LO, we first observe that for any finite set of atomic sentences α in the language of rational vector spaces, plus natural numbers, α is a subset of the atomic diagram of a vector space of any given finite dimension. If α describes n independent vectors in a vector space V, it is obvious that α is a subset of atomic diagrams of vector spaces of dimension greater than n, but it is also true that α is a subset of the atomic diagrams of vector spaces of dimension less than n. This is because, since α is finite, the sentences it contains can only describe a finite number of linear combinations of the n vectors, saying that these are not 0. We may extend α to β, with a sentence saying that some further linear combination of two of the vectors is 0, so that β is a subset of the diagram of a vector space V′ of dimension n − 1.

To show that F DS ≰_{c} F LO, assume towards a contradiction that there exists a Φ witnessing F DS ≤_{c} F LO. Let V be a two-dimensional member of F DS, and say that Φ(V) = L, where L is an ordering of type n. There is a finite set of pairs (α_{1}, φ_{1}), …, (α_{r}, φ_{r}) in Φ such that D(L) = {φ_{1}, …, φ_{r}}. Then α = ∪_{1≤i≤r}α_{i} is a finite subset of D(V). We saw above that the set α is also a subset of the atomic diagram of a rational vector space V′ of dimension one. Since α ⊆ D(V′), Φ(V′) must be a linear order, say L′, such that D(L) ⊆ D(L′). Therefore, either L′ ≅ L, or L ⊂ L′. If L′ ≅ L, then Φ is not one to one on isomorphism types. If L ⊂ L′, then Proposition 1.1 would fail for Φ. Either way, we have our contradiction.

Note that in the proof that F DS ≰_{c} F LO, where we used dimensions one and two, we could have substituted any two different dimensions.

Corollary 2.7. If K is a class containing vector spaces of two different dimensions, then K ≰_{c} F LO.

3 General Characteristics

The natural examples of classes described in Section 2 give rise to broader questions regarding our ability to determine what key characteristics of those classes are essential for their placement in our structure. Our goal was to give general results that determine where an arbitrary class lies in relation to the landmark examples, and then manipulate those results in order to construct more examples to fill in our partial order. For simplicity, we now will refer to the c-degree containing finite prime fields as T ype I and the c-degree containing finite linear orders and finite undirected graphs as T ype II. Most generally, we know that all classes of finite structures will embed into a class of T ype II, from Lemma 2.3. We would like to know what is required for an arbitrary class (of possibly infinite structures) to embed in a class of T ype II. We would also like to know which classes lie above and below those of T ype I.

3.1 Results relating to T ype I

Our examples in Section 2 suggested the abstract conditions on a class of structures K that are required for T ype I ≤_{c} K. The conditions involve computable Friedberg enumerations (defined in Section 2). It is well-known that there are classes with a computable enumeration but no computable Friedberg enumeration, although we have not been able to determine who first showed this. There are familiar examples, such as the class of computable linear orderings. Below, we construct a simple example, consisting of finite structures.

Proposition 3.1. There is a class of finite structures K that has a computable enumeration but no computable Friedberg enumeration.

Proof. We want to create a class K with a computable enumeration E. For each n, the set {φ|(n, φ) ∈ E} should be the diagram of some A_{n} ∈ K, and each element of K should be isomorphic to A_{n}, for some n. For each e, we have a requirement R_{e} stating that W_{e} is not a computable Friedberg enumeration of K; either W_{e} fails to be an enumeration of K, or else it repeats isomorphism types.

At each stage s, we have enumerated a finite subset of E, attempting to take care of the first s requirements. Our strategy for R_{e} is as follows: Let C be an e-cycle, and let C^{−} be the result of adding to C an extra “tail”—that is, an extra vertex connected to exactly one vertex of the cycle. We initiate the requirement by putting into E pairs (2e, φ) for all φ ∈ D(C) and (2e+1, φ) for all φ ∈ D(C^{−}). Suppose at some later stage t, we see, for some B ≅ C and B^{−} ≅ C^{−}, and for some m, n,

{(m, φ)|φ ∈ D(B)} ∪ {(n, φ)|φ ∈ D(B^{−})} ⊆ W_{e,t} .

Then we put into E any missing pairs (2e, φ) for φ ∈ D(C^{−}). Thus, either C and C^{−} both appear in our enumeration, while W_{e} fails to enumerate both, or else C^{−} appears twice in our enumeration, and if W_{e} is Friedberg, then it includes some extension of C not on our list. Note that at each stage s we initiate Requirement R_{s}, and we also look at W_{e,s} to see if any requirements R_{e}, for e < s, require our adjustment. This procedure clearly yields a class K with a computable enumeration E but with no computable Friedberg enumeration.

Now we have the following requirement for T ype I ≤_{c} K.

Theorem 3.2. For any class K, T ype I ≤_{c} K iff there is an infinite computable Friedberg enumeration (A_{n})_{n∈ω} of a subclass of K.

Proof. First, suppose T ype I ≤_{c} K, witnessed by the compuable embedding Φ of finite prime fields to elements of K. For each n ∈ ω, we effectively produce a prime field of size p_{n} (where p_{n} is the n^{th} prime), and we let A_{n} be the output of Φ on this field. Then (A_{n})_{n∈ω} is an infinite computable Friedberg enumeration of a subclass of K.

Now, suppose that(A_{n})_{n∈ω} is an infinite computable Friedberg enumeration of a subclass of K. Then T ype I ≤_{c} K, witnessed by the computable embedding Φ that takes the prime field of size p_{n} to A_{n}. Clearly, Φ is well-defined and oneto-one on isomorphism types because the enumeration of the subclass of K was Friedberg.

Now, we know what is required for a class K to have a class of T ype I embed in it, but we would like to know what is required for K to embed into a class of T ype I. Our observation of the structure of the representatives of the T ype I classes motivated the following definition.

Definition 4. We say that K has the substructure property if no A_{1} ∈ K is isomorphic to a substructure of A_{2} ∈ K unless A_{1} ≅ A_{2}.

Proposition 3.3. If K is a class of structures and K ≤_{c} T ype I, then K has the substructure property.

Proof. Say Φ witnesses the embedding, and suppose that we have A_{1} ⊆ A_{2}, both in K, with Φ(A_{1}) = B_{1} and Φ(A_{2}) = B_{2}. By Proposition 1.1, B_{1} ⊆ B_{2}. Since A_{1} ≇ A_{2}, we have B_{1} ≇ B_{2}.

The converse of Proposition 3.3 does not hold. More is needed for K to embed into T ype I than just having the substructure property. The difficulty encountered in trying to embed a class of structures into T ype I, even with the substructure property, was that nonisomorphic structures may still have a common substructure. In understanding the classes of T ype I, the following definition is helpful.

Definition 5. For A a structure in the language of K, B ∈ K, A is a characteristic substructure of B for K if and only if A is a substructure of B and for any C ∈ K with A isomorphic to a substructure of C, we have B ≅ C. When this holds, we write A ⊑ B.

The idea is that when we have seen a characteristic substructure, no further information is needed. With this definition, we develop the following result.

Theorem 3.4. Let K be a class of structures. Then the following are equivalent:

1. K ≤_{c} T ype I.

2. There is a computably enumerable set S of pairs (A, n), where A is a finite structure in the language of K, n ∈ ω, and the following conditions hold.

(a) For all B ∈ K there is a pair (A, n) ∈ S such that A ⊆ B.

(b) If (A, n), (A′, n′) ∈ S and B, B′ ∈ K, with A ⊆ B and A′ ⊆ B′, then n = n′ if and only if B ≅ B′.

3. There is a c.e. set S^{∗} of pairs (φ, n), where φ is an existential sentence in the language of K, n ∈ ω, and

(a) for each B ∈ K there exists (φ, n) ∈ S^{∗} such that B ⊧ φ,

(b) if (φ, n), (φ′, n′) ∈ S^{∗} and B, B′ ∈ K, with B ⊧ φ and B′ ⊧ φ′, then n = n′ if and only if B ≅ B′.

4. There is a computable sequence (φ_{n})_{n∈ω}, where each φ_{i} is a computable Σ_{1} sentence, such that

(a) for all B ∈ K there exists n such that B ⊧ φ_{n},

(b) if B, B′ ∈ K, with B ⊧ φ_{n} and B′ ⊧ φ_{n′}, then B ≅ B′ if and only if n = n′.

Remark: Note that item 2 is stating that if we see (A, n) ∈ S and A ⊆ B, then A ⊑ B.

Proof. First, to show that 1 ⇒ 2, we suppose (without loss of generality) that K ≤_{c} P F. Let Φ witness the embedding. We look for (α_{1}, φ_{1}), ..., (α_{k}, φ_{k}) ∈ Φ where {φ_{1}, ..., φ_{k}} = D(F) for F ≅ 𝔽_{p_{n}} and where there is a finite structure A in the language of K such that ∪α_{i} ⊆ D(A). Then we put (A, n) ∈ S. This S satisfies the desired properties. Next, to show 2 ⇒ 3, we convert the given S into the required S^{∗} as follows. Whenever (A, n) ∈ S, put (φ, n) ∈ S^{∗} where φ is a natural existential sentence saying that there exist elements forming a copy of A.

We get 3 ⇒ 4 immediately, letting φ_{n} be the disjunction of the existential sentences such that (φ, n) is in the given S^{∗}. Finally, we show 4 ⇒ 1. Let (B_{n})_{n∈ω} be a uniformly computable family of fields, where B_{n} ≅ 𝔽_{p_{n}}. Let Φ consist of the pairs (α(c⃗), φ), where α(\overline{c}) is obtained from a disjunct (∃\overline{u}) α(\overline{u}) of φ_{n}, by replacing the tuple of variables \overline{u} by a tuple of constants from ω, and φ ∈ D(B_{n}). Then Φ witnesses K ≤_{c} T ype I.

Motivated by the fact that many of our natural examples of classes of structures had computable enumerations, we considered how Theorem 3.4 would change if we considered only classes with this feature. We obtained the following simpler result.

Theorem 3.5. Suppose K is a class of structures with a computable enumeration. Then the following are equivalent:

1. K ≤_{c} T ype I.

2. There is a computable sequence (B_{n})_{n∈ω} such that for all n, there exists A ∈ K such that B_{n} ⊑ A, and for all A ∈ K, there is a unique n such that B_{n} is isomorphic to a substructure of A.

Proof. To show 1 ⇒ 2, we start with the set of pairs E forming an enumeration of K. Say E_{m} is the structure with

D(E_{m}) = {φ|(m, φ) ∈ E} .

Let Φ be a computable embedding of K into P F. For each m, we search for a finite set of pairs in Φ, say (α_{1}, φ_{1}), …, (α_{r}, φ_{r}), such that E_{m} ⊧ α_{k}, for 1 ≤ k ≤ r, and {φ_{1}, …, φ_{r}} = D(F) where F is a finite prime field. Assuming that the prime field F is new; i.e., for all k < m, Φ(E_{k}) is not isomorphic to F, we take a finite substructure B of E_{m} satisfying α_{k}, for 1 ≤ k ≤ r, and we let this structure be the next one on our list. If F is not new, we add nothing. The sequence (B_{n})_{n∈ω} of finite structures that we obtain in this way has the desired properties. For each A ∈ K, there is a first m such that E_{m} ≅ A, and we have put on our list an appropriate B ⊑ E_{m}.

To show 2 ⇒ 1, we start with a sequence (B_{n})_{n∈ω} as in 2, and we let S consist of the pairs (α, n), where α is the atomic diagram of a copy of B_{n}. Now, by Theorem 3.4, we have K ≤_{c} P F.

Together, Theorems 3.2 and 3.4 give us a clear picture of the requirements for a class K to have T ype I ≤_{c} K and K ≤_{c} T ype I.

3.2 Results relating to T ype II

We would like a result saying when a class of possibly infinite structures will embed in a class of T ype II. The next result is similar to Theorem 3.4 in that the structures are distinguished by sentences describing isomorphism types of substructures. To state the new result, we need the following definition (see [2], [10], or the book [1]).

Definition 6. A computable Σ_{1} formula is a c.e. disjunction of finitary existential forumulas, with a fixed tuple of free variables. A computable Σ_{1} sentence is a computable Σ_{1} formula with no free variables.

Theorem 3.6. Let K be a class of structures for the finite relational language L. Then the following are equivalent:

1. K ≤_{c} T ype II.

2. There is a c.e. set S of pairs (A, B) where A is a finite L-structure and B is a finite linear ordering, such that

(a) for any C ∈ K, there exists (A, B) ∈ S such that A ⊆ C, and (A, B) is sufficient for C, in the sense that for (A′, B′) ∈ S, if A′ ⊆ C, then B′ ⊆ B,

(b) for C, C′ ∈ K, if(A, B), (A′, B′) are elements of S sufficient for C, C′, respectively, then C ≅ C′ iff B ≅ B′.

3. There is a computable sequence (φ_{n})_{n∈ω} of computable Σ_{1} sentences such that (a) for all A ∈ K, there is some n such that A ⊧ φ_{n} & ¬φ_{n+1},

(b) for all A ∈ K and all n, A ⊧ φ_{n+1} → φ_{n},

(c) for all A, A′ ∈ K, if A ≇ A′, then there is some n such that φ_{n} is true in only one of A, A′.

Proof. To show 1 ⇒ 2, suppose we have some Φ witnessing the embedding. We put into S the pairs (A, B), where A is a finite L-structure and B is a finite linear ordering such that if D(B) = {φ_{1}, ..., φ_{k}}, there are pairs (A_{i}, φ_{i}) ∈ Φ with A_{i} ⊆ A. Now S is a c.e. set of pairs with the properties needed for 2.

To show 2 ⇒ 3, we take the given S, and for each n, we let φ_{n} be the disjunction, over the pairs (A, B) ∈ S such that B has order type at least n, of existential sentences saying that there are elements forming a copy of A. This gives a computable sequence of computable Σ_{1} sentences with the desired properties.

Finally, to show 3 ⇒ 1, suppose that we have a computable sequence (φ_{n})_{n∈ω} of computable Σ_{1} sentences satisfying the three properties in 3. Let L_{n} be the usual ordering on {0, 1, …, n − 1} (as before). Let Φ consist of the pairs (α, φ) such that for some n,

1. α = D(A), for some finite structure A in the language of K,

2. A ⊧ φ_{n}, and

3. φ ∈ D(L_{n}).

Clearly, Φ is c.e. Moreover, we can see that K ≤_{c} F LO via Φ. We note that if A ∈ K, then Φ(A) = L_{n}, where n is greatest such that A ⊧ φ_{n}.

Using these results, in the next section we will construct examples of classes that fall into places in our partial order that no previous example occupied.

4 The structure of the partial order ≤_{c}

In this section, we look at the partial order ≤_{c} on FC (classes of finite structures) and C (all classes). We begin with FC. It may not have been clear, at first face, that FC should have more than one ≡_{c}-class. However, we showed in Proposition 2.1 that there are at least two, which we called T ypes I and II. We are about to describe many, many more, showing that the partial order (FC, ≤_{c}) is not only nontrivial, but highly complex.

Definition 7. We say that the classes K and K′ are incomparable, and we write K ⊥ K′, if K ≰_{c} K′ and K′ ≰_{c} K.

The result below says that there are many inequivalent classes below T ype I.

Proposition 4.1. There is a family of classes (K_{f})_{f∈2^{ω}} such that for all f ∈ 2^{ω}, K_{f} ≤_{c} P F, and for f, g ∈ 2^{ω}, if f ≠ g, then K_{f} ⊥ K_{g}.

Proof. We assure that K_{f} ≤_{c} P F by making K_{f} ⊆ P F (see Proposition 1.3). There is a natural 1 − 1 correspondence between natural numbers and isomorphism types of prime fields—let the number n correspond to the type of 𝔽_{p_{n}}. Then each set A ⊆ ω corresponds to the class K_{A} ⊆ P F consisting of the fields of type 𝔽_{p_{n}}, for n ∈ A.

To obtain a family (K_{f})_{f∈2^{ω}} of incomparable subclasses of P F, we shall construct a family (A_{f})_{f∈ω} of subsets of ω with some special properties related to immunity. Recall that a set A ⊆ ω is immune if it is infinite and has no infinite c.e. subset (see Soare [22]). We now define a stronger property, for pairs of sets.

Definition 8. Let X ⊆ ω. For A, B ⊆ ω, we say that A and B are X bi-immune provided that for any X-computable function f with infinite range, there is some a ∈ A such that f(a) ∉ B, and there is some b ∈ B such that f(b) ∉ A. We say that A and B are bi-immune if they are X bi-immune for computable X.

If A and B are X bi-immune, then it is clear that neither has any infinite X-computably enumerable subset, and further that no partial X-computable function takes one to an infinite subset of the other. In a sense, A and B are X-immune with respect to each other. We obtain a pair of incomparable classes below P F by taking a bi-immune pair of sets A, B and forming the classes K_{A}, K_{B}. It is not difficult to see that K_{A} ⊥ K_{B}. Suppose K_{A} ≤_{c} K_{B} via Φ. We could convert Φ into a partial computable function f that maps A injectively into B. Let (A_{n})_{n∈ω} be a uniformly computable sequence of fields such that A_{n} has type 𝔽_{p_{n}}. Let f(a) = b iff when we apply Φ to the input A_{a}, we get output describing a field of type 𝔽_{p_{b}}.

To produce the family of classes (K_{f})_{f∈2^{ω}} required for Proposition 4.1, it is enough to produce a family of sets (A_{f})_{f∈2^{ω}} which are pairwise bi-immune. We prove the following.

Lemma 4.2. For any set X, there exists a family (A_{f})_{f∈2^{ω}} such that for any distinct f, g ∈ 2^{ω}, A_{f} and A_{g} are X bi-immune.

Proof. We determine the sets A_{f} in stages. At stage s, we associate with each τ ∈ 2^{s} a disjoint pair of finite sets A_{τ} , A_{τ}^{∗}, such that if ν ⊆ τ, then A_{ν} ⊆ A_{τ} and A_{ν}^{∗} ⊆ A_{τ}^{∗}. For each f ∈ 2^{ω}, we will take A_{f} to be the union of the sets A_{τ}, for τ ⊆ f. We have the following requirements.

Q_{e}: For all f ∈ 2^{ω}, |A_{f}| ≥ e
R_{<e,σ>}: For all f, g ∈ 2^{ω} such that f ⊇ σˆ 0 and g ⊇ σˆ 1, if ran(φ_{e}^{X}) is
infinite, then φ_{e}^{X}[A_{f}] ⊈ A_{g}, and φ_{e}^{X}[A_{g}] ⊈ A_{f}

We make a list of these requirements, with the feature that if Requirement s has the form R_{<e,σ>}, then |σ| ≤ s. At stage s, we will determine A_{τ} and A_{τ}^{∗} for all τ of length s, so as to guarantee satisfaction of the first s requirements.

We begin by letting A_{∅} = A_{∅}^{∗} = ∅. At stage s+1, we consider Requirement s. If it has the form Q_{e}, then for each τ of length s, we take a number k not in A_{τ} ∪A_{τ}^{∗}. We let A_{τˆ 0} = A_{τˆ 1} = A_{τ} ∪{k}, and A_{τˆ 0}^{∗} = A_{τˆ 1}^{∗} = A_{τ}^{∗}. Now, suppose Requirement s has the form R_{<e,σ>}, where |σ| ≤ s. For each τ of length s, we let A_{τˆ 0} and A_{τˆ 1} include the elements of A_{τ}, and we let A_{τˆ 0}^{∗} and A_{τˆ 1}^{∗} include the elements of A_{τ}^{∗}. We may add further elements as follows. Suppose there exist k, k′, m, m′ such that φ_{e}^{X}(k) = m and φ_{e}^{X}(m′) = k′, where k ≠ k′, m ≠ m′, and k, k′, m, m′ are not in any of the sets A_{τ}, A_{τ}^{∗}, for τ of length s. If ran(φ_{e}^{X}) is infinite, then there will exist such k, k′, m, m′. For each pair τ ⊇ σˆ 0, τ′ ⊇ σˆ 1 at level s, we add k to A_{τˆ 0} and A_{τˆ 1}, and we add m to A_{τ′ˆ 0}^{∗} and A_{τ′ˆ 1}^{∗}. Similarly, we add m′ to A_{τ′ˆ 0} and A_{τ′ˆ 1}, and we add k′ to A_{τˆ 0}^{∗}, A_{τˆ 1}^{∗}.

We have described the construction. When we form the sets A_{f} = ∪_{σ⊆f}A_{σ}, as planned, each of the requirements is satisfied, and the conclusion of the lemma holds. We note that the construction could be carried out using a Δ_{2}^{0}(X) oracle, so that the assignment of finite sets A_{τ} and A_{τ}^{∗} to τ ∈ 2^{<ω} is Δ_{2}^{0}(X).

Having completed the proof of Lemma 4.2, we have also completed the proof of Proposition 4.1.

There are also incomparable degrees that are not below T ype I. These may be obtained by using Δ_{2}^{0} bi-immune sets and letting them determine linear orders instead of prime fields.

Proposition 4.3. There is a family of classes (K_{f})_{f∈2^{ω}} such that for all f ∈ 2^{ω}, K_{f} ≤_{c} F LO and K_{f} ⊥ P F, and for distinct f, g ∈ 2^{ω}, K_{f} ⊥ K_{g}.

Proof. We show that any pair of Δ_{2}^{0} bi-immune sets gives rise to a pair of subclasses of LO that are incomparable with each other and with P F. Then to obtain the family of classes (K_{f})_{f∈2^{ω}} with the required properties, we apply Lemma 4.2 to get a family (A_{f})_{f∈2^{ω}} of pairwise Δ_{2}^{0} bi-immune sets, and let K_{f} be the set of linear orders whose sizes are in A_{f}.

Let A and B be Δ_{2}^{0} bi-immune sets. Let K_{1} be the class of linear orders whose sizes are members of A, and let K_{2} be the class of linear orders whose sizes are members of B. By Proposition 1.3, K_{i} ≤_{c} F LO. We must show that K_{1} ⊥ K_{2}. Suppose not, say K_{1} ≤_{c} K_{2} via Φ. We convert Φ into a partial Δ_{2}^{0} function f that maps A injectively into B. Let (L_{n})_{n∈ω} be a uniformly computable family of orderings, where L_{n} has type n. We let f(a) = b if Φ takes L_{a} to an ordering of type b. Using Δ_{2}^{0}, we can determine, for each input structure A_{a}, the full atomic diagram of the output structure Φ(L_{a}). Now, f maps A injectively into B, contradicting the assumption that A, B are Δ_{2}^{0} bi-immune.

We must show that K_{i} ⊥ P F. The fact that K_{i} ≰_{c} P F follows from Corollary 2.2. Suppose P F ≤_{c} K_{1} via Φ. Let (A_{n})_{n∈ω} be a uniformly computable sequence of fields, where A_{n} has type 𝔽_{p_{n}}. Then we have an injective Δ_{2}^{0} function g from ω into A, defined so that g(n) is the number of elements in Φ(A_{n}). This contradicts the immunity assumptions. Therefore, P F ≰_{c} K_{i}.

We still have not shown that there are classes properly between T ypes I and II. On one hand, it seems that the only difference between these two types is whether, in building the structure, we can tell whether we’re done or not. Thus, it would not be surprising to see that there was simply nothing in between. On the other hand, there is a sense in which T ype I looks analogous to a computable degree, and T ype II to a complete c.e. degree, so it is also reasonable to think that there are things between them. It turns out that this second argument may be closer to the truth.

Proposition 4.4. There is a pairwise incomparable family of classses (K̂_{f})_{f∈2^{ω}} such that P F ⪇_{c} K̂_{f} ⪇_{c} F UG, where F UG is the class of finite undirected graphs.

Proof. For simplicity, the discussion here will show only how to produce a single class K̂. The construction of 2^{ℵ_{0}} incomparable classes K̂_{f} would follow the outline of Lemma 4.2. The class K̂ will be made up of finite graphs. This guarantees that K̂ ⊆ F UG. Let (C_{n})_{n∈ω} be a uniformly computuble sequence of cyclic graphs of size n. To guarantee that P F ≤_{c} K̂, we include the graphs of isomorphism type C_{2n}, for all n ∈ ω. This suffices, since we have a computable embedding that takes fields of type 𝔽_{p_{n}} to C_{2n}.

To guarantee that K̂ ≰_{c} P F, we satisfy the following requirements.

R_{e}: W_{e} does not witness that K̂ ≤_{c} P F.

The strategy for R_{e} is as follows. We give W_{e} = Φ input C_{2e+1}, and see if it produces a prime field as output (we could determine this using a Δ_{2}^{0} oracle). If not, then we put all copies of C_{2e+1} into K̂. If, given input C_{2e+1}, Φ produces as output some finite prime field, then we do not put copies of C_{2e+1} into K̂. Instead, we add all copies of two different extensions of C_{2e+1}. We could take these to be the result of adding a single new vertex, and either connecting it to one of the vertices of C_{2e+1}, or not.

We have described all elements of the class K̂. We have satisfied each requirement R_{e}—either C_{2e+1} ∈ K̂, and Φ does not map it to a finite prime field, or else K̂ contains two nonisomorphic extensions of C_{2e+1} (neither isomorphic to a substructure of the other), and Φ fails to map them to nonisomorphic prime fields, since the diagram of Φ(C_{2e+1}) is contained in the output for both extensions. Finally, we must show that F UG ≰_{c} K̂. For this, we use Corollary 1.2, noting that there are arbitrarily large finite increasing chains of graphs, and there are no chains of structures in K̂ of length greater than one.

In fact, there is an infinite chain of classes between T ypes I and II, all incomparable with K̂. These, and more examples to come, are formed by starting with a class of T ype I (for aesthetic reasons, usually cyclic graphs) and adjoining subclasses of a T ype II class. For instance, we can build all the examples constructed here using only cyclic graphs and chains (simply connected graphs in which each vertex is connected to at most two others). The following will be useful. Clearly any class containing only these elements is a subclass of the set of finite graphs, and is thus reducible to T ype II.

Proposition 4.5. Let K̂ be as in Proposition 4.4. Then there is a sequence of classes (K_{n})_{n} ∈ ω such that

P F ≡_{c} K_{0} ⪇_{c} K_{1} ⪇_{c} K_{2} ⪇_{c} … ≤_{c} F LO ,

and for all n > 0, K_{n} ⊥ K̂.

Proof. For the moment, we let K_{n} consist of all finite prime fields and all chains of length j for j ≤ 2n. This will make it easier for us to refer back to the construction of K̂ in the proof of Proposition 4.4. At the end of the proof, we shall replace the prime fields by cyclic graphs.

Since P F = K_{0}, we have P F ≡_{c} K_{0}. For all n, we have K_{n} ≤_{c} K_{n+1}, since K_{n} ⊆ K_{n+1} (using Proposition 1.3). We must show that K_{n+1} ≰_{c} K_{n}. If K_{n+1} ≤_{c} K_{n}, witnessed by Φ, then Φ maps at least two nonisomorphic chains to finite prime fields. We may suppose that one of these chains is a substructure of the other. Since no prime field is a substructure of another, Corollary 1.2 gives a contradiction. Thus, there is no such Φ, and K_{n} ⪇_{c} K_{n+1}. We have K_{n} ≤_{c} F LO, for all n, just because all of the structures in K_{n} are finite— in Section 2, we saw that all classes of finite structures can be computably embedded in F LO.

We must show that for all n > 0, K_{n} ⊥ K̂. We get the fact that K_{n} ≰_{c} K̂ using Corollary 1.2. The class K_{n} contains a chain of structures of length at least 2, while K̂ has no such chains. Finally, we show that K̂ ≰ K_{n}. Suppose K̂ ≤_{c} K_{n}, witnessed by Φ = W_{e}. We constructed K̂ so that either C_{2e+1} is in K̂ and Φ fails to map C_{2e+1} to a finite prime field, or else K̂ contains two nonisomorphic extensions of C_{2e+1}, while Φ gives output for both that contains the diagram of the same finite prime field (so Φ cannot map these extensions to either finite prime fields or chains).

Now, Φ cannot map C_{2e+1} to a finite prime field, and must instead map it to one of the chains in K_{n}. Recall that there are infinitely many different indices e′ for the same c.e. set Φ. If Φ = W_{e′}, then the argument above shows that Φ must map C_{2e′+1} to one of the chains in K_{n}. Since there are only finitely many isomorphism types of chains in K_{n}, and Φ must map infinitely many nonisomorphic cyclic graphs to them, Φ cannot be 1 − 1 on isomorphism types. Thus, K̂ ≰_{c} K_{n}.

At this point, we replace the finite prime fields in each class K_{n} by the finite cyclic graphs. The resulting class is computably equivalent to K_{n}, but it satisfies the convention that all structures in a class have the same finite relational language. We justify the temporary violation of our convention that all members of a class have a common language by noting that we could have substituted finite cyclic graphs for the prime fields in the construction in Proposition 4.4, and in the classes K_{n}.

Now, any class consisting of all finite cyclic graphs and infinitely many finite chains will lie strictly above K_{n}, for all n, and will be bounded above by T ype II. We will use exactly this sort of class to produce many more incomparable classes between the chain of K_{n}’s and T ype II.

Proposition 4.6. Let (K_{n})_{n∈ω} be as in Proposition 4.5. Then there is a family of pairwise incomparable classes (H_{f})_{f∈2^{ω}} lying above all K_{n} and below T ype II.

Proof. We show how to produce two classes H, H′. Each class will contain all finite cyclic graphs. We add finite chains so as to satisfy the following requirements:

R_{e}: W_{e} does not witness H ≤_{c} H′
R′_{e}: W_{e} does not witness H′ ≤_{c} H

We make a list of the requirements and satisfy them in order. The strategy for R_{e} is as follows. Let Φ = W_{e}. For earlier requirements, we will have decided, for finitely many k, whether or not to put chains of length k into H, H′. Take n greater than any of these k. Then n is also an upper bound on the number of chains already in H′. We add chains to H so that there is an increasing sequence L_{0} ⊆ … ⊆ L_{n} of length n + 1. If Φ does not map these L_{i} to an increasing sequence of chains, then the requirement is already satisfied. (If Φ maps some L_{i} to a prime field, then we would have a contradiction of Corollary 1.2.) If Φ maps the L_{i} to an increasing sequence of chains, then at least one, say the chain of length m, is not already in H′. We satisfy the requirement by keeping chains of length m out of H′. The strategy for R′_{e} is the same, so it is clear that we can produce two incomparable classes H, H′, lying above all K_{n} and below T ype II.

In satisfying any one requirement, we make only finitely many decisions about which chains do and do not belong to a given class. Therefore, we could use the same strategy to produce a family (K_{f})_{f∈2^{ω}} of incomparable classes. We would follow the outline in the proof of Lemma 4.2.

The results so far, for classes of finite structures, are summarized in Figure 3. Finite orders lie at the top, along with finite undirected graphs. Finite cyclic groups, and finite simple groups lie there too. Prime fields lie strictly lower. The empty class obviously lies on the bottom. The classes consisting of copies of a single finite structure lie just above that—equivalent to classes consisting of copies of a single computable structure. The numbers 4.3, 4.6, 4.1 refer to propositions showing the existence of large incomparable families, and 4.5 refers to the proposition producing a chain. The question marks indicate places where there may or may not be a class, lying below certain classes and above certain others.

Of course, the structure is dramatically enriched when we also consider classes containing infinite structures. We have seen that the class F V S of finite dimensional vector spaces over the rationals sits strictly above T ype II. First, let us show that there are classes below F V S that are not below T ype II.

Proposition 4.7. There is a family of classes (K_{f})_{f∈2^{ω}}, such that for all f ∈ 2^{ω}, K_{f} ≤_{c} F V S and K_{f} is incomparable with T ypes I and II, and for distinct f, g ∈ 2^{ω}, K_{f} ⊥ K_{g}.

[figure: finite orders; …; 4.6; ?; …; 4.4; 4.5; 4.3; prime fields; …; 4.1; ?; …; single ≅-type; empty]

Figure 3: Classes of finite structures

Proof. Let A, B ⊆ ω be a pair of Δ_{3}^{0} bi-immune sets, and let K, K′ be the classes of ℚ-vector spaces whose dimensions are members of A, B, respectively. We have K, K′ ≤_{c} F V S, by Proposition 1.3. Next, we show that K, K′ are incomparable with T ypes I and II. By Corollary 2.7, no class containing vector spaces of two different dimensions embeds in F LO. Therefore K, K′ ≰_{c} F LO, and it follows that K, K′ ≰_{c} P F. Let (A_{n})_{n∈ω} be a uniformly computable sequence of fields, where A_{n} ≅ 𝔽_{p_{n}}. Suppose P F ≤_{c} K via Φ. From Φ, we will obtain a Δ_{3}^{0} function f mapping ω injectively into A. We let f(n) be the dimension of Φ(A_{n}). Note that the relation {(n, m)|dim(Φ(A_{n})) ≥ m} is Σ_{2}^{0}. From this, it is clear that f is Δ_{3}^{0}. This contradicts the immunity properties of A. Therefore, P F ≰_{c} K, and similarly P F ≰_{c} K′. It follows that F LO ≰_{c} K, K′.

Similarly, we show that K ⊥ K′. Let (V_{n})_{n∈ω} be a uniformly computable family of vector spaces, where V_{n} has dimension n. If K ≤_{c} K′ via Φ, then we would have a partial Δ_{3}^{0} function f mapping A injectively into B. We let f(a) be the dimension of Φ(V_{a})—assuming that this is a finite-dimensional vector space, we can apply a Δ_{3}^{0} procedure to find the dimension.

Now, Lemma 4.2 yields a family (A_{f})_{f∈2^{ω}} of pairwise Δ_{3}^{0} bi-immune sets. For each f ∈ 2^{ω}, we let K_{f} be the class of vector spaces of dimension in A_{f}. The argument above shows that this family has all of the properties needed in Proposition 4.7.

The interval between T ype II and F V S admits further complexity. There is an ω-chain with an infinite antichain above it, all in this interval.

Lemma 4.8. If K = F LO ∪ F V S, then K ≤_{c} F V S.

Proof. We define a computable embedding Φ that takes a linear order of size n to a vector space of dimension 2n+1, and takes a vector space of dimension n to one of dimension 2n. Only the last part requires verification. We partition ω into three infinite computable sets A, B, C, and we let f, g, h be injective computable functions mapping ω into A, B, C, respectively. Suppose α is a finite set of atomic sentences and negations of atomic sentences (appropriate to be included in the diagram of a vector space over ℚ). Say α describes distinct vectors n_{0}, …, n_{k}, where n_{0} is the zero vector. We modify g, letting g(n_{0}) = f(n_{0}). Let α^{∗} consist of sentences φ(f(n_{0}), …, f(n_{i})) and φ(g(n_{0}), g(n_{1}), …, g(n_{k})), where φ(n_{0}, …, n_{k}) ∈ α, plus further sentences saying f(n_{i}) + g(n_{j}) = h(< n_{i}, n_{j} >), for i, j ≠ 0, and sentences generated from these by the axioms for vector spaces. For example, if we have the sentence q · n_{i} = n_{j}, where i ≠ 0 and q is a non-zero rational, then we obtain the sentence q · h(< n_{i}, n_{i} >) = h(< n_{j}, h_{j} >). We put into Φ the pairs (α, φ), where α is as described, and φ is in the corresponding set α^{∗}.

Proposition 4.9. There is a sequence of classes (J_{n})_{n∈ω} such that

F LO ≤_{c} J_{0} ⪇_{c} J_{1} ⪇_{c} J_{2} … ≤_{c} F V S .

Proof. We define J_{n} to be the class containing all finite linear orders and all rational vector spaces of dimension at most 2n. If we wish, we can consider these as structures in a single language, one that enables us to distinguish a linear order from a vector space. Clearly, F LO = J_{0}. The proof that F V S ≰_{c} F LO (from Theorem 2.6) shows that J_{1} ≰_{c} F LO. By Proposition 1.3, we have J_{n} ≤_{c} J_{n+1}. Finally, if J_{n+1} ≤_{c} J_{n} via Φ, then Φ would map at least two isomorphism classes of vector spaces to isomorphism classes of linear orders, which is again impossible.

In Proposition 4.6, we obtained incomparable classes strictly between T ypes I and II by adding to the class all of finite prime fields the linear orders of selected sizes. Below, we use the same idea to obtain incomparable classes above all J_{n} and below F V S.

Proposition 4.10. Let (J_{n})_{n∈ω} be as in Proposition 4.9. There exist pairwise incomparable classes (G_{f})_{f∈2^{ω}} such that for all n ∈ ω and all f ∈ 2^{ω}, we have J_{n} ≤_{c} G_{f} ≤_{c} F V S. (Then J_{n} ⪇_{c} G_{f} ⪇_{c} F V S.)

Proof. Each class G_{n} will contain all finite linear orders. We add vector spaces of selected dimensions so as to satisfy the following requirements.

R_{⟨e,σ⟩}: for all f ⊇ σˆ 0, g ⊇ σˆ 1, W_{e} does not witness G_{f} ≤_{c} G_{g}.
R′_{⟨e,σ⟩}: for all f ⊇ σˆ 0, g ⊇ σ 1, W_{e} does not witness G_{g} ≤_{c} G_{f}.

We have a list of all requirements. At each stage s, we have decided, for finitely many pairs (i, n), whether to put vector spaces of dimension n in G_{f}, for f ⊇ τ, for τ of length s. We write G_{τ} for the class reflecting the decisions made up to stage s. In the end, we will let G_{f} be the union of the sets G_{τ}, for τ ⊆ f.

We satisfy the requirements in order. At stage s + 1, we consider Requirement s. Say this is R_{⟨e,σ⟩}, and let Φ = W_{e}. Take n greater than the dimension of any vector spaces considered so far. For all τ ⊇ σˆ 0 of length s + 1, we put into G_{τ} the vector spaces of dimension n + i for i ≤ n. If Φ does not map

[figure: linear orders; 4.12; vector spaces; ...; 4.10; ?; 4.9; finite orders; 4.11; prime fields; …; 4.7; empty]

Figure 4: Classes of structures, possibly infinite

one of the newly added vector spaces to anything in F LO ∪ F V S, then the requirement is trivially satisfied. If Φ embeds G_{τ} into F LO ∪ F V S, then by the argument in Theorem 2.6 or Corollary 2.7, since G_{τ} contains vector spaces of at least two different finite dimensions, Φ cannot map any vector space in G_{τ} to a finite linear order. Thus, Φ must map one of the n + 1 new vector spaces to a vector space of dimension greater than n. We satisfy the requirement by keeping the vector spaces of this dimension out of G_{ν}, for all ν ⊇ σˆ 1 of length s + 1.

There are other classes not below F V S. Of course, any class is embeddable in the class of infinite graphs. Also, we have an increasing sequence of classes that is not below F V S. For each ordinal α < ω_{1}, let LO^{α} denote the set of well orders of order type less than α.

Proposition 4.11. If α < β < ω_{1}, then LO^{α} ⪇_{c} LO^{β}. Also, for ω < α, LO^{α} ≰_{c} F V S.

Proof. If α < β, then Proposition 1.3 yields the fact that LO^{α} ≤_{c} LO^{β}. There are representatives of the order types in LO^{α} forming a chain of structures of length α. Then by Corollary 1.2, if α < β, L^{β} ≰ L^{α}, and if α > ω, then L^{α} ≰_{c} F V S.

This result also suffices to show that the class of infinite linear orders does not lie below the finite dimensional vector spaces. However, we have the following:

Proposition 4.12. If LO is the class of linear orders (possibly infinite), and F V S is the class of finite dimensional ℚ-vector spaces, then F V S ≤_{c} LO.

Proof. Each vector space V will correspond to a substructure of ω·η, in which for each n ≤ dim(V), we have densely many copies of the finite linear order of size n, and also densely many copies of ω. Clearly if we can describe a computable transformation that behaves this way, it will be well-defined and injective on isomorphism types.

Let B be the lexicographic ordering on ℚ × ω. We partition ℚ computably into dense subsets ℚa⃗, corresponding to finite sequences a⃗ of natural numbers. Given a finite set α of atomic sentences and negations of atomic sentences describing an n-tuple of vectors a⃗, let α^{∗} describe the restriction of B to ℚa⃗ × ω, if α contains evidence that a⃗ is dependent, and ℚa⃗ × n, otherwise. Let Φ consist of the pairs (α, φ), where φ ∈ α^{∗}.

Thus, the situation when we include classes containing infinite structures looks something like Figure 4. Undirected graphs lie on top. Linear orders actually also lie on top. Friedman and Stanley [8] give a Borel embedding of undirected graphs in linear orderings that can be converted into a computable embedding.^{1} Finite dimensional vector spaces over ℚ lie strictly below linear orders, and finite linear orders lie strictly below vector spaces. The numbers 4.7, 4.10, etc., indicate the propositions being illustrated.

5 Problems

In this section, we list some open problems. The first two ask for further cdegrees representing “natural” classes. The natural classes of finite structures that we considered all lay in one of two c-degrees, and the c-degrees of natural classes (of possibly infinite structures) were linearly ordered.

Problem 1. Is there a natural class K, consisting of finite structures of infinitely many different isomorphism types, such that K is not computably equivalent to either finite prime fields or finite linear orderings? In particular, is there a natural example of a class properly between these two?

Problem 2. Is there a natural pair of classes K, K′ such that K ⊥ K′?

We have results characterizing those classes that computably embed in the finite prime fields, and also in the finite linear orderings. For classes that embed in the finite dimensional vector spaces over ℚ, we can give some necessary conditions, but we have no characterization.

Problem 3. Characterize the classes K such that K ≤_{c} F V S.

We have not entirely sorted out the differences between the definition of ≤_{c} that we chose and the two alternative definitions. We can show that the partial ordering obtained from Definition 1′′ differs from ≤_{c}. We do not know about the partial ordering obtained from Definition 1′.

Problem 4. Is it true that for any classes of structures K, K′, K ≤_{c} K′ iff there is a computable operator Φ = φ_{e} of the kind in Definition 1′, taking A ∈ K to B ∈ K′ such that φ_{e}^{D(A)} = χ_{D(B)}, in a way that is well-defined and 1 − 1 on isomorphism types?

1The conversion will be given in [6], along with a result showing that there is no computable embedding of undirected graphs in linear orderings satisfying some further conditions of finiteness and homogeneity.

References

[1] Ash, C. J., and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Elsevier Science, 2000.

[2] Ash, C. J., and A. Nerode, “Intrinsically recursive relations”, in Aspects of Effective Algebra, ed. by J. N. Crossley, Upside Down A Book Co., Steel’s Creek, Australia, pp. 26–41.

[3] Becker, H., and A. S. Kechris, The descriptive set theory of Polish group actions, London Math. Soc. Lecture Note Series, vol. 232, Cambridge Univ. Press, 1996.

[4] Calvert, W., “The isomorphism problem for classes of computable fields”, preprint.

[5] Calvert, W., “The isomorphism problem for classes of computable Abelian groups”, preprint.

[6] Cummins, D., senior thesis, University of Notre Dame, in preparation.

[7] Dyment, E. Z., “Certain properties of the Medvedev lattice”, Matematičeskii Sbornik, vol. 101(143)(1976), pp. 360-379 (Russian); English translation, Mathematics of the USSR Sbornik, vol. 30(1976), pp. 321–340.

[8] Friedman, H., and L. Stanley, “A Borel reducibility theory for classes of countable structures”, J. Symb. Logic, vol. 54(1989), pp. 894–914.

[9] Goncharov, S. S., and J. F. Knight, “Computable structure and nonstructure theorems”, Algebra and Logic, vol. 41(2002), pp. 351–373.

[10] Harizanov, V. S., “Some effects of Ash-Nerode and other decidability conditions on degree spectra”, Annals of Pure and Applied Logic, vol. 55(1991), pp. 51–65.

[11] Hirschfeldt, D., B. Khoussainov, R. Shore and A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Annals of Pure and Appl. Logic, vol. 115(2002), pp. 71–113”.

[12] Hjorth, G., Classification and Orbit Equivalence Relations, Amer. Math. Society, 1999.

[13] Hjorth, G., and A. S. Kechris, “Recent developments in the theory of Borel reducibility”, Fund. Math., vol. 170(2001), pp. 21–52.

[14] Hjorth, G., and A. S. Kechris, “Analytic equivalence relations and Ulmtype classifications”, J. Symb. Logic, vol. 60(1995), pp. 1273–1300.

[15] Knight, J. F., “Algebraic structure of classes under computable embedding”, in preparation.

[16] Marker, D., Model theory: An Introduction, Springer-Verlag, 2002.

[17] Medvedev, Yu. T, “Degrees of difficulty of the mass problems”, Doklady Akademii Nauk SSSR, vol. 104(1955), pp. 501–504 (Russian).

[18] Nies, A., “Undecidable fragments of elementary theories”, Algebra Universalis, vol. 35(1996), pp. 8–33.

[19] Rabin, M. O., and D. Scott, “The undecidability of some simple theories”, preprint.

[20] Rogers, H., Theory of Recursive Functions and Effective Computability, MIT Press,1987.

[21] Simpson, S., and S. Binns, “Embeddings into the Medvedev and Muchnik lattices of Π_{1}^{0} classes, preprint.

[22] Soare, R. I., Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.

[23] Sorbi, A., “Some remarks on the algebraic structure of the Medvedev lattice”, J. Symb. Logic, vol. 55(1990), pp. 831–853.