The Turing degrees below generics and randoms

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

July 24, 2013

Abstract

If x_{0} and x_{1} are both generic, the theories of the degrees below x_{0} and x_{1} are the same. The same is true if both are random. We show that the n-genericity or n-randomness of x do not suffice to guarantee that the degrees below x have these common theories. We also show that these two theories (for generics and randoms) are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.

1 Introduction

There are two common notions of what it means for a real number (which we identify with a binary string in Cantor space and so also a subset of ℕ) to be a “typical” real. One definition, of a “generic” real, is in terms of category and so topological. The other, of a “random” real, is given in terms of measure (usually Lesbegue). In each case there is a specified collection of large sets (comeager or measure 1) and their complements the small sets (meager or measure 0). The typical reals are thought of as being in every large set (or no small set). Of course, this is not literally possible as every singleton is a small set. A now standard procedure is to restrict the sets being considered to some countable family given in computability or definability theoretic terms and then require that a typical real be in every large (no small) set in the family of interest.

As usual, this provides a hierarchy of notions based on the extent of the family of sets being considered. This hierarchy begins with the levels of definability given by formulas of first order arithmetic (measured by quantifier complexity) and corresponds in computability theoretic terms to ones describably recursively (computably) in some iteration of the Turing jump, i.e. of the halting problem. (Precise definitions are given below in Definitions 2.1-2.3.)

∗Partially supported by NSF Grants DMS-0852811 and DMS-1161175, the Isaac Newton Institute and the John Templeton Foundation.

Our concerns here are with the computability theoretic properties of such typical reals. More specifically, we are interested in the structure of relative complexity of computation as specified by Turing reducibility. We say that one set A is Turing computable from, or recursive in, another B, A ≤_{T} B, if there is a (program for a) Turing machine Φ_{e} which, when equipped with an oracle for B (i.e. a procedure that answers all questions of the form “is n ∈ B” that the machine generates), computes membership in A. The equivalence classes of sets under this transitive relation are called the (Turing) degrees. We want to analyze the structure of this relation on the degrees computable from a typical set X for both notions of typicalness.

Our starting point is an old result of Jockusch [1980] that says that the first order structure of the degrees below a (fully, i.e. for all formulas of arithmetic) generic G is independent of the choice of G. This follows from either an application of classical 0 − 1 laws for category or by a standard analysis of genericity in terms of (Cohen like) forcing. In either case, the only relevant fact is that the degree of a set (infinite binary string) is invariant under finite changes. We denote this common theory (in the language with just ≤_{T}) by T h(≤ G). Jockusch (personal communication) asked long ago if any finite level n of genericity (as in Definition 2.1) suffices to guarantee that the degrees below an n-generic set have the same first order theory as those below a fully generic set.

Now the analogous 0 − 1 laws or forcing analysis (for Solovay like forcing) apply to measure as well as category and so if R and R̂ are both fully random (again for all levels of first order arithmetic), the theories of the degrees below each of them are the same. We call this common theory T h(≤ R). Barmpalias, Day and Lewis [2012] have recently extensively analyzed many degree theoretic properties of random reals and the amount of randomness needed to guarantee each of them. They explicitly ask the question for measure analogous to the one above for category (Question 8): Does some level n of randomness (as in Definition 2.2) suffice to guarantee that the theory of the degrees below an n-random real will be this common theory. They also ask (Question 7) if the two common theories, T h(≤ G) and T h(≤ R), are the same.

We supply negative answers (as were expected) for all of these questions. We also supply wholesale but precise information about the related theme of distinguishing between different levels of genericity or randomness in terms of the structure D(≤ x) of relative computability on sets recursive in such typical degrees x. Our theorems are as follows:

Theorem 1.1. There are sentences φ_{n} such that, for n ≥ 2, D(≤ x) ⊨ φ_{n} for every (n + 1)-generic or (n + 1)-random x but such that D(≤ x) ⊨ ¬φ_{n} for some n-generics and n-randoms.

(These are the same φ_{n} for n-generic x and n-random x.)

Theorem 1.2. There is a sentence φ such that D(≤ x) ⊨ φ for every 3-random x but D(≤ x) ⊨ ¬φ for every 3-generic x.

Now for n = 1, a sentence φ_{1} witnessing Theorem 1.1 is already known: φ_{1} says that there is no minimal degree. Theorem 2.7 below implies that no 2-generic or 2-random bounds a minimal degree. On the other hand, some 1-generics and 1-randoms do (Chong and Downey [1990] and Kumabe [1990] for 1-generics; for 1-randoms, Chaitin’s Ω [1975] is of degree 0′ and so bounds a minimal degree by Sacks [1966]; indeed, by Kucera [1985] or Gács [1986] every degree is computed by some 1-random). This φ_{1} is then what one might call a natural sentence distinguishing between 1 and 2 genericity and randomness. It seems quite difficult to find a wholesale collection of such “natural” sentences distinguishing between all (or indeed any of) the higher levels of genericity and randomness in terms of the first order theory of the degrees below them. At the very least, they would have to be of increasing quantifier complexity as, with a little care, the Cohen forcing argument mentioned above shows that, for each n, the degrees below any n + 2 generic have a common n-quantifier theory. Thus, no n-quantifier formula (of degree theory) can distinguish between the degrees below an n + 2 generic and an n + 3 generic. The situation is the same for Solovay like forcing and the levels of randomness by Kautz [1991, Theorem IV.2.2]. Our examples φ_{n} for n ≥ 2 are not only of increasing complexity but are of a quite different sort than the natural one given here for n = 1.

All of the sentences we supply distinguishing among these degree structures are based on interpreting arithmetic inside them. Thus we rely on a few basic facts about generics and randoms that allow us to apply the whole machinery of interpretations of true arithmetic in degree structures that has been extensively developed over the past few decades to answer these questions. Once we have explained how we can interpret arithmetic in the structures and code sets in the interpretations, one will understand that we can talk about many arithmetic properties of the degrees below x inside D(≤ x). Thus the sentences φ_{n} essentially say that there is a definable standard model of arithmetic in which there is a code for a set not recursive in 0^{(n)} (the nth iterate of the Turing jump). As noted below in Remark 2.4, no (n + 1)-generic or (n + 1)-random is recursive in 0^{(n)}. The fact that our interpretation allows us to code the top degree itself, makes φ_{n} true in D(≤ x) for x (n + 1)-generic or (n + 1)-random. On the other hand, we will see (based on Proposition 2.5 and Definition 2.6) that only sets recursive in x′′ can be coded in the defined models of arithmetic inside D(≤ x). Now there are n-generics and n-randoms x below 0^{(n)} and indeed ones with x^{(n)} = x ⊕ 0^{(n)} ≤ 0^{(n)}. (Apply Remark 2.4 to the results for n = 1 by Jockusch [1980] for generics and the low basis theorem applied to a Π_{1}^{0} class of 1-randoms for randoms as mentioned, for example, in Downey and Hirschfeldt [2010, Proposition 8.1.2].) The only degrees coded below such n-generics or n-randoms are recursive in 0^{(n)}. Thus φ_{n} is false in D(≤ x) for n-generic or n-random x with x′′ = x ⊕ 0′′≤ 0^{(n)}.

When it comes to distinguishing between T h(≤ G) and T h(≤ R), our sentence φ simply says that there is a code for a 3-random set in D(≤ x). Here we rely on the fact that if x is 3-generic then no 3-randoms can be computed from x′′. This is simply the relativization to 0′′ (via Remark 2.4) of the fact that no 1-generic computes a 1-random (Demuth and Kučera [1987]) plus the fact that, for x 3-generic, x′′ = x ⊕ 0′′.

2 Interpreting Arithmetic and Coding Sets

We want to describe the coding of arithmetic that we use in D(≤ x) for x at least 2generic or 2-random. General background information about coding and interpretations of arithmetic in degree structures can be found in Shore [2013] and arguments similar to the ones described here in Shore [2012]. First, however, our promised (standard) definitions of (n-)genericity and (n-)randomness.

Definition 2.1. X is n-generic (over A) if for every Σ_{n}^{0} (Σ_{n}^{A}) S ⊆ 2^{<ω} there is a σ ⊂ X such that σ ∈ S or ∀τ ⊇ σ(τ ∉ S).

Definition 2.2. X is n-random (over A) if for every uniformly Σ_{n}^{0} (Σ_{n}^{A}) collection V_{k} of open subsets of 2^{ω} of measure at most 2^{−k}, X ∉ ∩V_{k}. (The V_{k} are specified by uniformly Σ_{n}^{0} (Σ_{n}^{A}) subsets U_{k} of 2^{<ω} such that Z ∈ V_{k} ⇔ ∃σ ⊂ Z(σ ∈ U_{k}).)

Definition 2.3. X is generic (random) if it is n-generic (n-random) for every n ∈ ℕ. A degree x is (n-) generic or (n-)random if it contains a set which is (n-)generic or (n-)random.

Remark 2.4. It is clear from the definitions that X is (n + 1)-generic or (n + 1)-random if and only if it is 1-generic or 1-random, respectively, over 0^{(n)}. Thus, for example, as it is easy to see that no 1-generic or 1-random can be recursive, no (n + 1)-generic or (n + 1)-random can be recursive in 0^{(n)}.

From now on we assume that x is 2-generic or 2-random. We begin our path to coding sets and arithmetic into D(≤ x) with a specific highly effective form of coding orderings of type ω called nice effective successor structures introduced in Shore [1981]. They have been used as well in Nies, Shore and Slaman [1998] and Shore [2007] which contains (in §3) a good presentation of the details. For our purposes all we need to know is that the scheme provides a way of coding a sequence ⟨d_{n}⟩ of independent degrees (i.e. no d_{n} is below the join of the rest of the degrees d_{m}) by finitely many parameters q̄ which generate (under ∨ and ∧) a partial lattice including the d_{n}. We assume that the first element q_{0} of q̄ is a bound on all the other elements needed to determine this partial lattice. The crucial property of this coding is the following:

Proposition 2.5 (Shore [1981]). Given a q̄ determining a nice effective successor structure, the set of indices, relative to Q_{0} ∈ q_{0}, for the degrees in the ideal generated by the d_{n} is Σ_{3}^{Q_{0}} and any set S such that S = {n|d_{n} ≤ g_{0}, g_{1}} for any g_{0}, g_{1} ≤ g with q_{0} ≤ g is also Σ_{3}^{G}. Moreover, for every S ∈ Σ_{3}^{Z} with Q_{0} ≤_{T} Z, the set of indices relative to Z, for the ideal generated by {d_{n}|n ∈ S} is Σ_{3}^{Z}. (Note also that by the independence of the d_{n}, this ideal contains d_{n} if and only if n ∈ S.)

Definition 2.6. With the notation as in Proposition 2.5, we say that the set S is coded (with respect to the structure determined by q̄) by the degrees ḡ = ⟨g_{0}, g_{1}, g_{2}, g_{3}⟩ if S = {n|d_{n} ≤ g_{0}, g_{1}} and S̄ = {n|d_{n} ≤ g_{2}, g_{3}}. So if the ḡ, q̄ ≤ x then S ∈ Δ_{3}^{X}, i.e. S ≤_{T} X′′.

Next, we want to know that we can code these nice effective successor structures in D(≤ x) and indeed below any y≤x. We use the fact that the 1-generics are downward dense below x and so any recursive partial lattice can be embedded effectively below any 1-generic. (For random degrees the downward density is due to Kurtz [1981] and for 2-randoms to Kautz [1991].)

Theorem 2.7 (Jockusch [1980]; Barmpalias, Day and Lewis [2012]). The 1generic degrees are downward dense below x, i.e. ∀y ≤ x∃z ≤ y(y is 1-generic).

Theorem 2.8 (Greenberg and Montalbán [2003]). For each recursive partial lattice L and every 1-generic G, there is an embedding of L into the degrees below G which is uniformly recursive in G. So, in particular, every 1-generic G compute degrees \overline{q} determining a nice effective successor structure in which the d_{n} are uniformly recursive in q_{0}.

Proposition 2.5 and Definition 2.6 say that only sets S ∈ Δ_{3}^{X} can be coded by degrees below x in nice effective successor structures given by q̄≤x. We want a converse and so a characterization of which sets can be coded in D(≤ x). Again we rely on one fact about 2-generics and 2-randoms (due to Kurtz [1981] for randoms) and one about coding.

Theorem 2.9 (Jockusch [1980]; Kautz [1991]). Our degree x is RRE (relatively recursively enumerable), i.e. ∃y < x(x is r.e. in y).

Theorem 2.10 (Shore [1981]). If b <_{T} a, a is r.e. in b and I is a Σ_{3}^{B} ideal in D(≤ b) then there is an exact pair for I below a, i.e. g_{0}, g_{1} < a such that I = {z|z ≤ g_{0}, g_{1}}.

Thus for our x , the sets S which can be coded by ḡ ≤ x in some nice effective successor structure given by a q̄ ≤ x are precisely the ones Δ_{3}^{X}. Indeed, there is a y ≤ x (any in which x is RRE) such that the sets S so coded by ḡ ≤ x for downward dense such q̄ ≤ y are also precisely the ones Δ_{3}^{X}. Thus we have our characterization.

Corollary 2.11. The sets S that are coded by degrees ḡ below x in some nice effective successor structure given by q̄ ≤ x are precisely the S ≤_{T} X′′.

Next we want to move from simply coding sets to coding them in standard models of arithmetic given definably in D(≤ x). This will enable us to talk about the coded sets with the full apparatus of arithmetic and so to say for example that one of them is not recursive in 0^{(n)} (our sentence φ_{n}) or is 3-random (our sentence φ) as these facts are clearly definable in first order arithmetic.

The first step here is to specify schemes giving an interpretation of arithmetic in D(≤ x). We need a coding scheme S(\overline{p}), i.e. formulas φ_{D}(x, \overline{p}), φ_{+}(x, y, \overline{p}), φ_{×}(x, y, \overline{p}) and φ_{<}(x, y, \overline{p}) that provide, for each choice \overline{p} of parameters from D(≤ x), an interpretation of the language of arithmetic in D(≤ x) with +, ×, ≤ defined on D = {w|C ⊨ φ_{D}(w)} by the respective formulas to give a structure M(\overline{p}) for the language of arithmetic. (See Hodges [1993] for a general explanation of interpretations of one structure in another. Descriptions of ones designed specifically for interpreting arithmetic in degree structures can be found in Nies, Shore and Slaman [1998].) We also include a correctness condition φ_{C}(p̄) which says (at least) that M(\overline{p}) is a model of some standard finite axiomatization of arithmetic.

To carry our coding results over to the definable models of arithmetic, we also require that the parameters p̄ have an initial segment q̄ determining a nice effective successor structure as above such that the set {d_{n}} determined by q̄ is (in the obvious order) an initial segment of the domain D of M(p̄). Providing the translation of the axioms of arithmetic is a general fact about interpretations as is saying that d_{0} is the 0 of the structure. Saying that the d_{n} form an initial segment is phrased by using the definition of the way d_{n+1} is generated (in terms of ∨ and ∧) from the degrees in q̄. We also want to add a condition to φ_{C} that guarantees that the models M(p̄) for p̄ in D(≤ x) which satisfies it are all standard.

The primary tool for achieving all of these results is Slaman-Woodin forcing (Slaman and Woodin [1986]). In the setting of all the degrees D this forcing is used to code arbitrary countable sets and relations on the degrees by fixed formulas (with free variables) that depend only on the arity of the relation. As one substitutes arbitrary degrees for the free variables, the formulas define all countable relations of the corresponding arity. In proper substructures of D such as our D(≤ x), one has to take care to see which relations are coded in this way within the structure. The basic arguments in Slaman and Woodin [1986] immediately show that 2-genericity (relative to a listing of the relation itself) suffices. We need a bit more.

Theorem 2.12 (Greenberg and Montalbán [2003]). There is an m ∈ ℕ and a sequence ψ_{n}(z̄, ȳ) of formulas of degree theory with |z̄| = n and |ȳ| = m + 1 with the following property. Suppose that l ∈ ℕ, the set C uniformly computes both the sequence {C_{i}|i ∈ ℕ} of sets and the k_{j}-ary relations R_{j} on {deg(C_{i})|i ∈ ℕ} as represented by the sets {⟨i_{1}, …, i_{k_{j}}⟩ |R_{j}(deg(C_{i_{1}}), …, deg(C_{i_{k}}))} for j ≤ l and G is 1-generic over C. Then there are, for j ≤ l, \overline{P}_{j} (of length m) computable from G ⊕ C such that, for each j ≤ l, R_{j}(\overline{z}) ⇔ ψ_{k_{j}}(\overline{z}, c,\overline{p}_{j}). (As usual, c = deg(C) and similarly for the sets in the P̄_{j}.) Moreover, ψ_{k_{j}}(\overline{z}, c,\overline{p}_{j}) holds (in D) if and only if it holds in any (equivalently all) ideals (i.e. subsets of D closed downward and under join) containing c and the degrees in \overline{p}_{j}.

Greenberg and Montalbán [2003] show that this suffices, for example, to give an interpretation of arithmetic and a correctness condition that guarantees that any interpretation M(p̄) with p̄ satisfying the correctness condition is standard as long as one is working in a D(≤ x) such that the 1-generic degrees are downward dense below x. (So in particular, the theory of D(≤ x) for any such x computes that or true arithmetic.) As we need to control the sets coded in such models as well, we restrict the class of structures considered by requiring that the domains of the models (or at least their standard part) form a nice effective successor structure.

Given any z < x, by Theorem 2.7, there are u < v < z such that u is 1-generic and v is 1-generic over u (i.e. v is the degree of the join of U ∈ u and a G which is 1-generic over U). (One simply takes a V ≤_{T} Z which is 1-generic and chooses U = V^{[0]}.) Then by Theorem 2.8 one can choose degrees q̄ < u which specify a nice effective successor structure with its d_{n} uniformly recursive in q_{0}. Theorem 2.12 then says we can code any k-ary relations on the d_{n} which are uniformly recursive in q_{0} by the corresponding ψ_{k} by choosing degrees below v to substitute for the variables of ψ_{k} and that the relation will be correctly defined in D(≤ x) by this formula and these parameters. In particular we can extend q̄ to a sequence p̄ of degrees below v so that they determine a model of arithmetic M(p̄) defined in D(≤ x) and indeed in D(≤ v) and extend our correctness condition to describe the needed facts about the nice effective successor structure given by q̄ and which has the the d_{n} as an initial segment of its domain. (We can explicitly say that d_{0} is the 0 of M(p̄). Then we can use Slaman-Woodin forcing to say that there is a set containing d_{0} which is closed under the operations generating the d_{n} and that this set is an initial segment of M(p̄) with successor given by the generation process for the d_{n}.)

All that remains now to specify our definable interpretation of arithmetic is to extend the correctness condition to guarantee that the models so defined are all standard. This is already handled in Greenberg and Montalbán [2003] using the method of comparison maps and the downward density of the 1-generics. No additional issues arise because of our added requirement that an initial segment of the domain of the model be a nice effective successor structure determined by an initial segment q̄ of p̄. One simply requires that for any other structure M(w) with w < q_{0} there are formulas (given by Slaman-Wooden coding using parameters below x) that define one-one order preserving maps from every initial segment of M(p̄) to onto one of M(w). Our arguments already show that standard models of the form M(p̄) in our class exist with p̄ below any given u < v < x. As the required maps between initial segments of such models and any model are all finitary, they are all definable below v by Theorem 2.12. Thus we have the required definable class of standard models with defining parameters downward dense below x.

We can now complete the proofs of Theorems 1.1 and 1.2.

Our previous analysis of which sets can be coded in the models we have described shows that all are Δ_{3}^{X} and there are such models (below u < v < y where u and v are as we have just described and y is such that x is RRE in it) in which all Δ_{3}^{X} sets can be coded. It follows that there is a set S ≰_{T} 0^{(n)} coded in such a model in D(≤ x) if and only if X′′ ≰_{T} 0^{(n)}. As we have noted in Remark 2.4, this condition holds for every (n + 1)-generic and (n + 1)-random X for n ≥ 2. Thus φ_{n} is true for every such X. On the other hand, as explained above, there are n-generic and n-random X such that X′′ ≡_{T} X ⊕0′′ ≤_{T} 0^{(n)} for every n ≥ 2. For such X, every S coded in D(≤ x) is recursive in 0^{(n)}, i.e. φ_{n} fails in D(≤ x) for such x. This proves Theorem 1.1.

As for Theorem 1.2, if X is 3-random, there is clearly a 3-random set (namely X itself) coded in one of our M(p̄) in D(≤ x). On the other hand, we have already noted above that no 3-random can be computed from X′′ for any 3-generic X and so φ is false in D(≤ x) for every 3-generic x as required to prove Theorem 1.2.

As a final point, we remark that while T h(≤ G) and T h(≤ R) are different theories, they have the same Turing (even 1−1) degree. As noted above Greenberg and Montalbán [2003] show that the downward density of the 1-generics suffices to show that they each compute (even in a 1 − 1 way) 0^{(ω)} or, equivalently, T h(ℕ), the true theory of arithmetic. On the other hand the fact (Jockusch [1980] for generics and the uniformity present in III.2.1 of Kautz [1991]) that there are generics and randoms X such that X^{(ω)} ≡_{T} 0^{(ω)} (and indeed with the same 1 − 1 degree), shows that each of T h(≤ G) and T h(≤ R) are even 1 − 1 reducible to 0^{(ω)} and T h(ℕ).

3 Bibliography

Barmpalias, G., Day, A. R. and Lewis, A. E. M. [2012], The typical Turing degree, Proc. London Math. Soc., to appear.

Chaitin, G. J. [1975], A theory of program size formally identical to information theory. J. Ass. Comp. Mach. 22, 329–340.

Chong, C. T. and Downey, R. G. [1990], Minimal degrees recursive in 1-generic degrees, Ann. Pure Appl. Logic 48, 215–225.

Demuth, O. and Kučera, A. [1987], Remarks on 1-genericity, semigenericity and related concepts, Comment. Math. Univ. Carolin. 28, 85–94.

Downey, Rodney G.; Hirschfeldt, Denis R. Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010.

Gács, P. [1986], Every set is reducible to a random one, Information and Control 70, 186–192.

Greenberg, N. and Montalbán, A. [2003], Embedding and coding below a 1-generic degree, Notre Dame J. Formal Logic 44, 200–216.

Jockusch, C. G. jr. [1980], Degrees of generic sets, in Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979), London Math. Soc. Lecture Note Ser., 45, Cambridge Univ. Press, Cambridge-New York, 110–139.

Kautz, S. [1991], Degrees of random sets, Ph.D. Thesis, Cornell University.

Kurtz, S. [1981], Randomness and Genericity in the Degrees of Unsolvability, Ph.D. Thesis, University of Illinois.

Kumabe, M. [1990], A 1-generic degree which bounds a minimal degree, J. Symbolic Logic 55, 733–743.

Kuc̆era, A. [1985], Measure, Π_{1}^{0} classes, and complete extensions of PA, in H.-D. Ebbinghaus, G. H. M¨ uller, and G. E. Sacks, eds., Recursion Theory Week, Proceedings of the Conference Held at the Mathematisches Forschungsinstitut in Oberwolfach, April 15–21, 1984, Lecture Notes in Mathematics 1141, 245–259.

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

Sacks, G. E. [1966], Degrees of unsolvability, Annals of Math. Studies 55, Princeton Univ. Press, Princeton NJ.

Shore, R. A. [1981], The theory of the degrees below 0′, J. London Math. Soc. (3) 24 (1981), 1-14.

Shore, R. A. [2007], Direct and local definitions of the Turing jump, J. of Math. Logic 7, 229-262.

Shore, R. A. [2012], Biinterpretability up to double jump in the degrees below 0′, Proc. Am. Math. Soc., to appear.

Shore, R. A. [2013], Lecture notes on the Turing degrees, AII Graduate Summer School in Logic, Singapore, 28 June - 23 July 2010, to appear (available as item 130 at http://www.math.cornell.edu/~shore/publications.html).

Slaman, T. A. and Woodin, H. W. [1986], Definability in the Turing degrees, Illinois J. Math. 30, 320-334.