Rigidity and biinterpretability in the hyperdegrees

Richard A. Shore^{∗} Department of Mathemcatics Cornell Univeristy Ithaca NY 14853

October 31, 2005

Abstract

Slaman and Woodin have developed and used set-theoretic methods to prove some remarkable theorems about automorphisms of, and definability in, the Turing degrees. Their methods apply to other coarser degree structures as well and, as they point out, give even stronger results for some of them. In particular, their methods can be used to show that the hyperarithmetic degrees are rigid and biinterpretable with second order arithmetic. We give a direct proof using only older coding style arguments to prove these results without any appeal to set-theoretic or metamathematical considerations. Our methods also apply to various coarser reducibilities.

1 Introduction

Slaman and Woodin [2006] (see also Slaman [1991]) have developed and used set-theoretic and metamathematical techniques to prove some remarkable theorems about the Turing degrees, D_{T}. These techniques include forcing over models of ZFC to make the set of reals in the ground model countable in the generic extension as well as absoluteness arguments. One key result is that every relation on D_{T} invariant under automorphisms and definable in second order arithmetic is actually definable in D_{T}. They also prove that the double jump is invariant and hence definable. (This result was then used by Shore and Slaman [2000] to prove that the Turing jump itself is definable in D_{T}.) As other examples, we mention their results that every degree above 0′′ is fixed under every automorphism; there are at most countably many automorphisms of D_{T}; and in fact every 5-generic g is an automorphism base (i.e. if π is an automorphism of D_{T} and π(g) = g then π is the identity map).

∗Partially supported by NSF Grant DMS-0100035 and the IMS of the National University of Singapore. The material in this paper was presented in a talk at the IMS workshop Computational Prospects of Infinity in July, 2005. We also want to thank Ted Slaman for some conversations and suggestions.

Slaman [1991] points out that their methods apply to a wide array of degree structures, often giving stronger results based on specific special properties of the reducibility. For example, in the arithmetic degrees, D_{a}, every automorphism is the identity on the degrees above 0^{(ω)}, the first arithmetic jump of 0, while the hyperdegrees D_{h} are rigid and biinterpretable with second order arithmetic. Thus every relation on D_{h} is definable if and only if it is definable in second order arithmetic.

(We say that X is arithmetic in Y, X ≤_{a} Y, if X ≤_{T} Y^{(n)} for some n ∈ ω and X is hyperarithmetic in Y, X ≤_{h} Y, if X ≤_{T} Y^{(α)} for some ordinal α recursive in Y where Y^{(α)} is the α^{th} iterate of the Turing jump applied to Y. Kleene showed (see Sacks [1990, II.1-2]) that X ≤_{h} Y if and only if X is Δ_{1}^{1}(Y). A degree structure D is biinterpretable with second order arithmetic if there is a definable standard model of arithmetic (or class of structures all isomorphic to ℕ) with definable schemes for both quantification over subsets of the model and a relation matching degrees with codes for sets in the model which are of the specified degrees. Of course, this immediately gives the desired result on definability of relations on D. See Slaman and Woodin [2006] for more details.)

Our goal here is to prove first that D_{h} is rigid by a direct coding argument similar to that used in Abraham and Shore [1986] to prove (under mild set theoretic hypotheses such as ℵ_{1}^{L[r]} being countable for every real r) that the constructibility degrees of reals are rigid. Both arguments are based on lattice embedding construction from the Turing degrees as in Shore [1982a]. The methods needed do the required embeddings are just Cohenlike forcing in the setting of the hyperarithmetic hierarchy. We also use ideas from Shore [1981] and [1982] to make the codings sufficiently effective to make the recovery of the set coded hyperarithmetic in the top degree of the embedded lattice. We then use the coding methods of Slaman and Woodin [1986] (in the hyperarithmetic setting) to translate the rigidity proof to one of biinterpretability. We exploit the specific proof of rigidity to do this translation and so avoid the need to definably deal with automorphisms as is possible using the set-theoretic methods and absoluteness results of Slaman and Woodin.

In Section 2, we present the proof of rigidity in abstract terms based on the existence of a coding scheme satisfying certain properties. In Section 3, we describe the specific lattices we employ that implement these coding requirements. Then, in Section 4, we use Cohen forcing in the hyperarithmetic setting as introduced by Feferman [1965] and presented in Sacks [1990] to show that all countable lattices (with 0) can be embedded into D_{h}. Finally, in Section 5, we describe the translation to biinterpretability and comment on the applicability of our methods to other coarser degree structures mentioned in Slaman [1991].

2 Rigidity

Intuitively, our basic idea is to code any given set X of degree x into D_{h} “near x” in such a way as to be able to uniquely pick out the set X in way that is definably tied to the degree x. We want some structure L_{X} from which X can be “easily” recovered and that we can embed into D_{h} near x.

First we explain what constitutes “easily” recoverable. In the setting of the Turing degrees, the underlying obstacle to improving the results fixing, for example, the cone above 0′′ under all automorphisms is the complexity of the notion of Turing reducibility. The relation X ≤_{T} Y is Σ_{3}(X, Y) and, in general, a formula of the form (∃X ≤_{T} Y)Φ(X, Y) is Σ_{3}(Y) even when Φ is recursive. Thus the best one can hope for is that a formula about D_{T} in the language with ≤_{T} is that it will be Σ_{3} in the degrees mentioned and even this only for positive existential formulas. (As the sets Σ_{3} in X determine the degree of X′′ and vice versa, this is the source of the ubiquitous nature of the double jump, and of 0′′ in particular, in the results on D_{T}.) In the setting of the constructibility degrees of reals, D_{c}, the relation X ≤_{c} Y is itself constructible and so any quantifier free relation in the language with ≤_{c} on degrees is itself constructible. It is that advantage that permits the coding proof of rigidity of Abraham and Shore [1986] to work in D_{c} but leaves it a couple of jumps short in D_{T}. The situation for hyperarithmetic reducibility is intermediate but close enough to that for constructibility to allow a slightly modified proof to work. Not only is X ≤_{h} Y a Π_{1}^{1}(X, Y) relation but a formula ∃X ≤_{h} Y Φ(X, Y) is equivalent to a Π_{1}^{1} formula when Φ is itself Π_{1}^{1}. Thus a positive coding of both X and its complement X̄ (i.e. one that can be decoded by considering only positive existential formulas in the language with ≤_{h}) would show both X and X̄ to be Π_{1}^{1}, and so hyperarithmetic, in the coding degrees. In all of these settings, the addition of ∨ to the language does not cost any more as we can go effectively between X,Y and X ⊕ Y.

To be a bit more specific we work with lattices with 0 and 1 and plan to associate with each set X a lattice M_{X} which codes membership in both X and X̄ by a recursive list of positive elementary formulas (in ≤ and ∨). (Note that we must avoid using ∧ in our decoding formulas since it costs another quantifier.) Thus we will have a lattice M_{X} such that, for any lattice embedding f : M_{X} → D_{h}, X ≤_{h} f(1_{M_{X}}). Actually, we work with partial lattices. A partial lattice is a partial order in which join and infimum are determined by relations which define partial functions satisfying the usual conditions (in terms of order) for ∨ and ∧ when defined. Our constructions are no different for partial lattices than for lattices and realizing this means that when describing a structure we do not have to specify all the infima and suprema but only the ones relevant to our concerns. Thus whenever we say lattice below we include partial lattices as well.

Next, the notion of “near x” might suggest that we want f(1_{M}) ≤_{h} x. This is done for many of the arguments in D_{T} but only once one is above, for example, 0′ or 0′′ or is considering degrees with some other special property. It was also done in D_{c} below Cohen generic reals (Abraham and Shore [1986]) and a similar argument would work in the setting of D_{h}. Instead, we employ one in which “near” means that f(0_{M}) = x. This procedure avoids some additional argumentation used for D_{c} by building a bit more into our structure. We form a new lattice L_{X} from two disjoint copies M_{X} and M̂_{X} of our original one by letting 1_{L_{X}} be the join of 1_{M_{X}} and 1M̂_{X} and 0_{L_{X}} be their infimum.

Now, suppose we have an embedding f : L_{X} → D_{h} that takes 0_{L_{X}} to x and we consider any automorphism π of D_{h}. As it is an automorphism, π carries the image of L_{X} under f to another image πf(L_{X}) in D_{h}. The coding scheme assumed above insures that x ≤_{h} πf(1_{M_{X}}), πf(1M̂_{X}). On the other hand, as f is a lattice embedding, x ≡_{h}f(1_{M_{X}}) ∧ f(1M̂_{X}) and so applying the automorphisms gives π(x) ≡_{h} πf(1_{M_{X}}) ∧ πf(1M̂_{X}). Thus x ≤_{h}π(x). The same argument applied to π^{−1} gives x ≤_{h}π^{−1}(x) and so π(x) ≤_{h} x. Thus x ≡_{h}π(x) for every automorphism π of D_{h}. To prove rigidity all we have to do now is describe, for each X, a lattice L_{X} with the desired properties and prove that it can be embedded in D_{h} with 0_{L_{X}} going to x.

3 Coding

The essential ingredient in making X “easily” recoverable from the coding lattice L_{X} is the “effectively generated” model of arithmetic introduced in Shore [1982],[1981]. We here need only the successor function and the coding of the set X. The elements of our lattice that generate a copy of ℕ are designated by d_{0}, e_{0}, e_{1,}f_{0} and f_{1}. The element of the lattice corresponding to n ∈ ℕ is d_{n}. The generating scheme that implements the successor function on ℕ is determined by the following requirements:

1. (d_{2n} ∨ e_{0}) ∧ f_{1} = d_{2n+1} and

2. (d_{2n+1} ∨ e_{1}) ∧ f_{0} = d_{2n+2}.

These conditions clearly guarantee that we can enumerate the d_{n} recursively in the lattice structure and write a recursive list of quantifier free formulas in this language which define each of them. We wish to convert this procedure and these formulas into ones that are positive in the language with just ≤ and ∨ at least to the extent that we can use them to code X and X̄ (with the aid of other parameters c and c̄). In Shore [1982] and [1981] the lattices were embedded as initial segments with the d_{n} as minimal elements and so it sufficed to say, for example, that d_{2n+1} ≤ (d_{2n} ∨ e_{0}), f_{1} and d_{2n+1} ≠ 0. As for being different from 0, we can simply add two other parameters p and q and require in our lattice that q ≠ 0 and p ∨ d_{n} ≥ q for each n. Thus we can say of an x that we view as a candidate for being one of the d_{n} that x ∨ p ≥ q in place of saying that x ≠ 0. In the context of coding X (done by exact pairs outside the basic lattice rather than by internal elements in Shore [1981] for reasons extraneous to our concerns here) we can replace the initial segment features of the structure with additional purely lattice theoretic requirements on the coding parameters. Specifically, we require the lattice to have two additional parameters c_{X} and c̄_{X} such that d_{n} ≤ c_{X} for n ∈ X, d_{n} ∧ c_{X} = 0 for n ∉ X, d_{n} ≤ c̄_{X} for n ∉ X and d_{n} ∧ c̄_{X} = 0 for n ∈ X.

We now show how to recursively generate positive existential formulas ϕ_{n}(x) using just ≤ and ∨ such that, in any lattice L_{X} with elements d_{0}, e_{0}, e_{1,}f_{0}, f_{1}, p and q as described, ϕ_{n}(x) holds of x if and only 0 < x ≤ d_{n}. Given such formulas, our requirements on c and c̄ allow us to define X by n ∈ X ⇔ ∃x(ϕ_{n}(x) & x ≤ c_{X}) and n ∉ X ⇔ ∃x(ϕ_{n}(x) & x ≤ c̄_{X}). As we have already noted, when interpreted in an isomorphic copy of L_{X} in D_{h}, such formulas are equivalent to ones Π_{1}^{1} in the relevant parameters.

We begin with x = d_{0} as ϕ_{0}. Recursively, we let ϕ_{2n+1}(x) be ∃z(ϕ_{2n}(z) & x ≤ z ∨e_{0}, f_{1} & q ≤ x∨p) and ϕ_{2n+2}(x) be ∃z(ϕ_{2n+1}(z) & x ≤ z ∨e_{1}, f_{0} & q ≤ x∨p). Consider any x such that ϕ_{2n+1}(x) holds. We then have a z as described such that, by induction, 0 < z ≤ d_{2n}. Thus z ∨ e_{0} ≤ d_{2n} ∨ e_{0} and so x ≤ d_{2n} ∨ e_{0}, f_{1}. As d_{2n+1} = (d_{2n} ∨ e_{0}) ∧ f_{1}, x ≤ d_{2n+1} as required. Of course, q ≤ x ∨ p guarantees that x > 0 as well. The argument for ϕ_{2n+2} is essentially the same.

We now turn to embedding countable lattices in D_{h}.

4 Embedding lattices

In this section, we describe how the elementary methods of Shore [1982a] in the Turing degrees can be used to embed any countable (partial) lattice with 0 in D_{h} preserving 0. Relativization to any degree x supplies the desired embeddings of L_{X} (the partial lattice generated as specified above by elements d_{0}, e_{0}, e_{1,}f_{0}, f_{1}, p, q, c and c̄) as it is recursive in X as a partial lattice, i.e. the partial order, the partial functions ∨ and ∧ and their domains are recursive in X.

The standard lattice representation arguments (originally from Jonsson [1953] but translated into the language of Lerman [1971] or [1983] and as presented also in Shore [1982a]) give our desired representation theorem. (A simple proof without the requirement for 0 is in Shore [1982a]. Adding the requirement that the value of each function in the representation is 0 at 0 at the beginning presents no difficulties nor does relativization to X.)

Theorem 4.1. Let {p_{i}} enumerate a recursively presentable partial lattice P with p_{0} its least element. There is a uniformly recursive array of functions α_{n} : ω → ω such that for all i, j, k, n, m:

0. α_{n}(0) = 0,

1. p_{i} ≤ p_{j} ⇒ α_{n}(j) = α_{m}(j) → α_{n}(i) = α_{m}(i) and p_{i} ≰ p_{j} ⇒ ∃q, r(α_{q}(j) = α_{r}(j) & α_{q}(i) ≠ α_{r}(i)),

2. p_{i} ∨ p_{j} = p_{k} ⇒ [α_{n}(i) = α_{m}(i) & α_{n}(j) = α_{m}(j) → α_{n}(k) = α_{m}(k)],

3. p_{i} ∧ p_{j} = p_{k} & α_{n}(k) = α_{m}(k) ⇒ ∃q_{1}, q_{2}, q_{3}[α_{n}(i) = α_{q_{1}}(i) & α_{q_{1}}(j) = α_{q_{2}}(j) & α_{q_{2}}(i) = α_{q_{3}}(i) & α_{q_{3}}(j) = α_{m}(j)].

We can define an embedding of P into D_{h} from any sufficiently generic function g : ω → ω by setting the image of p_{i} to be the degree of the function h_{i} defined by h_{i}(n) = α_{g(n)}(i). Intuitively, if one iterates the construction of trees of (n+1)-generics inside ones of n-generics into the transfinite taking appropriate diagonal-like intersections of the trees at limits one gets paths P which are generic at each level γ of the hyperarithmetic hierarchy and make P^{(γ)} ≡_{T} P ⊕ 0^{(γ)}. If one does this uniformly and properly for all recursive γ one gets a generic P (indeed one recursive in O) such that, in addition, ω_{1}^{P} = ω_{1}^{CK} and so everything hyperarithmetic in P is recursive in P ⊕ 0^{(γ)} for some recursive γ. This reduces the arguments about hyperarithmetic reducibility to ones about Turing reducibility and so the correctness of the embedding in the hyperarithmetic setting can be read off from the proof for the Turing degrees.

Formalizing this idea seems to require a hierarchy of languages in which one can talk about formulas (and terms representing the sets constructed) at each level of the hyperarithmetic hierarchy. The needed facts can probably be extracted from, e.g. MacIntyre [1977] who modifies the basic approach to Cohen forcing in the hyperarithmetic setting as introduced by Feferman [1965] (or from the analysis of a more general setting in Jockusch and Shore [1984]). We describe a somewhat coarser but more readily available analysis based on essentially the presentation in Sacks [1990] of Feferman’s results. For convenience we make the purely notational change of using a function symbol G in our forcing language in place of one T for a set as in Sacks [1990] and so the conditions consist of consistent finite conjunctions of formulas of the form G(n) = m thought off as nonempty subbasic open subsets of ω^{ω} (in place of 2^{ω}). (If one prefers, one can keep the set version and code our desired function into a set in any standard way.). We also introduce standard terms H_{i} for the h_{i} with the specified interpretations and the obvious forcing relations. By generic we now mean generic for the (obvious extension of the) ramified language L(ω_{1}^{CK}, G) defined in Sacks [1990, III.4], i.e. for every formula F there is a condition satisfied by the generic that decides F. Also note that there is a term of the language x̂Φ(x) for each ranked formula Φ that denotes the set of numbers satisfying Φ which define all the elements of the structure M(ω_{1}^{CK}, g). For generic g with ω_{1}^{g} = ω_{1}^{CK}, the structure consists of all sets hyperarithmetic in g as is shown there as well. Of course, the sets hyperarithmetic in the h_{i} are represented by terms t(H_{i}) built up from H_{i}, i.e. ones x̂Φ(x) where Φ (hereditarily) contains H_{i} but no other H_{j} or G. The existence of functions g generic in this sense with g ≤_{h} O and so ω_{1}^{g} = ω_{1}^{CK} as well as all the usual facts about generic objects can be found in Sacks [1990, IV.3]. We can now easily argue as in the Turing degrees that we have the desired (partial) lattice embedding.

Theorem 4.2. Let P be a recursive partial lattice (with 0); let α_{n} be a recursive representation of P as in Theorem 4.1; and g be an M(ω_{1}^{CK}) generic. The map taking p_{i} to the hyperdegree of h_{i} as defined above preserves the partial lattice structure of P.

Proof. The argument is standard. As h_{0}(n) = α_{g(n)}(0) = 0 for every n by 4.1.0, 0 is preserved. If p_{i} ≤ p_{j} then h_{i}(n) = α_{n}(i) = α_{m}(i) for any m such that α_{m}(j) = α_{n}(j) = h_{j}(n) and so h_{i} is even recursive in h_{j} as the array α_{n} is uniformly recursive. Thus the embedding preserves order. Similarly if p_{i} ∨ p_{j} = p_{k} we can compute h_{k}(n) = α_{g(n)}(k) recursively from h_{i}(n) and h_{j}(n) by finding any α_{m} such that α_{m}(i) = h_{i}(n) = α_{g(n)}(i) and α_{m}(j) = h_{j}(n) = α_{g(n)}(j) as by 4.1.1, α_{m}(k) = α_{g(n)}(k) = h_{k}(n) for any such m. Thus the embedding preserves join when defined in P. The arguments for preserving ≰ and ∧ depend on genericity.

Suppose p_{i} ≰ p_{j} and consider any term t(H_{j}) of the language generated by H_{j}. We wish to show that t(h_{j}) ≠ h_{i} as this implies that h_{1} ≰_{h} h_{j}. If it were otherwise, there would be a condition q ⊩ t(H_{j}) = H_{i}. By 4.1.2 there are n and m such that α_{n}(j) = α_{m}(j) but α_{n}(i) ≠ α_{m}(i). Let r be an extension of q containing the formula G(z) = n which decides a values for t(H_{j})(z) and forces g(z) = n for some z not mentioned in q and let r′ be the same condition as r except that it contains G(z) = m in place of G(z) = n. As the interpretation of H_{j} is the same in any two generics extending r and r′ which differ only at z both conditions force the same value for t(H_{j})(z). On the other hand, r ⊩ H_{i}(z) = α_{n}(i) while r′ ⊩ H_{i}(z) = α_{m}(i). As α_{n}(i) ≠ α_{m}(i) by our choice of n and m we have the desired contradiction. Thus the embedding preserves ≰.

Finally, suppose that p_{i}∧p_{j} = p_{k}. We already know that h_{i} and h_{j} are hyperarithmetic (indeed recursive) in h_{k} by the preservation of order. We wish to show that any f ≤_{h} h_{i}, h_{j} is hyperarithmetic in h_{k}. We take terms t_{0} and t_{1} and a condition q satisfied by g that forces t_{0}(H_{i}) = t_{1}(H_{j}) and describe a procedure hyperarithmetic in h_{k} that defines f = t_{0}(h_{i}) = t_{1}(h_{j}). The definition of f from h_{k} as a function on ω is given by the following procedure: to find f(u) find any r extending q which forces some particular (necessarily common) value for t_{0}(H_{i})(u) and t_{1}(H_{j})(u) such that h_{k}(z)(= α_{g(z)}(k)) = α_{r(z)}(k) for every z in the domain of r. We claim that this procedure is hyperarithmetic in h_{k} and provides the true value of these terms evaluated on h_{i} and h_{j}, respectively. It is, of course, recursive in h_{k} to check that a forcing condition satisfies the second requirement. As forcing for sentences of fixed rank is a hyperarithmetic relation, this procedure produces a hyperarithmetic reduction of f to h_{k} as long as it always produces the correct value.

To see that the procedure always produces the correct values, suppose there are u, v ≠ w ∈ ω and some r extending q as described such that r ⊩ t_{0}(H_{i})(u) = t_{1}(H_{j})(u) = v but t_{0}(h_{i}) = w = t_{1}(h_{j}). As g is generic there is an s extending q satisfied by g that forces t_{0}(H_{i})(u) = t_{1}(H_{j})(u) = w. We now work for a contradiction. Assume without loss of generality that the domains of r and s are the same. For each z in this common domain, α_{r(z)}(k) = α_{s(z)}(k) by our assumption on r. By 4.1.3, we can choose for each such z numbers q_{z,l} for l = 1, 2, 3 witnessing the conclusion of 4.1.3 for α_{r(z)} and α_{s(z)} in place of α_{n} and α_{m}. We define forcing conditions q_{l} by q_{l}(z) = q_{z,l}. We extend these conditions to generics g^{l} (with g^{0} extending r) by simply copying g when they are not defined. (Finite changes in a generic keep the function generic.) It is clear from the requirements of 4.1.3 that h_{i}^{0} = h_{i}^{1}, h_{j}^{1} = h_{j}^{2}, h_{i}^{2} = h_{i}^{3} and h_{j}^{3} = h_{j}. Thus by our choice of q and the first equality, v = t_{0}(h_{i}^{0})(u) = t_{0}(h_{i}^{1})(u). Our choice of q and the next equalities give t_{0}(h_{i}^{1})(u) = t_{1}(h_{j}^{1})(u) = t_{1}(h_{j}^{2})(u) = t_{0}(h_{i}^{2})(u) = t_{0}(h_{i}^{3})(u) = t_{1}(h_{j}^{3})(u) = t_{1}(h_{j})(u) but this last term has value w ≠ v by assumption for the desired contradiction.

This theorem shows that the partial lattices described in the Section 3 can be embedded in D_{h} as required to implement the proof of rigidity described there and in Section 2. Thus we have our direct proof of rigidity.

Theorem 4.3. (Slaman and Woodin) The hyperdegrees are rigid.

5 Biinterpretability

Slaman and Woodin [2006] prove for D_{T} that rigidity implies biinterpretability by showing that one can describe their full analysis of persistence of automorphisms within the degree structure itself. As mentioned in Slaman [1991] their methods apply to many other degree structures. Based on our direct proof of rigidity for D_{h} we can derive biinterpretability using only the coding methods of Slaman and Woodin [1986] to code each countable relation (there on D_{T}, here on D_{h}) by finitely many parameters (uniformly in the arity of the relation) in the setting of the hyperarithmetic degrees. These methods will also apply to the coarser degree structures mentioned in Slaman [1991].

There is not much needed here beyond pointing out that the coding constructions of Slaman and Woodin [1986] work the same way for D_{T} as long as one uses Cohenlike forcing in the hyperarithmetic setting in place of the arithmetic one used in their work. Indeed, the arguments here are even a bit simpler since we do not need the careful calculations done there of how much genericity is needed. We give a brief description of the argument.

The first step is to prove that any antichain of degrees a_{i} is definable from three parameters b, g_{1} and g_{2}. We take B ∈ b to be an upper bound on the a_{i}. The other parameters are defined by a forcing construction. One begins with a sequence of representatives A_{i} ∈ a_{i} such that A_{i} is recursive in any of its infinite subsets. The notion of forcing, P, consists of triples p = ⟨p_{1}, p_{2}, p_{3}⟩ where p_{1}, p_{2} ∈ 2^{<ω} have the same length (which we also call the length of p) and p_{3} ∈ ω. Extension is defined by q ≤ p ⇔ q_{1} ⊇ p_{1} & q_{2} ⊇ p_{2} & q_{3} ≥ p_{3} & ∀k ≤ p_{3}∀a ∈ A_{k}(|p_{1}| < ⟨k, a⟩ ≤ |q_{1}| → q_{1}(⟨k, a⟩) = q_{2}(⟨k, a⟩)). Let G be any generic for P in the sense of hyperarithmetic forcing analogous to the one in Sacks [1990] as described above relativized to B with basic terms A_{k} for the A_{k}, B for B and G_{1}, G_{2} for the unions of first and second coordinates of G as well. If G_{1}, G_{2} are the union of the first coordinates of G then the set {a_{i}|i ∈ ω} of hyperdegrees is definable as the set of minimal solutions x in D_{h} below b to the equation (g_{1} ∨ x) ∧ (g_{2} ∨ x) ≠ x.

To see that each a_{k} satisfies the equation, consider a condition p ∈ G with p_{3} ≥ k and the set C(k) = {m ∈ A_{k}| |p_{1}| < ⟨k, m⟩ ∈ G_{1}}. It is immediate from its definition that C(k) ≤_{T} G_{1} ⊕ A_{k} and it follows from the choice of p and the definition of extension that C(k) = {m ∈ A_{k}| |p_{1}| < ⟨k, m⟩ ∈ G_{2}} and so C(k) ≤_{T} G_{2} ⊕ A_{k} as well. To see that C(k) ≰_{h} A_{k} suppose to the contrary and choose a term t_{1}(G_{1}) for C(k) and consider a term t so that t(A_{k}) is a standard name for a given set hyperarithmetic in A_{k} and a condition q ∈ G extending p such that q ⊩ t(A_{k}) = t_{1}(G_{1}). Let m ∈ A_{k} be larger than |q_{1}|. We can clearly find an extension r of q such that r_{1}(⟨k, m⟩) ≠ t(A_{k})(⟨k, m⟩) as the right hand side is fixed independently of the choice of generic. This gives the desired contradiction.

Next, we suppose we have some C ≤_{h} B and D ≤_{h} G_{1} ⊕ C, G_{2} ⊕ C such that D ≰_{h} C and prove that A_{k} ≤_{h} C for some k. Choose terms t_{C}(B), t_{D}(B), t_{1}(G_{1} ⊕ t_{c}(B)), t_{2}(G_{2} ⊕ t_{c}(B)) representing the relevant sets and a condition p ∈ G such that p ⊩ t_{D}(B) = t_{1}(G_{1} ⊕ t_{c}(B)) = t_{2}(G_{2} ⊕ t_{c}(B)). There must be infinitely many n with conditions q^{n}, r^{n} of p of common length at least n extending p that force different values for t_{1}(G_{1}⊕t_{c}(B))(n) as otherwise we could compute D hyperarithmetically in C by finding for each n (other than the finitely many assumed exceptions) any condition q of length at least n extending p that forced a value for t_{1}(G_{1} ⊕ t_{c}(B))(n) and know that it is the correct value. As forcing for formulas of fixed rank is hyperarithmetic in the parameter C, this would contradict our assumption that D ≰_{h} C. We can thus find such q^{n} and r^{n} hyperarithmetically in C. We can interpolate a sequence of conditions s^{n,1}, …, s^{n,m} between q^{n} and r^{n} so that the successive s^{n,i} differ at exactly one number. We can then extend the s^{n,i} to ŝ^{n,i} which also differ only at that same location and each force a value for t_{1}(G_{1} ⊕ t_{c}(B))(n) = t_{2}(G_{2} ⊕ t_{c}(B))(n). As the values at the two ends are different there must be an i such that ŝ^{n,i} and ŝ^{n,i+1} force different values. If the one location ⟨j, m⟩ at which they differed were not such that j < p_{3} and m ∈ A_{j} then we could form a single condition s = ⟨ŝ1^{n,i}, ŝ2^{n,i+1}, u⟩ for u the maximum of the third coordinates of the two conditions which would extend p and have the same values for G_{1} and G_{2} as ŝ^{n,i} and ŝ^{n,i+1}, respectively. Thus s would force the same value for t_{1}(G_{1} ⊕ t_{c}(B))(n) as ŝ1^{n,i} while it would force the same value for t_{2}(G_{2} ⊕ t_{c}(B))(n) as ŝ^{n,i+1}. As these are different and s extends p this would be a contradiction. Thus there are infinitely many pairs of conditions (extending p) differing only at one point ⟨j, m⟩ with j < p_{3} which force different answers. Again, as the forcing relation for formulas of fixed rank is hyperarithmetic, we can find infinitely many such hyperarithmetically in the parameter C. As all of these must have m ∈ A_{j} by our argument above and there must be infinitely many with the same j < p_{3}, we can find infinitely many m ∈ A_{j} for this j hyperarithmetically in C. Thus by our choice of A_{j}, A_{j} ≤_{h} C as required.

Finally, Slaman and Woodin [1986] show how to convert an arbitrary countable relation on the degrees into an antichain so that the original relation is definable from the antichain and parameters. Suppose R is an n-ary relation on the degrees less than b, ⟨b_{j}|j ∈ ω⟩ lists the degrees below b with representatives B_{j}, and G_{i,j} for 1 ≤ i ≤ n and j ∈ ω are mutually Cohen generics over B ∈ b in the sense of hyperarithmetic forcing of degrees g_{i} (for example the appropriate columns of a single generic). Now all of the sets {b_{j} ∨ g_{i,j}|j ∈ ω} = S_{i} and {g_{i,j}|j ∈ ω} = T_{i} are antichains in D_{h} and so definable as above as is U = {g_{1,j_{1}} ∨ … ∨ g_{n,j_{n}}| R(b_{j_{1}}, …, b_{j_{n}})}. Thus R(x_{1}, …, x_{n}) if and only if there are y_{i} ∈ T_{i} and z_{i} ∈ S_{i} such that the join of the y_{i} is in U and for each i, x_{i} ∨ y_{i} = z_{i}.

Thus we can definably quantify over all countable relations on D_{h}. In particular, we can definably describe a class of parameters that each define by some fixed scheme the standard model of arithmetic with a scheme for coding subsets of the model by degrees as well. This allows us to translate our proof of rigidity into biinterpretability. For any coding scheme for a model of arithmetic we can define a relation between degrees and codes of sets in such a model that associates degrees with sets of that degree. To be specific, we say that a degree x is associated with a set X coded in the model if for every set Y coded in the model there is a (partial) lattice isomorphic to L_{Y} in D_{h} with least element x if and only if (in the model) Y ≤_{h} X. As each L_{Y} is recursive in Y, it can be described in the model using the code for X and the apparatus of arithmetic in the model. The required images of L_{Y} in D_{h} and isomorphism between it and the version coded in the model of arithmetic can then be specified by other countable relations on the degrees of the model and ones above x and below some z representing the top of the lattice. Thus we have our direct proof of biinterpretability.

Theorem 5.1. (Slaman and Woodin) The structure D_{h} of the hyperdegrees is biinterpretable with second order arithmetic.

We close with a comment on another view of hyperarithmetic reducibility and its implications for some other degree structures.

We have mentioned two views of the hyperarithmetic sets. The first sees them as the sets recursive in 0^{(α)} for some recursive ordinal α. The second as the Δ_{1}^{1} sets. A third view sees them as the subsets of ω constructed in Gödel’s L before the first nonrecursive ordinal, ω_{1}^{CK}. In the last view, we see X as hyperarithmetic in Y if X ∈ L_{ω}_{1}^{Y} [Y], i.e. X is constructed before the first ordinal not recursive in Y with the use of a predicate for Y in the language. This view of ≤_{h} has a natural generalization when one sees ω_{1}^{CK} as the first Σ_{1} admissible ordinal and L_{ω}_{1}^{CK} as the least admissible set containing ω. The relativization sees L_{ω}_{1}^{Y} [Y] as the least Σ_{1} admissible set containing Y. The suggested reducibility generalizes Σ_{1} to Σ_{n} and we say that X ≤_{Σ_{n}} Y if X is a member of the least Σ_{n} admissible set containing Y. The associated degrees are called the Σ_{n}-admissible degrees in Slaman [1991]. As noted there, the methods of Slaman and Woodin carry over to these degrees as well. So do the ones presented here.

The notions of forcing to be considered are the same. The universes are now of the form L_{ω}_{n}^{X}[X] where ω_{n}^{X} is the first ordinal α such that L_{ω}_{n}^{X}[X] is Σ_{n} admissible. Cohen forcing in these settings has been considered in α-recursion theory. The crucial point for the forcing constructions is the preservation of Σ_{n} admissibility. Once this is established, the arguments for e.g. incomparability and infima requirements are the same. Discussions of the forcing and preservation of Σ_{n} admissibility can be found, for example, in Chong [1984] for n = 1 and for larger n in Shore [1974] albeit mixed in there with a more complicated priority argument. The essential ingredient for our decoding analysis was that the decoding of X (and so also X̄) was given by a formula which was Σ_{1} over the structure being considered and that X being Δ_{1} over the structure for Y guarantees that X is reducible to Y. (Note that if X is Δ_{1} over L_{ω}_{n}^{Y} [Y] then X ∈ L_{ω}_{n}^{Y} [Y] as even Σ_{1} admissibility gives a bound β on the witnesses needed to demonstrate that n ∈ X or n ∉ X for each n ∈ ω. We can then define X over L_{β}[Y] and so see that X ≤_{Σ_{n}} Y.) The formulas decoding n ∈ X (and n ∈ X̄) were all of the form that there are various sets reducible to a fixed set Z with properties described by positive formulas in the orderings. Each set Σ_{n}-reducible to Z is given simply by an ordinal less than ω_{n}^{Z} and the relations of one set being constructible from another by a given ordinal and an ordinal being Σ_{n} admissible relative to a given set are certainly Δ_{1} (over even any Σ_{1} admissible) in the sets and ordinals. Thus the decoding of X from an embedding of M_{X} produces a set Σ_{n}-reducible to the image of 1_{M_{X}} as required. Our forcing arguments then give a direct proof of the analogous results.

Theorem 5.2. (Slaman and Woodin) The structures of the Σ_{n}-degrees are for n > 1 are rigid and biinterpretable with second order arithmetic.

References

[1] Chong, C. T. [1984], Techniques of Admissible Recursion Theory, LNM 1106, Springer-Verlag, Berlin.

[2] Feferman, S. [1965], Some applications of the notion of forcing and generic sets, Fund. Math. 56, 325-45.

[3] Jockusch, C. G. Jr. and Shore, R. A. [1984], Pseudo-jump operators II: transfinite iterations, hierarchies and minimal covers, J. Symb. Logic 49, 1205-1236.

[4] Jónsson, B. On the representations of lattices, Math. Scand. 1, 193-206.

[5] Lerman, M. [1971], Initial segments of the degrees of unsolvability, Ann. Math. 93, 365-89.

[6] Lerman, M. [1983], Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin.

[7] MacIntyre, J. [1977], Transfinite extensions of Friedberg’s completeness criterion. J. Symb. Logic 42, 1–10.

[8] Sacks, G. E. [1990], Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin.

[9] Abraham, U. and Shore, R. A. [1986], The degrees of constructibility below a Cohen real, J. London Math. Soc. (3) 53 (1986), 193-208.

[10] Shore, R. A. [1974], Σ_{n} sets which are Δ_{n}-incomparable (uniformly), J. Symb. Logic 39 (1974), 295-304 [11] Shore, R. A. [1981], The theory of the degrees below 0′, J. London Math. Soc. (3)

24 (1981), 1-14.

[12] Shore, R. A. [1982], On homogeneity and definability in the first order theory of the Turing degrees, J. of Symb. Logic 47 (1982), 8-16.

[13] Shore, R. A. [1982a], Finitely generated codings and the degrees r.e. in a degree d, Proc. Am. Math. Soc. 84, 256-263.

[14] Shore, R. A. and Slaman, T. A. [2000], Defining the Turing jump, Math. Research Letters 6 (1999), 711-722.

[15] Slaman, T. A. [1991], Degree structures, in Proc. Int. Cong. Math., Kyoto 1990, Springer-Verlag, Tokyo, 303-316.

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

[17] Slaman, T. A. and Woodin, H. W. [2006], Definability in degree structures, this volume.