Stephen G. Simpson
Department of Mathematics
August 10, 2004
Pennsylvania State University
A principal object of study in recursion theory going back to the seminal work of Turing [36] and Post [25] has been the countable upper semilattice of recursively enumerable Turing degrees, i.e., Turing degrees of recursively enumerable sets of positive integers. See the monographs of Sacks [27], Rogers [26], Soare [35], and Odifreddi [22,23].
A major difficulty or obstacle in the study of has been the lack of natural examples. Although it has long been known that is infinite and structurally rich, to this day no specific, natural examples of recursively enumerable Turing degrees are known, beyond the two examples originally noted by Turing: the Turing degree of the Halting Problem, and the Turing degree of solvable problems. Furthermore, and are respectively the top and bottom elements of . This paucity of examples in is striking, because it is widely recognized that most other branches of mathematics are motivated and nurtured by a rich stock of examples. Clearly it ought to be of interest to somehow overcome this deficiency in the study of .
In 1999 [30,31] we defined a degree structure, here denoted , which is closely related to , but superior to in at least two respects. First, exhibits better structural behavior than , in the sense that is a countable distributive lattice, while is not even a lattice. Second and more importantly, there are plenty of specific, natural degrees in which are intermediate between and , the top and bottom elements of . Thus does not suffer from the above-mentioned lack of examples, which plagues .
In more detail, let be the lattice of weak degrees (a.k.a., Muchnik degrees) of mass problems given by nonempty subsets of . In 1999 [30] we showed that among the intermediate degrees in is the specific degree associated with the set of -random reals. The concept of -randomness was already well known from algorithmic information theory [19]. After 1999, we and other authors [2,3,4,5,32,33,34] continued the study of , using priority arguments to prove structural properties, just as for . In addition, we [33] discovered families of specific, natural, intermediate degrees in related to foundationally interesting topics such as reverse mathematics, Gentzen-style proof theory, and computational complexity. Some additional degrees of this kind are presented in Sections 3 and 4 below.
The purpose of the present paper is to further clarify the relationship between the semilattice and the lattice . Namely, we exhibit a specific, natural embedding which is one-to-one, preserves the semilattice structure of , and carries the top and bottom elements of to the top and bottom elements of . See Theorem 5.5 below. By identifying with its image in , we place the recursively enumerable Turing degrees into a wider context, where natural intermediate degrees occur. We view this as a step toward overcoming the above-mentioned difficulties concerning .
At the same time, our embedding of into fails to solve the long standing open problem of finding a specific, natural, intermediate degree within itself. Indeed, we shall see below (Theorem 5.6) that, regrettably, all of the intermediate degrees belonging to the image of under our embedding are incomparable with all of the known natural intermediate degrees in .
In this section we review some basic information concerning the semilattice and the lattice .
Throughout this paper we shall use standard recursion-theoretic notation from Rogers [26] and Soare [35]. For special aspects of mass problems and sets, a convenient reference is [33].
We write for the set of natural numbers, for the space of total functions from into , and for the space of total functions from into . We sometimes identify a set with its characteristic function given by if , if . For and we write to mean that the Turing machine with Gödel number and oracle and input eventually halts with output . In the absence of an oracle , we write . For we consider recursive functionals given by for some and all and . A function is said to be recursive if there exists such that for all . A set is said to be recursively enumerable if it is the image of a recursive function, i.e., for some recursive .
For we write to mean that is Turing reducible to , i.e., . The Turing degree of , denoted , is the set of all such that , i.e., and . The set of all Turing degrees is partially ordered by putting if and only if . Under this partial ordering, the bottom element of is is recursive. Within , the least upper bound of and is where and for all . A Turing degree is said to be recursively enumerable if where is recursively enumerable. The set of all recursively enumerable Turing degrees is denoted . It is easy to see that is closed under the least upper bound operation inherited from . The top and bottom elements of are and respectively, where is the Turing degree of the Halting Problem, . Thus is a countable upper semilattice with a top and bottom element.
Proof.The least upper bound of and in is
where
Proof.See [33, Theorems 4.7 and 4.10].
Proof.This is immediate from Theorem 2.7.
Proof.If and are subsets of , then so are and . Thus is closed under the least upper bound and greatest lower bound operations inherited from . Clearly is countable, because there are only countably many subsets of . Clearly is the bottom element of . Let be the set of completions of Peano Arithmetic. Identifying sentences with their Gödel numbers, we may view as a subset of . By Scott [29], is the top element of . See also [33, Section 6].
We end this section by mentioning some technical notions and results concerning trees and almost recursiveness.
A finite sequence of natural numbers
is called a
string of length . The set of all strings is denoted
. The set of strings of 's and 's is denoted
. If are strings of length
respectively, then the concatenation
A tree is a set such that, for all , . A path through is an such that . The set of all paths through is denoted . We sometimes identify a string with its Gödel number . A tree is said to be recursive if is recursive.
Proof.See [33, Theorem 4.3].
Proof.See [33, Theorem 4.18].
The following result is known as the Almost Recursive Basis Theorem.
Proof.This is a restatement of the Hyperimmune-Free Basis Theorem of [15, Theorem 2.4]. See also [33, Theorem 4.19].
In this section we identify and characterize some specific, natural degrees in , and we investigate their degree-theoretic properties.
Thus is -random if and only if is random in the sense of Martin-Löf [20], and is -random if and only if is random relative to the Halting Problem. For a thorough treatment of randomness and -randomness, see Kautz [16] or Downey/Hirschfeldt [8]. We write
Proof.It is is well known (see for instance [33, Theorem 8.3]) that is . Relativizing to we see that is -random is , i.e., relative to . Putting , we see that is relative to . From this it follows easily that is .
Proof.First use a Skolem function technique to reduce to the case where
is . Namely, fix a recursive predicate such that
, and
replace by the set of all
such that
holds.
Clearly the latter set is and . Assuming now
that is a subset of , let be a
recursive subtree of
such that is the set of
paths through . We may safely assume that, for all and the length of , . Let be a
recursive subtree of such that is the set of paths
through . Define to be the set of strings
of the form
Proof.By Lemmas 3.2 and 3.3 we can find sets such that and . Since is nonempty and , there is a nonempty set . Then , hence , hence .
Proof.By Lemma 3.4 there are sets such that and . Thus and . Clearly , hence . Clearly has no recursive member, i.e., . By [33, Section 7] or [15, Corollary 5.4], the Turing upward closure of is of measure , i.e., for all of positive measure. In particular , i.e., . Summarizing, we have now shown that .
It remains to show that , i.e., . By Lemma 3.2, let be a nonempty subset of . By the Almost Recursive Basis Theorem 2.15, let be almost recursive. By Kautz [16, Theorem IV.2.4(iv)] or Dobrinen/Simpson [7, Remark 2.8], there is no almost recursive . In particular, there is no such that . Suppose there were such that . By Theorem 2.14 let be a total recursive functional such that . Put . We have , hence , hence is nonempty. Since and are , it follows by [33, Theorem 4.4] that is . Hence, by [33, Lemma 8.8], is of positive measure. Since , it follows that the Turing upward closure of is of positive measure, but this is a contradiction. We have now shown that, for a particular , there is no such that . Thus , and this completes the proof.
Proof.The first statement is [33, Theorem 8.10]. For the second statement, assume that is a subset of whose Turing upward closure is of positive measure. A computation in the style of Tarski and Kuratowski (compare Rogers [26, Section 14.3]) shows that is . Since is of positive measure, let be of positive measure. By Kautz [16, Lemma II.1.4(ii)] or Dobrinen/Simpson [7, Theorem 3.3], we may assume that is relative to . Relativizing [33, Lemma 8.7] to , we have . Since , it follows that , hence . Furthermore, since is a nonempty subset of , we have . We now see that , i.e., . On the other hand, by Theorem 3.6 let be a subset of such that . Note that , hence is of positive measure. We have now shown that is the maximum such that is of positive measure. This completes the proof of our theorem.
Proof.If then trivially , hence is of measure . Conversely, if is of positive measure, then by Theorem 3.8 we have .
Proof.By Theorem 3.6 let be such that . By Theorem 3.8, is of positive measure. If there were a set of positive measure, then by Theorem 3.8 we would have , contradicting Theorem 3.6.
Proof.The first statement is [33, Theorem 8.12, part 3]. For the second statement, let be nonempty subsets of with and . Trivially . Moreover , hence is of positive measure if and only if at least one of and is of positive measure. By Corollary 3.9 this means that if and only if at least one of and .
Proof.This is a special case of [33, Theorem 7.5].
Proof.Assume . By the definition of , we have , hence . Since is separating and , Theorem 3.13 tells us that , hence .
Proof.This follows from Theorem 3.11 and Corollary 3.14.
In this section we identify some additional specific, natural, intermediate degrees in related to diagonal nonrecursiveness.
Proof.Put is diagonally nonrecursive. Obviously is a nonempty subset of . By Lemma 3.3 we can find a nonempty set such that . But , hence . We now see that .
Proof.By Theorem 3.6 we have . Clearly has no recursive member, i.e., . By Giusto/Simpson [11, Lemma 6.18], for all there exists such that . Thus we have . It remains to show that . By Kumabe [18] there is a diagonally nonrecursive function which is of minimal Turing degree. But if is -random, then is not of minimal Turing degree, because the functions and defined by are Turing incomparable (see for instance van Lambalgen [37]). This proves . An alternative reference for the conclusion is Ambos-Spies et al [1, Theorems 1.4 and 2.1].
Proof.A Tarski/Kuratowski computation shows that is . Let be as in the proof of Theorem 4.2. By Lemma 3.3 we can find a nonempty set such that . Thus . By Ambos-Spies et al [1, Theorems 1.4, 1.8, 1.9] we have , and the rest is from Theorem 4.3.
In this section we exhibit a specific, natural embedding of the countable upper semilattice into the countable distributive lattice .
Proof.The first statement is the special case of Lemma 3.3 with and . For the second statement, note that for any and we have , and implies . In particular this holds when and are singletons and .
Proof.The first statement is a special case of Lemma 5.2, because if and only if is (see Kleene [17, Theorem XI, page 293]), which implies that is a singleton. It is easy to see that . To show that , by Kleene [17, Theorem 38*, pages 401-402] let be . Then and , hence .
Proof.Let be such that and . We must show that if and only if . The ``only if'' part is trivial. For the ``if'' part, suppose . In particular, . If , then , hence , hence by the Arslanov Completeness Criterion [12], hence , a contradiction. Thus . This proves our lemma.
We now obtain our main result.
Proof.This result is obtained by combining Lemmas 5.3 and 5.4.
Proof.By the Arslanov Completeness Criterion [12] we have . It remains to show that . This is obvious, because for any nonrecursive we have [27, §10, Theorem 1].
We finish by noting some generalizations of Theorem 5.5.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 extre
The translation was initiated by Stephen G Simpson on 2008-04-28