# Mass Problems and Randomness

Stephen G. Simpson

Department of Mathematics

Draft: October 27, 2004

Pennsylvania State University

This research was partially supported by NSF grant DMS-0070718. I would like to thank Stephen Binns for discussing these topics with me.

AMS 2000 Subject Classifications: 03D30, 03D80, 03D25, 03F35, 03F15, 68Q30, 68Q15.

Bulletin of Symbolic Logic, 11, 2005, pp. 1-27.

### Abstract:

A mass problem is a set of Turing oracles. If and are mass problems, we say that is weakly reducible to if every member of Turing computes a member of . We say that is strongly reducible to if every member of Turing computes a member of via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We focus on the countable distributive lattices and of weak and strong degrees of mass problems given by nonempty subsets of . Using an abstract Gödel/Rosser incompleteness property, we characterize the subsets of whose associated mass problems are of top degree in and , respectively. Let be the set of Turing oracles which are random in the sense of Martin-Løf, and let be the weak degree of . We show that is a natural intermediate degree within . Namely, we characterize as the unique largest weak degree of a subset of of positive measure. Within we show that is meet irreducible, does not join to , and is incomparable with all weak degrees of nonempty thin perfect subsets of . In addition, we present other natural examples of intermediate degrees in . We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory.

# Introduction

Among the principal objects of study in recursion theory going back to the seminal work of Turing [59] and Post [44] have been the upper semilattice of all Turing degrees, i.e., degrees of unsolvability, and its countable sub-semilattice consisting of the recursively enumerable Turing degrees, i.e., the Turing degrees of recursively enumerable sets of positive integers. See for instance Sacks [46], Rogers [45], Lerman [36], Soare [56], Odifreddi [42,43].

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 original examples 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 lack of natural examples, although well known and a major source of frustration, has almost never been discussed in print, but see Rogers [45, Section 9.6]. In any case, the paucity of examples in is striking, because it is well known that most other branches of mathematics are motivated and nurtured by a rich stock of natural examples. Clearly it ought to be of interest to somehow overcome this deficiency in the study of .

In recent years it has emerged that there are some natural, important, well-behaved degree structures, closely related to but different from , which do not suffer from the above mentioned deficiency. Simpson 1999 [50,51,54] called attention to the countable distributive lattices and of weak and strong degrees of mass problems given by nonempty subsets of , and noted the existence of specific, natural degrees which are intermediate between the top and bottom elements of and . One of the natural intermediate degrees noted by Simpson was the weak degree of the set of Turing oracles which are random in the sense of Martin-Løf [39]. The study of and has been continued by Simpson [53,49], Cenzer/Hinman [9], Simpson/Slaman [55], Binns [3,4,5], Binns/Simpson [6], Terwijn [58].

The purpose of the present paper is to elucidate additional properties of previously noted natural degrees in and , and to present some additional natural degrees in . Along the way we give a somewhat leisurely introduction to mass problems in general, and to and in particular, and we review other known results concerning and .

In a later paper [48] we shall exhibit a natural embedding of the countable upper semilattice into the countable distributive lattice . This embedding will be one-to-one and will preserve the top and bottom elements as well as the partial order relation and least upper bound operation from . In this way we shall see that provides a satisfactory solution to several of the well known difficulties concerning .

# Recursion-theoretic preliminaries

In this section we establish notation concerning recursive functionals and Turing degrees.

Throughout this paper we use standard recursion-theoretic notation and concepts from Rogers [45] and Soare [56]. We write for the set of natural numbers. We write for the space of total functions from into . We write for the subspace of consisting of the 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 . Furthermore, means that is defined, i.e., , and means that is undefined, i.e., . In the absence of an oracle , we write simply , etc. For we consider recursive functionals given by for some and all and . In particular, a function is said to be recursive or computable if there exists such that for all . (The terms recursive'' and computable'' are synonymous.) 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. It is known that has no top element. Within , the least upper bound of and is given as where and for all . The standard, natural example of a Turing degree is given by the Turing jump operator, , where is (the characteristic function of) the Halting Problem relative to , . A Turing degree is said to be recursively enumerable if it is where is the characteristic function of a recursively enumerable set . The set of all recursively enumerable Turing degrees is denoted . Clearly is countable, because there are only countably many recursively enumerable sets. It is known that is closed under the least upper bound operation inherited from , and that and are the top and bottom elements of . Thus is a countable upper semilattice with a top and bottom element.

# Mass problems

A mass problem is a subset of . The underlying idea here is to view a set as a problem'' with a solution'' that does not necessarily exist and is not necessarily unique. The solutions'' of are simply the members of . In the special case when is a singleton set, the solution'' exists and is unique, and the mass problem corresponds to a Turing degree.

In accordance with the conceptual scheme which was explained in the previous paragraph, one makes the following definitions.

Definition 3.1   Let and be subsets of . We say that is weakly reducible to , written , if for all there exists such that . Conceptually this means that, given any solution'' of the mass problem , we can use it as an oracle to compute a solution'' of the mass problem . The weak degree of , written , is the set of all such that , i.e., and . The set of all weak degrees is partially ordered by putting if and only if .

Remark 3.2   The concept of weak reducibility goes back to Muchnik [41] and has sometimes been called Muchnik reducibility.

Definition 3.3   We say that is strongly reducible to , written , if there exists such that for all there exists such that for all . In other words, if and only if there exists a recursive functional . Note that strong reducibility is the uniform variant of weak reducibility. Just as for weak degrees, the strong degree of , written , is the set of all such that , i.e., and . The set of all strong degrees is partially ordered by putting if and only if .

Remark 3.4   The concept of strong reducibility goes back to Medvedev [40] and has sometimes been called Medvedev reducibility.

Remark 3.5   Given , a recursive homeomorphism of onto is a recursive functional mapping one-to-one onto such that the inverse functional is also recursive. In this case we say that and are recursively homeomorphic. In addition, let us say that is Turing degree isomorphic to if . Clearly recursive homeomorphism of and implies strong equivalence and Turing degree isomorphism, either of which implies weak equivalence. No other implications hold.

Theorem 3.6   and are distributive lattices. They have a bottom element, denoted , and a top element, denoted .

Remark 3.7   There are obvious, natural embeddings of into and given by and respectively. Here is the singleton set whose only member is . These embeddings are one-to-one and preserve and the partial order relation and least upper bound operation from .

Remark 3.8   There is an obvious lattice homomorphism of onto given by .

Remark 3.9   is canonically isomorphic to the lattice of upward closed subsets of under the set-theoretic operations of intersection and union. Namely, for each , the weak degree gets mapped to the upward closure of within . It follows that is a complete distributive lattice. We do not know of an analogous set-theoretic representation of .

Remark 3.10   For a survey of general mass problems, see Sorbi [57].

# Recursively bounded sets

In this section we present some well known generalities concerning recursively bounded sets and almost recursive functions. The reader is advised to skip most of this section now, and refer to it later as needed.

Definition 4.1   A predicate is said to be recursive if
if , and if . A set is said to be if there exists a recursive predicate such that .

Definition 4.2   A finite sequence of natural numbers is called a string of length . We write . The set of all strings is denoted . If are strings of length respectively, then the concatenation

is a string of length . Note that if and only if for some , and this implies . If is a string of length , then for all we have defined by for , for . Note that if and only if for some . 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, and if is .

Theorem 4.3   is if and only if for some recursive tree .

Theorem 4.4   If are and is a recursive functional, then the preimage is .

Definition 4.5   A set is said to be recursively bounded if there exists a recursive function such that for all and .

Remark 4.6   Any subset of a recursively bounded set is recursively bounded. We shall be concerned with subsets of which are recursively bounded and . In particular, is recursively bounded and , and we are especially interested in subsets of . As in Theorem 4.3, is a subset of if and only if for some recursive tree . Here denotes the set of all strings of 's and 's. See also Theorem 4.10 and Corollary 4.11 below.

Theorem 4.7   Assume that is recursively bounded , and assume that is a recursive functional. Then the image is recursively bounded . Moreover, there exists a total recursive functional such that extends , i.e., for all .

Definition 4.8   In general, suppose that to each we have effectively associated a finite sequence of ordered pairs where and for each . Define a recursive functional by putting where is minimal such that , or if no such exists. Then is called a truth table functional. For we say that is truth table reducible to , written , if there exists a truth table functional such that . Rogers [45, Chapter 8 and Section 9.6] provides general background on truth table reducibility.

Corollary 4.9   Assume that is recursively bounded , and assume that is a recursive functional. Then can be extended to a truth table functional. In particular, for all .

Theorem 4.10   Let be a recursively bounded set. Then is recursively homeomorphic to a subset of .

Corollary 4.11   The weak (strong) degrees of nonempty recursively bounded sets are the same as the weak (strong) degrees of nonempty subsets of .

Definition 4.12   Given , put

the set of extendible nodes of . Note that is a tree, and is the topological closure of in . In particular, if is , then .

Lemma 4.13   Let be a recursively bounded set. Then is .

Definition 4.14   For , an isolated point of is an such that, for some string , is the unique such that . We say that is perfect if has no isolated points.

Theorem 4.15   Let be a recursively bounded set. If is an isolated point of , then is recursive.

Corollary 4.16   Let be a recursively bounded set. If the weak or strong degree of is , then is perfect.

Definition 4.17   We say that is almost recursive if for all there exists such that and is recursive. (Turing degrees which contain almost recursive functions have been known in the literature as hyperimmune-free Turing degrees.)

Theorem 4.18   Suppose is almost recursive. Then for all we have , i.e., is truth table reducible to . In particular, for some total recursive functional .

We end this section with the Almost Recursive Basis Theorem.

Theorem 4.19   If is nonempty, recursively bounded, and , then there exists such that is almost recursive.

# The lattices and

In this section we introduce the lattices and which are the focus of this paper.

Remark 5.1   There is a large recursion-theoretic literature concerning Turing degrees of members of subsets of , and especially Turing degrees of members of recursively bounded subsets of . See for instance the classic paper of Jockusch and Soare [26] and the survey article by Cenzer and Remmel [10]. Mindful of this literature, we find it natural to view nonempty recursively bounded sets as mass problems.

By Theorem 4.10 and Corollary 4.11, it suffices to consider subsets of .

Definition 5.2   () is the set of weak (strong) degrees of nonempty recursively bounded sets. By Corollary 4.11, () is the same as the set of weak (strong) degrees of nonempty subsets of .

Theorem 5.3   and are countable distributive lattices with a top and bottom element, denoted and respectively.

Remark 5.4   There is an obvious lattice homomorphism of onto given by . Simpson and Slaman [55] have shown that every nonzero weak degree in contains infinitely many strong degrees in .

Remark 5.5   In the context of recursively bounded sets, there is reason to view weak reducibility as the mass problem analog of Turing reducibility, while strong reducibility is the mass problem analog of truth table reducibility. See Rogers [45, Sections 8.3 and 9.6] and Simpson [54, Remark 3.12]. Namely, if is recursively bounded and , then by Corollary 4.9 the recursive functional is given by truth tables, hence for each there exists such that , i.e., is truth table reducible to . Thus we see that is analogous to , the recursively enumerable Turing degrees, while is more closely analogous to , the recursively enumerable truth table degrees.

Remark 5.6   It is known that the countable distributive lattices and are structurally rich. Binns/Simpson [3,6] have shown that every countable distributive lattice is lattice embeddable in every nontrivial initial segment of . A similar conjecture for remains open, although partial results in this direction are known. Binns [3,4] has obtained the and analogs of the Sacks Splitting Theorem. Namely, for all in there exist in such that , and similarly for . Cenzer/Hinman [9] have obtained the analog of the Sacks Density Theorem. Namely, for all in there exists in such that . A similar conjecture for remains open. Binns [3,4] has improved the result of Cenzer/Hinman [9] by showing that for all in there exist in such that . These structural results for and are proved by means of priority arguments. They invite comparison with the older, known results for recursively enumerable Turing degrees, which were also proved by priority arguments.

# Weak and strong completeness

In this section we obtain additional information concerning sets which are of weak or strong degree in or , respectively. We show that, if is a nonempty recursively bounded set, then if and only if is Turing degree isomorphic to , and if and only if is recursively homeomorphic to .

By Theorem 4.10 and Corollary 4.11, it suffices to consider subsets of .

Definition 6.1   Let be a nonempty recursively bounded set. is weakly complete if , i.e., for all nonempty sets . is strongly complete if , i.e., for all nonempty sets . These notions have sometimes been referred to as Muchnik completeness and Medvedev completeness, respectively.

Remark 6.2   We have seen in the proof of Theorem 5.3 that is strongly complete, hence weakly complete. In addition, there are natural examples of recursively bounded sets which are weakly complete but not strongly complete. See Definition 7.9 and Remark 7.10 below.

Theorem 6.3   Let and be nonempty subsets of .
1. If and are strongly complete, then is recursively homeomorphic to .
2. If is strongly complete, then we can find a recursive functional which is onto , i.e., .
3. is strongly complete if and only if is productive, i.e., given an index of a nonempty set we can effectively find a canonically indexed clopen set such that both and are nonempty.

Corollary 6.4   Let be a nonempty recursively bounded set. If is strongly complete, then the set of Turing degrees of members of is upward closed.

Corollary 6.5   Let be a nonempty recursively bounded set. Then is strongly complete if and only if is recursively homeomorphic to .

The next corollary is originally due to Robert M. Solovay.

Corollary 6.6   The set of Turing degrees of members of is upward closed.

Remark 6.7   Instead of Peano Arithmetic, we could have used any consistent recursively axiomatizable theory which is effectively essentially incomplete, i.e., has the property given by the Gödel/Rosser Theorem. The required property of is as follows. Given a consistent recursively axiomatizable theory extending , we can effectively find a sentence in the language of which is independent of , i.e., and . Compare this with our notion of productivity from part 3 of Theorem 6.3, which may be viewed as an abstract Gödel/Rosser property for subsets of .

Theorem 6.8   Let be a nonempty recursively bounded set. Then is weakly complete if and only if is Turing degree isomorphic to .

Corollary 6.9   Let and be nonempty recursively bounded sets. If and are weakly complete, then is Turing degree isomorphic to .

We can now strengthen Corollary 6.4 as follows.

Corollary 6.10   Let be a nonempty recursively bounded set. If is weakly complete, then the set of Turing degrees of members of is upward closed.

# sets of positive measure

Definition 7.1   The fair coin probability measure on is defined by

for all and . A set is said to be of positive measure if .

In this section we prove a non-helping'' theorem for weak and strong degrees of subsets of which are of positive measure.

Lemma 7.2   Let , be a sequence of finite subsets of of bounded cardinality. Put
.
Let be of positive measure. Let be arbitrary. If , then .

Lemma 7.3   Same as Lemma 7.2 with strong reducibility, , replaced by weak reducibility, .

Definition 7.4   For we say that separates if for all , and for all . A nonempty set is said to be separating if there exist recursively enumerable sets such that separates . In this case we say that the weak degree and the strong degree are separating.

Theorem 7.5   Let be subsets of . Assume that is separating and that is of positive measure. Let be the weak degrees of respectively. If , then . The same holds for strong degrees.

Corollary 7.6   Let and be nonempty subsets of . Assume that is of positive measure. Let be the weak degrees of respectively. If , then . The same holds for strong degrees.

Corollary 7.7   Let be a subset of of positive measure. Let be the weak degree of . Then . The same holds for strong degrees.

Remark 7.8   In [48] we shall give an example of a set whose Turing upward closure is of positive measure yet does not contain any set of positive measure.

Definition 7.9   Following Jockusch [25], for we define
and . Thus is the set of -bounded, diagonally nonrecursive functions. Note that is recursively bounded and .

Remark 7.10   By Jockusch [25, Theorem 5] each is weakly complete, i.e., of weak degree . Let be the strong degree of . It is well known (see also the proof of Corollary 7.6 above) that is strongly complete, i.e., in . By Jockusch [25, Theorem 6] we have

We have the following new result.

Corollary 7.11   Let and be subsets of . Assume that is of positive measure. Let be the strong degrees of respectively. For each , if , then . In particular we have
.

Remark 7.12   In Corollary 7.11, we do not know whether it is necessarily the case that , or for all .

# sets of random reals

In this section we exhibit a particular degree and note some of its degree-theoretic properties.

As in Section 7, let denote the fair coin probability measure on .

Definition 8.1   An effective null is a set of the form where is a recursive sequence of subsets of with for all . A point is said to be random if for all effective null sets .

Remark 8.2   The notion of randomness in Definition 8.1 is due to Martin-Løf [39] and has been studied extensively. It appears to be the most general and natural notion of algorithmic randomness for infinite sequences of 's and 's. It has also been called Martin-Løf randomness (Li/Vitányi [37, Section 2.5]), 1-randomness (Kurtz [28], Kautz [27]), and the NAP property (Kucera [29,30,31,32,33,34,35]). It is closely related to Kolmogorov complexity (see Li/Vitányi [37]).

The following theorem is well known. It says that the union of all effective null sets is an effective null set.

Theorem 8.3   is not random is an effective null set.

Corollary 8.4   There exists a nonempty set
is random.

Notation 8.5   We use the following notation for shifts: . Note that is a mapping of into .

Lemma 8.6   For all and , is random if and only if is random.

The next lemma is an effective version of the Zero-One Law of probability theory.

Lemma 8.7   Let be random. Let be with . Then .

Lemma 8.8   Let be random. Then for all sets , if then .

Lemma 8.9   Let and be as in Corollary 8.4. Then , and .

Theorem 8.10   Let where is random. Then can be characterized as the unique largest weak degree of a set such that .

Remark 8.11   Theorem 8.10 tells us that, among all weak degrees of sets of positive measure, there exists a unique largest degree. Simpson/Slaman [55] and independently Terwijn [58] have shown that, among all strong degrees of sets of positive measure, there is no largest or even maximal degree.

We end this section by noting some additional properties of the particular weak degree which was defined in Theorem 8.10.

Theorem 8.12   Let be the weak degree of is random. Then:
1. , and .
2. For all , if then .
3. For all , if then either or .
4. There is no separating such that .

Corollary 8.13   The weak degree is meet irreducible and does not join to in .

# Thin subsets of

In this section we discuss an interesting class of degrees in , each of which is incomparable with the particular degree of Section 8.

We begin with some generalities concerning thin sets.

Definition 9.1   A set is said to be thin if, for all sets , the set-theoretic difference is .

Lemma 9.2   Let be a recursively bounded set. Then is thin if and only if all subsets of are trivial, i.e., they are of the form
or or
for some finite set of strings .

Theorem 9.3   Let be a nonempty thin recursively bounded set. Then is isolated if and only if is recursive. In particular, is perfect if and only if and only if has no recursive members, i.e., .

Lemma 9.4   Let be a thin recursively bounded set. Then:
1. Every subset of is thin and recursively bounded.
2. Let be the image of under a recursive functional . Then is a thin recursively bounded set.

Theorem 9.5   If is a thin recursively bounded set, then is recursively homeomorphic to a thin set . Moreover, is perfect if and only if is perfect.

Remark 9.6   There is a large literature on thin perfect subsets of going back to Martin/Pour-El [38]. See Downey/Jockusch/Stob [15,16] and Cholak et al [11]. Typically, thin perfect subsets of are constructed by means of priority arguments. In this sense, thin perfect subsets of and their weak and strong degrees are artificial or unnatural. In particular, thin perfect subsets of have been used by Binns/Simpson [6] to embed countable distributive lattices into and .

Remark 9.7   Let where is any nonempty thin perfect recursively bounded set. Obviously . Let where is random. We have seen in Theorem 8.10 that . Our goal in this section is to prove Theorem 9.15, which says that and are incomparable, i.e., and . By Theorem 9.5, it suffices to prove this in the special case when is a nonempty thin perfect subset of .

Lemma 9.8   Let be a thin subset of . Then .

Remark 9.9   We do not know the answer to the following question. If is a thin perfect subset of , does it follow that the Turing upward closure is of measure 0?

Lemma 9.10   Let be a nonempty thin subset of . If is random, and if is almost recursive, then . In particular, .

Lemma 9.11   Let be random. If is nonrecursive, then there exists such that and is random.

Lemma 9.12   Let be random and almost recursive. If is nonrecursive, then there exists such that and is random.

Lemma 9.13   Let be a nonempty thin perfect subset of . If , and if is random and almost recursive, then . In particular , and for all sets of positive measure.

Summarizing, we have:

Lemma 9.14   Let be almost recursive. Assume that is random, and assume that where is a thin perfect subset of . Then and , i.e., the Turing degrees of and are incomparable.

Theorem 9.15   Let where is a nonempty thin perfect subset of . Let where is random. Then and are incomparable weak degrees in .

Corollary 9.16   There exist in such that is separating and is not separating. Indeed, every separating which is is .

# Some additional natural examples in

In this section we present some additional natural examples in , including a hierarchy of weak degrees in corresponding to the transfinite Ackermann hierarchy from proof theory.

Definition 10.1   Put , the set of diagonally nonrecursive functions. The set of Turing degrees of members of has been studied by Jockusch [25]. Note that is nonempty and . If is a recursive function such that for all , put , the set of -bounded functions. In addition, put is recursive, the set of recursively bounded functions.

Remark 10.2   Trivially

hence , hence . According to Ambos-Spies et al [2, Theorems 1.8 and 1.9], we have strict inequalities

As in Section 8, let be the set of random reals. An argument of Kurtz (see Jockusch [25, Proposition 3]) shows that provided is such that , for example .

Remark 10.3   Since is nonempty, recursively bounded, and , we have and . Although and are not recursively bounded, it will be shown in Simpson [48] that and . We do not know whether , or whether . Put , , , . Summarizing, we have the following result.

Theorem 10.4   In we have

for all sufficiently fast-growing recursive functions .

Remark 10.5   Some of our natural weak degrees are closely related to certain formal systems which arise naturally in the foundations of mathematics. Namely, the weak degrees , , correspond to the systems , , respectively. Each of these subsystems of second order arithmetic is of interest in connection with the well known foundational program of reverse mathematics. See Simpson [52, Chapter IV and Section X.1], Yu/Simpson [61], Brown/Giusto/Simpson [7], and Giusto/Simpson [23]. The standard reference for reverse mathematics is Simpson [52].

Remark 10.6   From the recursion-theoretic viewpoint, there are some subtle issues concerning naturalness of the mass problems , , and of their weak degrees , , . First, , , are not invariant under recursive permutations of , and on this basis it is possible to question their recursion-theoretic naturalness. (See also the discussion of the recursion-theoretic Erlanger Programm in Rogers [45, Chapter 4].) On the other hand, this objection clearly does not apply to the weak degrees , , , because all weak and strong degrees are invariant under recursive permutations of . Second, one may note that our definitions of , , and their weak degrees , , depend upon a particular choice of Gödel numbering of Turing machines, because the function is defined in terms of such a Gödel numbering. (See also the discussion of acceptable Gödel numberings in Rogers [45].) We shall now present a method of overcoming this objection. Our idea is to replace the particular partial recursive function by an arbitrary partial recursive function . This will answer the objection, because the extensional concept partial recursive function'' is independent of the choice of Gödel numbering.

Definition 10.7   Let be the set of such that for all partial recursive functions there exists such that . Let be the set of such that for all partial recursive functions there exists such that and for some recursive function .

Remark 10.8   Using the S-m-n Theorem, it is easy to see that and . (See also the proof of Theorem 10.10 below.) Thus the weak degrees and are natural in the sense that they can be defined in a way that does not depend on the choice of Gödel numbering. What about where is a fixed recursive function? Let be the set of such that for all partial recursive functions there exists such that and . It is not clear that for a fixed recursive function , but we have the following definition and theorem for classes of recursive functions.

Definition 10.9   If is a class of recursive functions, put . Let be the set of such that for all partial recursive functions there exists such that and for some .

Theorem 10.10   If is closed under composition with primitive recursive functions, then . If there exists a uniform recursive enumeration of , then .

Theorem 10.11   Let be a subset of . Then we can find a set such that is Turing degree isomorphic to .

Remark 10.12   In the proof of Theorem 10.11, note that , where and . Thus the proof shows that is closed under effective infima.

Remark 10.13   If is a class of recursive functions satisfying the hypotheses of Theorem 10.10, put . We have seen that and that is natural in the sense that it can be defined in a way which does not depend on the choice of Gödel numbering. Moreover, if is another such class, then , and according to Ambos-Spies et al [2, Theorem 1.9] we have strict inequality provided contains a function which grows much faster than'' all functions in . There are many examples and problems here.

Example 10.14   For each constructive ordinal , let be the class of recursive functions obtained at levels of the transfinite Ackermann hierarchy. (See for instance Wainer [60].) Thus is the class of primitive recursive functions, is the class of functions which are primitive recursive relative to the Ackermann function, etc. Putting we have a transfinite descending sequence

in . Moreover, if is a limit ordinal, then . Thus we see a rich set of natural degrees in which are related to subrecursive hierarchies of the kind that arise in Gentzen-style proof theory.

Remark 10.15   Let us assume that we are using one of the standard Gödel numberings of Turing machines which appear in the literature. Then the function in the proof of Theorem 10.10 can be chosen to be bounded by a linear function. Therefore, instead of assuming that is closed under composition with primitive recursive functions, we could assume merely that for all and there exists such that for all . In particular, we can take to be various well known computational complexity classes such as PTIME, EXPTIME, etc. For each such class, Theorem 10.10 shows that the weak degree is natural in that its definition does not depend on the choice of a standard Gödel numbering.

Example 10.16   In we have

etc. Thus we see a rich set of natural degrees in which are related to computational complexity.

## Bibliography

1
K. Ambos-Spies, G. H. Müller, and G. E. Sacks, editors.
Recursion Theory Week.
Number 1432 in Lecture Notes in Mathematics. Springer-Verlag, 1990.
IX + 393 pages.

2
Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman.
Comparing DNR and WWKL.
Journal of Symbolic Logic, 69:1089-1104, 2004.

3
Stephen Binns.
The Medvedev and Muchnik Lattices of Classes.
PhD thesis, Pennsylvania State University, August 2003.
VII + 80 pages.

4
Stephen Binns.
A splitting theorem for the Medvedev and Muchnik lattices.
Mathematical Logic Quarterly, 49:327-335, 2003.

5
Stephen Binns.
Small classes.
Archive for Mathematical Logic, 45:393-410, 2006.

6
Stephen Binns and Stephen G. Simpson.
Embeddings into the Medvedev and Muchnik lattices of classes.
Archive for Mathematical Logic, 43:399-414, 2004.

7
Douglas K. Brown, Mariagnese Giusto, and Stephen G. Simpson.
Vitali's theorem and WWKL.
Archive for Mathematical Logic, 41:191-206, 2002.

8
P. Bruscoli and A. Guglielmi, editors.
Summer School and Workshop on Proof Theory, Computation and Complexity, Dresden, 2003.
Electronic Notes in Theoretical Computer Science. Elsevier, 2004.
To appear.

9
Douglas Cenzer and Peter G. Hinman.
Density of the Medvedev lattice of classes.
Archive for Mathematical Logic, 42:583-600, 2003.

10
Douglas Cenzer and Jeffrey B. Remmel.
classes in mathematics.
In [20], pages 623-821, 1998.

11
Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann.
Automorphisms of the lattice of classes; perfect thin classes and ANC degrees.
Transactions of the American Mathematical Society, 353:4899-4924, 2001.

12
COMP-THY e-mail list.
http://listserv.nd.edu/archives/comp-thy.html, September 1995 to the present.

13
S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors.
Computability, Enumerability, Unsolvability: Directions in Recursion Theory.
Number 224 in London Mathematical Society Lecture Notes. Cambridge University Press, 1996.
VII + 347 pages.

14
Oswald Demuth.
A notion of semigenericity.
Commentationes Mathematicae Universitatis Carolinae, 28:71-84, 1987.

15
Rodney G. Downey, Carl G. Jockusch, Jr., and Michael Stob.
Array nonrecursive sets and multiple permitting arguments.
In [1], pages 141-174, 1990.

16
Rodney G. Downey, Carl G. Jockusch, Jr., and Michael Stob.
Array nonrecursive degrees and genericity.
In [13], pages 93-105, 1996.

17
F. R. Drake and J. K. Truss, editors.
Logic Colloquium '86.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1988.
X + 342 pages.

18
H.-D. Ebbinghaus, J. Fernandez-Prida, M. Garrido, D. Lascar, and M. Rodriguez Artalejo, editors.
Logic Colloquium '87.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1989.
X + 375 pages.

19
H.-D. Ebbinghaus, G. H. Müller, and G. E. Sacks, editors.
Recursion Theory Week.
Number 1141 in Lecture Notes in Mathematics. Springer-Verlag, 1985.
IX + 418 pages.

20
Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors.
Handbook of Recursive Mathematics.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1998.
Volumes 1 and 2, XLVI + 1372 pages.

21
J.-E. Fenstad, I. T. Frolov, and R. Hilpinen, editors.
Logic, Methodology and Philosophy of Science VIII.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1989.
XVII + 702 pages.

22
FOM e-mail list.
http://www.cs.nyu.edu/mailman/listinfo/fom/, September 1997 to the present.

23
Mariagnese Giusto and Stephen G. Simpson.
Located sets and reverse mathematics.
Journal of Symbolic Logic, 65:1451-1480, 2000.

24
J. Gruska, B. Rovan, and J. Wiedermann, editors.
Mathematical Foundations of Computer Science.
Number 233 in Lecture Notes in Computer Science. Springer-Verlag, 1986.
IX + 650 pages.

25
Carl G. Jockusch, Jr.
Degrees of functions with no fixed points.
In [21], pages 191-201, 1989.

26
Carl G. Jockusch, Jr. and Robert I. Soare.
classes and degrees of theories.
Transactions of the American Mathematical Society, 173:35-56, 1972.

27
Steven M. Kautz.
Degrees of Random Sets.
PhD thesis, Cornell University, 1991.
X + 89 pages.

28
Stuart A. Kurtz.
Randomness and Genericity in the Degrees of Unsolvability.
PhD thesis, University of Illinois at Urbana-Champaign, 1981.
VII + 131 pages.

29
Antonín Kucera.
Measure, classes and complete extensions of PA.
In [19], pages 245-259, 1985.

30
Antonín Kucera.
An alternative, priority-free, solution to Post's problem.
In [24], pages 493-500, 1986.

31
Antonín Kucera.
On the role of in recursion theory.
In [17], pages 133-141, 1988.

32
Antonín Kucera.
On the use of diagonally nonrecursive functions.
In [18], pages 219-239, 1989.

33
Antonín Kucera.
Randomness and generalizations of fixed point free functions.
In [1], pages 245-254, 1990.

34
Antonín Kucera.
On relative randomness.
Annals of Pure and Applied Logic, 63:61-67, 1993.

35
Antonín Kucera and Sebastiaan A. Terwijn.
Lowness for the class of random sets.
Journal of Symbolic Logic, 64:1396-1402, 1999.

36
Manuel Lerman.
Degrees of Unsolvability.
Perspectives in Mathematical Logic. Springer-Verlag, 1983.
XIII + 307 pages.

37
Ming Li and Paul Vitányi.
An Introduction to Kolmogorov Complexity and its Applications.
Graduate Texts in Computer Science. Springer-Verlag, 2nd edition, 1997.
XX + 637 pages.

38
Donald A. Martin and Marian B. Pour-El.
Axiomatizable theories with few axiomatizable extensions.
Journal of Symbolic Logic, 35:205-209, 1970.

39
Per Martin-Löf.
The definition of random sequences.
Information and Control, 9:602-619, 1966.

40
Yuri T. Medvedev.
Degrees of difficulty of mass problems.
In Russian.

41
A. A. Muchnik.
On strong and weak reducibilities of algorithmic problems.
Sibirskii Matematicheskii Zhurnal, 4:1328-1341, 1963.
In Russian.

42
Piergiorgio Odifreddi.
Classical Recursion Theory.
Number 125 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1989.
XVII + 668 pages.

43
Piergiorgio Odifreddi.
Classical Recursion Theory, Volume 2.
Number 143 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1999.
XVI + 949 pages.

44
Emil L. Post.
Recursively enumerable sets of positive integers and their decision problems.
Bulletin of the American Mathematical Society, 50:284-316, 1944.

45
Hartley Rogers, Jr.
Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967.
XIX + 482 pages.

46
Gerald E. Sacks.
Degrees of Unsolvability.
Number 55 in Annals of Mathematics Studies. Princeton University Press, 1963.
IX + 174 pages.

47
S. G. Simpson, editor.
Reverse Mathematics 2001, volume 21 of Lecture Notes in Logic.
Association for Symbolic Logic, 2005.
X + 401 pages.

48
Stephen G. Simpson.
An extension of the recursively enumerable Turing degrees.
Journal of the London Mathematical Society.
Preprint, August 2004, 15 pages, accepted for publication.

49
Stephen G. Simpson.
Mass problems.
Preprint, May 24, 2004, 24 pages, submitted for publication.

50
Stephen G. Simpson.
FOM: natural r.e. degrees; Pi01 classes.
FOM e-mail list [22], August 13, 1999.

51
Stephen G. Simpson.
FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes.
FOM e-mail list [22], August 16, 1999.

52
Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. Springer-Verlag, 1999.
XIV + 445 pages.

53
Stephen G. Simpson.
Medvedev degrees of nonempty Pi01 subsets of 2omega.
COMP-THY e-mail list [12], June 9, 2000.

54
Stephen G. Simpson.
sets and models of .
In [47], pages 352-378. 2005.

55
Stephen G. Simpson and Theodore A. Slaman.
Medvedev degrees of subsets of .
Preprint, July 2001, 4 pages, in preparation.

56
Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic. Springer-Verlag, 1987.
XVIII + 437 pages.

57
Andrea Sorbi.
The Medvedev lattice of degrees of difficulty.
In [13], pages 289-312, 1996.

58
Sebastiaan A. Terwijn.
The Medvedev lattice of computably closed sets.
Archive for Mathematical Logic.
Preprint, June 2004, 22 pages, accepted for publication.

59
Alan M. Turing.
On computable numbers, with an application to the Entscheidungsproblem.
Proceedings of the London Mathematical Society, 42:230-265, 1936.

60
Stanley S. Wainer.
A classification of the ordinal recursive functions.
Archiv für Mathematische Logik und Grundlagenforschung, 13:136-153, 1970.

61
Xiaokang Yu and Stephen G. Simpson.
Measure theory and weak König's lemma.
Archive for Mathematical Logic, 30:171-180, 1990.

Mass Problems and Randomness

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 massrand

The translation was initiated by Stephen G Simpson on 2007-09-28

Stephen G Simpson 2007-09-28