The low_{n} and low_{m} r.e. degrees are not elementarily equivalent

Richard A. Shore^{∗} Department of Mathematics Cornell University Ithaca NY 14853

September 21, 2004

Abstract

Jockusch, Li and Yang (TAMS 356 (2004), 2557-2568) showed that the Low_{n} and Low_{1} r.e. degrees are not elementarily equivalent for n > 1. We answer a question they raise by using the results of Nies, Shore and Slaman (PLMS (3) 77 (1998), 241-291) to show that the Low_{n} and Low_{m} r.e. degrees are not elementarily equivalent for n > m > 1.

1 Introduction

Decision problems were the motivating force in the search for a formal definition of algorithm that constituted the beginnings of recursion (computability) theory. In the abstract, given a set A, the decision problem for A consists of finding an algorithm which, given input n, decides whether or not n is in A. The classic decision problem for logic is whether a particular sentence is a theorem of a given theory T. Other examples arise in almost all branches of mathematics. In most settings one is almost immediately confronted by the notion of a recursively (or computably) enumerable set (the sets which can be listed (i.e. enumerated) by a computable (i.e. recursive) function): the theorems of a axiomatized theory, the solvable Diophantine equations, the true equations between words in a finitely presented group, etc. Typically, such decision problems amount to deciding if a particular r.e. set is computable (recursive). Indeed, the first examples of unsolvable decision problems provided examples of nonrecursive r.e. sets: the theorems of predicate logic, the word problem for groups, the halting problem. (For technical convenience, we code all expressions in formal languages, groups, etc. as natural numbers and so restrict our attention to sets of natural numbers.)

∗Partially supported by NSF Grant DMS-0100035 and New Directions in Theory and Applications of Models of Computation, Grand International Joint Project, No. 60310213 (P. R. China).

One can say that all these sets are simply noncomputable. Another view sees them as more complicated or harder to compute than the recursive sets. This is the view that leads to the notion of relative computability (reducibility) introduced by Turing [1936],

[1939] and Post [1936], [1944]. The equivalence classes under this notion of relative computability were first called the degrees of recursive unsolvability. As Church’s Thesis identifying the recursive functions with the (intuitively) calculable ones became widely accepted, the word “recursive” was dropped and they became simply the degrees of unsolvability. As Turing’s model of computation became the standard one, they became the Turing degrees. In view of the centrality of Turing’s notion as the basic general definition of computability, the unqualified notion of degree eventually became that of Turing degrees. (We typically denote the degree of a set A by a.)

The starting point for the investigation of this fundamental notion of relative computability was the r.e. degrees (those equivalence classes containing r.e. sets). The classic results of logic (such as Gödel’s incompleteness theorem, Church’s proof of the undecidability of predicate logic and Turing’s unsolvability of the Halting problem) each proved that there was a nonrecursive r.e. degree. The construction of r.e. sets of incomparable degree by Friedberg [1957] and Muchnik [1956] began an intensive study of the internal structure of R, the r.e. degrees with ≤. (See Shore [1999] for a general introduction and survey.)

Over the past two decades, much of the research into this structure (as well as that of all the Turing degrees) has been directly devoted to, or viewed as directed at, the study of global properties of these degree structures with the partial order induced by relative computability, ≤_{T}. (In fact, the ordering is an upper semilattice with join denoted by ∨.) The primary topics of investigation have been determining the complexity of their theories, restricting the action of possible automorphisms and the delineation of the relations definable in the structures. A common subtext of these investigations has been the relation between these questions, more specific structural results and the complexity of definitions of the sets themselves in arithmetic.

Within the degrees, the marker of syntactic complexity of the definition of a set in arithmetic is the Turing jump. Given a set A, its Turing jump, A′, is {e|ϕ_{e}^{A}(e) converges}. This set of indices is the halting problem for machines ϕ_{e}^{A} with index e and an oracle for A, i.e. direct access to information about the membership of numbers in A. This operation on sets is easily seen to preserve the Turing order and so to be well defined on degrees. It corresponds to one additional alternation of quantifiers in the definition of A. The jump of a degree a is denoted by a′ and its nth iteration by a^{(n)}. The degree of the recursive sets is denoted by 0 and so that of the halting problem by 0′.

From now on, we restrict our attention to the r.e. degrees, R. Within this structure, the classification induced by the action of the jump operator is given by the high/low hierarchy which measures the complexity of the jumps of a: a is high_{n}, a ∈ H_{n}, if a^{(n)} = 0^{(n+1)} (so the n^{th} jump of a is as high as possible) and a is low_{n}, a ∈ L_{n}, if a^{(n)} = 0^{(n)} (so the n^{th} jump of a is as low as possible). We follow common practice in using high and low for high_{1} and low_{1}. At least near the bottom and top, the position of a set in this hierarchy is strongly connected to rates of growth of functions of its degree. Thus, a well studied theme has been the connection between membership in these classes and structural properties of the corresponding degrees. In particular, one is interested in exploiting the complexity theoretic differences (as, for example, expressed by growth rates or complexity of definition) to distinguish between the corresponding classes of degrees.

At times, specific structural results provide natural examples of differences between such classes of degrees. Otherwise, global results generally combine structural work with coding methods. Some strong global results on the theory and definability using codings are given in Nies, Shore and Slaman [1998]. They show, for example, that a standard model of arithmetic is definable in the r.e. degrees as are all of the degree classes L_{n+1} and H_{n} for n ≥ 1. An excellent recent example of natural differences being deduced from specific structural results is Jockusch, Li and Yang [2004]. They use a sophisticated priority argument to prove a very nice structural result:

Theorem 1.1. (Jockusch, Li and Yang [2004]) For any nonrecursive r.e. w there is an r.e. a ∈ L_{2} such that (a ∨ w) ∈ H_{1}.

They then combine this result with one of Cholak, Groszek and Slaman [2001] to produce an elementary (i.e. first order) difference between the Low_{n} and the Low_{1} r.e. degrees for every n > 1.

Theorem 1.2. (Cholak, Groszek and Slaman [2001]) There is a low nonrecursive r.e. w such that, for any r.e. a ∈ L_{1}, a ∨ w ∈ L_{1}.

Corollary 1.3. For n > 1, L_{n} ≢ L_{1}, i.e. there is a first order difference between the Low_{n} and Low_{1} r.e. degrees in the language of partial orderings. The sentence on which they differ says that ∀w > 0∃a¬∃z(w, a ≤ z). It is true in L_{n}, for every n > 1, but false in L_{1}.

Jockusch, Li and Yang [2004] note that previous results show that L_{n} ≢ L_{2} and L_{n} ≢ L_{1} for n > 2. We cite, for example, results of Shore and Slaman. Shore and Slaman [1993] show that there are a, b and c nonrecursive and r.e. with a ∨ b ∨ c ∈ L_{3} such that, for any nonrecursive r.e. w ≤_{T} a, c ≤_{T} b ∨ w. On the other hand, Shore and Slaman [1990] show that there are no such a, b and c with a ∨ b ∨ c ∈ L_{2}. (Note that the L_{n} are not closed under join and so, in principle, one must phrase these results in the language of partial orders. However, the join of any two degrees a and b both below a fixed c ∈ L_{n} does exist in L_{n} and is the same as their join in the full structure. Thus the desired sentence here asserts that there is a d below which there are a, b and c with the indicated properties.) Jockusch, Li and Yang [2004] refer to Li [2006] for examples of instances of these elementary differences and new results showing that H_{n} ≢ H_{1} for n > 1. They also restate the very natural questions of Li [2003], [2006]:

1. Are there any n ≠ m such that H_{n} ≡ H_{m}?

2. Are there any n ≠ m such that L_{n} ≡ L_{m}?

The purpose of this paper is to point out how the results of Nies, Shore and Slaman [1998] can be used to answer the second question:

Theorem 2.7. For all n > m > 1, L_{n} ≢ L_{m}.

2 Coding to get elementary differences

The essence of the elementary difference between L_{n} and L_{m} for n > m > 1 is that we can definably pick out a class of parameters that provide interpretations of ℕ, the standard model of arithmetic, in which we can control the complexity of sets coded by other parameters in the structure. With the appropriate interpretation of arithmetic, there will be, in L_{n}, (parameters defining) a model M (isomorphic to the standard model ℕ) and a set X coded in the model (by other parameters) such that X^{(m−2)} is not in Σ_{m+1}. On the other hand, every set X so coded in L_{m} will have X^{(m−2)} ∈ Σ_{m+1}. We now review the relevant results from Nies, Shore and Slaman [1998] (hereafter NSS) and explain how they apply in any initial segment (i.e. downward closed subset) I of R that contains L_{1}. (Of course all the L_{n} are such initial segments of R.) We now fix such an I.

We intend to uniformly code models of some finitely axiomatized theory of arithmetic into I. Formally, a scheme for coding objects of a certain type in I is given by a sequence of formulas φ_{0}, …, φ_{k} (in the language of partial orderings) with a common list \overline{p} of parameters and further free variables, as well as a formula ψ(\overline{p}) called the correctness condition. The first formula φ_{0} defines the domain of the interpreted structure and the remaining formulas define its functions and relations. For our purposes, the domain can be taken to be a subset of I and the interpretation of the equality relation can be taken to be equality in I. The formula ψ typically says, at least, that the φ_{i} that are intended to define functions actually do so and that the relations and functions defined by the φ_{i} satisfy various axioms. Precise formulations of these notions can be found in W. Hodges [1993, 5.3] We content ourselves with an example

Example 2.1. A scheme S_{M} for coding models of some finitely axiomatized fragment P A^{−} of Peano arithmetic (in the language L (+, ×)) is given by the formulas

φ_{0}(x, \overline{p}), φ_{1}(x, y, z; \overline{p}), φ_{2}(x, y, z; \overline{p})

and a correctness condition ψ(\overline{p}) which says that φ_{1} and φ_{2} define binary functions on the set \{x : φ_{0}(x; \overline{p})\} which satisfy the finitely many axioms of P A^{−}. In our applications, the axioms ensure that M has a standard part.

The particular scheme that we need here is given by the notion of an effective successor model of arithmetic (Definition 2.8 of NSS). It uses parameters p̄ = ⟨p, q, r, b, l, e_{0}, e_{1}, f_{0}, f_{1}⟩ to which we add t (the top of the model) intended to stand simply for a degree above all those in the p̄ of NSS. We add on t so that in our formulas and discussions we can use join restricted to the degrees below t even though we are working inside I. The domain of the model M(p̄) coded by p̄ is a subset of the (Slaman-Woodin) set G defined by p̄. The set G consists of those x ∈ [ b, r] which are the minimal elements of [b, r] such that q ≤ x ∨ p (Definition 2.4 of NSS). The subset is defined as {x ∈G|x < f_{0} or x < f_{1}}. The operations of arithmetic are defined by formulas using the parameter l as well but their specific form play no role in our considerations other than to note that they too quantify only over degrees below t. The effectiveness of the model consists of the fact that it is generated from its first element, g_{0}, by using the additional parameters e_{0}, e_{1}, f_{0}, f_{1} along with join (below t) and infimum (understood to include the assertion that the greatest lower bound of the degrees to which it is applied exists in the degrees below t):

for each i ∈ ℕ, (g_{2i} ∨ e_{1}) ∧ f_{1} = g_{2i+1}and (g_{2i+1} ∨ e_{0}) ∧ f_{0} = g_{2i+2} (∗)

where g_{i} is the element of G that, under the intended interpretation of arithmetic, corresponds to i ∈ ℕ.

NSS can now be taken to add, to the usual correctness condition of Example 2.1, a scheme saying that t is good via the given coded model M_{0}, i.e. for any M_{1} with t_{1} < t_{0} and any given initial segment of (the ordering of) M_{0} there is a map uniformly defined by specified formulas taking the given initial segment of M_{0} isomorphically onto an initial segment of M_{1}. Now the formula that defines the required maps between initial segments of M_{0} and ones of M_{1} asks for a third coded model M (but without the effectiveness condition (∗)) satisfying various conditions of comparability and incomparability (in the sense of ≤_{T}) between (codes for) numbers in M_{0} and M and between ones in M_{1} and M. Lemma 2.6 (a special case of Theorem 5.1) of NSS states that the required parameters defining M can always be taken to have a low top. Otherwise, it only deals with (Turing) comparability between elements of the different models or with formulas representing arithmetic operations within a single model (which, as we have noted, are all restricted to the degrees below the top of the model). Thus, the formula has the same meaning in I as in R. In particular, Theorems 2.5 and 2.7(i) of NSS say that any M(p̄) satisfying this correctness condition is standard and so this remains true inside I. Moreover, the proofs there show that every standard M(p̄) with low top satisfies this extended correctness condition. From now on, we include this correctness condition in our formula defining a model M from parameters p̄. Theorem 6.1 of NSS shows that there is such a standard model which is nice, i.e. its top t is low and its “numbers” are uniformly recursive in t and uniformly r.e. Thus, in I, we have a definable class of parameters p̄ each of which defines a standard model of arithmetic in I one of which is nice.

We next turn to representing sets in models M with top t ∈ I. The coding (Definition 2.9 of NSS) uses two additional parameters c and d:

Definition 2.2. Let t be the top of a standard model M coded in I and let a ≥ t. A set X ⊆ ω is represented in M below a if there are further parameters c, d ≤ a such that

X = {i : c ≤ g_{i} ∨ d}.

The crucial bound on the complexity of coded sets is given by the proof of Lemma 2.13 of NSS (just note that we are assuming a ≥ t and relativize the argument to a).

Theorem 2.3. If X is represented in M below a then X ∈ Σ_{3}^{A}.

Corollary 2.4. For X represented in a model M below an a ∈ L_{m}, X^{(m−2)} ∈ Σ_{m+1}.

Proof. By the theorem, X ∈ Σ_{3}^{A} and so X^{(m−2)} ∈ Σ_{m+1}^{A} while a ∈ L_{m} implies that Σ_{m+1}^{A} ⊆ Σ_{m+1}. (The hypothesis on a says directly that A^{(m)} ≤_{T} 0^{(m)}. Of course, Σ_{m+1}^{A} consists of the sets r.e. in A^{(m)} which are then r.e. in 0^{(m)} and so in Σ_{m+1}.)

At the other end, Theorem 7.1 of NSS and the fact that there is a nice M, lets us represent all sets allowed by Theorem 2.3.

Theorem 2.5. (Theorem 7.1 of NSS ) If M is a nice model with top t ≤_{T} a ∈ I , then every X ∈ Σ_{3}^{A} can be represented in M below a.

Thus we have our difference between the initial segments L_{n} and L_{m}:

Corollary 2.6. There is a model M with top t ≤_{T} a ∈ L_{n} and an X represented in M below a such that X^{(m−2)} ∉ Σ_{m+1}.

Proof. Let M be a nice model and a be any degree above its low top t. By the theorem, A^{(3)} = X is represented in M below a. If A^{(m+1)} = X^{(m−2)} ∈ Σ_{m+1} then a ∈ L_{m}. (This fact means that (A^{(m)})′ is r.e. in 0^{(m)} and, of course, 0^{(m)} ≤_{T} A^{(m)} and so A^{(m)} ≤_{T} 0^{(m)} by the basic properties of the jump operator Soare [1987, III.2.3].) Thus, we only need to know that above every low t there is an a which is in L_{n} − L_{m}. This follows immediately from, for example, the fact that there is a z ∈ L_{n} − L_{m} (essentially by the Sacks jump theorem [1963] as in Soare [1987, VIII.3.4]) and the Robinson Interpolation Theorem [1971] applied to [t, 0′] and z′ to produce an a ≥ t with a′ = z′ and so a in exactly the same jump classes as z.

As all this takes place inside (coded) standard models, we actually have an elementary difference.

Theorem 2.7. For all n > m > 1, L_{n} ≢ L_{m}.

Proof. Fix n > m > 1. Our desired sentence θ says that there are parameters p̄ which code a standard model M of arithmetic with top t and an a ≥_{T} t with a set X represented in M below a such that M satisfies the (translation of the) sentence of arithmetic that says that X^{(m−2)} is not Σ_{m+1}. (There is clearly a sentence of arithmetic with added predicate for X that says that X^{(m−2)} ∉ Σ_{m+1}. We can talk about X in M as if we had a predicate for it added to the language of arithmetic by replacing i ∈ X by c ≤ g_{i} ∨ d.) This sentence θ is true in L_{n} by Corollary 2.6 but false in L_{m} by Corollary 2.4.

3 Bibliography

Cholak, P., Groszek, M. and Slaman, T. A. [2001], An almost deep degree, J. Symb. Logic, 66, 881–901.

Friedberg, R. M. [1957], Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat. Ac. Sci. 43, 236-238.

Hodges, W. [1993], Model Theory, Cambridge University Press, Cambridge, England. Jouckusch, C. G., jr., Li, A. and Yang, Y. [2004], Trans. Am. Math. Soc. 356,

2557–2568.

Li, A. [2003], Definable relations on the computably enumerable degrees, in Computability and Models, S. B. Cooper and S. S. Goncharov eds., Kluwer Academic/Plenum Publishers, New York, 267-288.

Li, A. [2006], Elementary diferneces among jump hierarchies, preprint.

Muchnik, A. A. [1956], On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR N.S. 108, 29-32.

Nies, A., Shore, R. A. and Slaman, T. [1998], Interpretability and definability in the recursively enumerable degrees, Proc. Lon. Math. Soc. (3) 77, 241-291.

Post, E. L. [1936], Finite combinatory processes – formulation, J. Symb. Logic 1, 103-105.

Post, E. L. [1944], Recursively enumerable sets of positive integers and their decision problems, Bull. Am. Math. Soc. 50, 284-316.

Robinson, R. W. [1971], Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93, 285-314.

Sacks, G. E. [1963], Recursive enumerability and the jump operator, Trans. Am. Math. Soc. 108, 223-239.

Soare, R. I. [1987], Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin. Shore, R. A. [1999], The recursively enumerable degrees, in Handbook of Computaility

Theory, E. R. Griffor ed., Elsevier, Amsterdam, 169-198.

Shore, R. A. and Slaman T. A. [1990], Working below a low_{2} recursively enumerable degree, Archive for Math. Logic 29, 201-211.

Shore, R. A. and Slaman T. A. [1993], Working below a high recursively enumerable degree, J. Symb. Logic 58, 824-859.

Turing, A. M. [1936], On computable numbers, withan application to the Entscheidungsproblem, Proc. Lon. Math. Soc. (2) 42, 230-265.

Turing, A. M. [1939], Systems of logic based on ordinals, Proc. Lon. Math. Soc. (2) 45, 161-228.