Solutions of the Goncharov-Millar and Degree Spectra Problems in The Theory of

Computable Models

Bakhadyr Khoussainov The University of Auckland New Zealand Richard A. Shore^{∗} Cornell University USA

The theory of computable models is an intensively developing area of mathematics that studies the interactions between the theory of models and computability theory. Analyzing the relationships between computable presentations of models, model-theoretic definability and the computable complexity of relations is one of the central problems in this area. A fundamental notion in the study of these problems is that of being computable isomorphic or autoequivalent as first introduced by A.I. Malcev [5]. We call a model B computable if its domain, basic predicates and operations are uniformly computable. If a model B is computable and is isomorphic to a model A, then B is called a computable presentation of A. Computable presentations B_{1} and B_{2} are computably isomorphic (autoequivalent) if there exists a computable isomorphism between B_{1} and B_{2}. The maximal number of computable but not computably isomorphic presentations of a model B is called the computable (algorithmic) dimension of B and is denoted by dim(B). A model B is computably categorical (autostable) if dim(B) = 1. Atomless Boolean algebras and dense linearly ordered sets are typical examples of computably categorical models. The notion of computable dimension was introduced by Goncharov. He proved that for any natural number n ≥ 1 there exists a model whose computable dimension is n [2]. By an appropriate coding of these models of Goncharov, examples of groups, partially ordered sets, unary and other algebras of computable dimension n have been constructed in [2] [3] [6].

One of the important problems in this area is that of Goncharov-Millar about the relationship between the computable dimension of any given model B that of its expansion (B, c_{1}, …, c_{m}) by finitely many constants. We note that the following inequality always holds: dim(B) ≤ dim(B, c_{1}, …, c_{m}). The following theorem gives a full solution to the Goncharov-Millar problem.

Theorem 1 For any nonzero cardinal n ≤ ω there exists a computably categorical model B such that the computable dimension of the model (B, c) is n for any given constant c ∈ B.

∗Partially supported by NSF Grants DMS-9503503, DMS-9802843 and INT-9602579

For finite n, this theorem is proved in [7]. The case n = ω requires some new ideas and a new mechanism for constructing the desired model. It has been proved by the authors in collaboration with D. Hirschfeldt. The following is a corollary to the proof of the theorem.

Corollary 2 1. For all n, m ∈ ω there exists a model B such that dim(B) = n + 1 and dim(B, c) = n + m + 1 for any constant c ∈ B.

2. For all n ∈ ω there exists a model B such that dim(B) = n + 1 and dim(B, c) = ω for any constant c ∈ B.

One of the central problems directly related to the study of computable dimension is the problem of characterizing the computable complexity of a relation (which is not included in the language) in computable presentations of a model. This problem was informally stated by Nerode at the beginning of the 70s. In order to study this problem, Harizanov and Millar [9] introduced the notion of the degree spectrum of a given relation. The spectrum of a relation R on a model B, denoted by S(R), is the set of all Turing degrees of images of R in computable presentations of the model B. The study of this set is closely related to questions about the definability of R in the language L_{ω_{1},ω}. It has been extensively studied by Ash, Knight, Nerode and others. It is obvious that if dim(B) < ω and R is fixed by each automorphism of the model, then the set S(R) is finite. Harizanov noted in [9] that Goncharov’s model of computable dimension 2 provides an example of a relation R such that S(R) = {0, a}, where 0 is the Turing degree of the recursive sets and a is the Turing degree of a set which is Δ_{3}^{0} in the Kleene-Mostowski hierarchy. Using the construction from [1], she constructed in [9] a model B with a relation R such that dim(B) = 2 and S(R) = {0, a}, where a is the degree of a Δ_{2}^{0}-set. Goncharov and Khoussainov [4] improved this result by constructing a model B with a relation R such that dim(B) = 2 and S(R) = {0, a}, where a is the degree of a recursively enumerable set. However, the following two questions, formulated in [4], that constitute the degree spectra problem had remained opened.

Question 1 Which finite partially ordered sets are isomorphic to partially ordered sets of the type (S(R), ≤), where ≤ is Turing reducibility?

Question 2 Which finite sets {a_{1}, …, a_{n}} of recursively enumerable degrees coincide with S(R), where R is a relation on a model whose computable dimension is n?

In [8] the authors give a full solution to Question 1. Very recently the authors have also been able to answer the second question.

Theorem 3 For any finite set {a_{1}, …, a_{n}} of recursively enumerable degrees there exists a model B and a relation R on it such that dim(B) = n and S(R) = {a_{1}, …, a_{n}}.

This theorem also answers the first question because any countable partially ordered set can be embedded into the set of recursively enumerable Turing degrees. We note that D. Hirschfeldt has also recently proved this theorem independently using somewhat different ideas [10].

The main step in our proof of Theorem 2 consists of a construction that builds a model B and a relation R on it with the following properties:

1. dim(B) = 2,

2. S(R) = {0, a},

where a is the Turing degree of a given recursively enumerable set. In order to satisfy these properties the construction must build two computable presentations B_{1} and B_{2} of B, isomorphic relations R_{1} and R_{2} on B_{1} and B_{2}, respectively, satisfying the following requirements:

D_{e}) ϕ_{e} is not an isomorphism between B_{1} and B_{2},

R_{j}) If C_{j} is isomorphic to B, then C_{j} is computably isomorphic to either B_{1} or B_{2},

P_{1}) The set R_{1} is recursive,

P_{2}) The set R_{2} is recursively enumerable and of degree a,

where a is a given recursively enumerable degree; ϕ_{e}, e ∈ ω, is an enumeration of all partial recursive functions; and C_{j}, j ∈ ω, is an enumeration of all recursively enumerable models. In order to satisfy all these requirements, two problems must be solved. The first problem arises from the conflicts between the requirements D_{e} and R_{j}, e, j ∈ ω. The resolution of these conflicts allows us to control the computable dimension of B. The ideas for controlling the computable dimension of B come from [8] and [1]. The second problem arises in resolving the conflict between controlling the computable dimension of B and coding the degree a into R_{2}. Two ideas are used in the solution of this problem. First, the model B is taken from a special class of graphs so that algebraic properties, in particular, various connectedness properties of B influence the construction’s outcomes at certain stages. Second, the requirements D_{e}, e ∈ ω, together with the coding requirement P_{2}, are satisfied by using a new procedure for modifying the graph being constructed as numbers are enumerated into a fixed set A of degree a so as to code A into the graph.

Now, all known computable models B of finite computable dimensions, if not computably categorical, are at least Δ_{3}^{0}–categorical, i.e. if A is computable and isomorphic to B then there is an isomorphism from A to B which is Δ_{3}^{0}. We conclude this paper with the following question.

Question 3 Is there, for each n ≥ 3, a computable model of computable dimension 2 which is Δ_{n+1}^{0}-categorical but not Δ_{n}^{0}-categorical?

References

[1] S.S. Goncharov, Computable Univalent Numerations, Algebra and Logic 19 (1980), N 5, 507-551.

[2] S.S. Goncharov, The Problem of Nonautoequivalent Constructivizations, Algebra and Logic 19 (1980), N 6, 621-639.

[3] S.S. Goncharov, A.V. Molokov and N.C. Romanovsky, Nilpotent Groups of Finite Algorithmic Dimensions, Siberian Math. Journal 30 (1989), N 1, 82-88.

[4] S.S. Goncharov and B. Khoussainov, Degree Spectra of Decidable Relations, Dokl. Akadem. Nauk SSSR 352 (1997), N 3, 301-303.

[5] A.I. Malcev, Recursive Abelian Groups, Dokl. Akademii Nauk SSSR 146 (1961), N 5, 1009-1012.

[6] B. Khoussainov, Algorithmic Degrees of Unars, Algebra and Logic 27 (1988), N 4, 479-494.

[7] P. Cholak, S.S. Goncharov, B. Khoussainov and R.A. Shore. Computably Categorical Structures and Expansions by Constants, J. Symbolic Logic. to appear.

[8] B. Khoussainov and R. Shore, Computable Isomorphisms, Degree Spectra of Relations and Scott Families, Annals of Pure and Applied Logic 93 (1998), N 1-3, 153-193.

[9] V. Harizanov, The Possible Turing Degree of the Nonzero Member in a two Element Degree Spectra, Annals of Pure and Applied Logic 55 (1991), N 1, 51-65.

[10] D. Hirschfeldt, Ph.D. Dissertation, Cornell University, 1999.