Lattice initial segments of the hyperdegrees

Richard A. Shore^{∗} Department of Mathematics

Cornell University Ithaca NY 14853

Bjørn Kjos-Hanssen^{†} Department of Mathematics University of Hawai‘i at Mānoa Honolulu HI 96822

March 29, 2009

Abstract

We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, D_{h}. In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of D_{h}. Corollaries include the decidability of the two quantifier theory of D_{h} and the undecidability of its three quantifier theory. The key tool in the proof is a new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of ω_{1}^{CK}. Somewhat surprisingly, the set theoretic analog of this forcing does not preserve ω_{1}. On the other hand, we construct countable lattices that are not isomorphic to any initial segment of D_{h}.

1 Introduction

Given a notion of relative computability or complexity ≤_{r} on sets A (of natural numbers) or functions f (from ω to ω) the corresponding degree structure D_{r} consists of the equivalence classes deg_{r}(A) (deg_{r}(f)) of mutually computable sets (functions) with the ordering induced by the given reducibility ≤_{r}. These classes are called the r-degrees. The classic example is Turing computability, Turing reducibility ≤_{T} and the Turing degrees but many others have been studied ranging from polynomial-time to constructibility.

∗Partially supported by NSF Grant DMS-0554855 and Grant 13408 from the John Templeton Foundation.

†Partially supported by NSF grant DMS-0652669.

The authors also thank the referee for suggestions that improved the presentation in several ways.

The first level of the scaffolding on which our understanding of such degree structures is built provides an analysis of the partial orders that can be embedded in them.

For the Turing degrees the story begins with Kleene and Post [1954] who proved that every countable partial order can be embedded in D_{T}. They used finite approximation methods that today would be called Cohen forcing in arithmetic. Stronger results about embedding uncountable partial orders were proven, for example, by Sacks [1963] but the full question of whether every partial order of size 2^{ℵ_{0}} with {x|x ≤ z} countable for every z can be embedded in D_{T} remains open. Nonetheless, the countable case is more than enough to decide all one quantifier sentences of ⟨D_{T} , ≤_{T} ⟩ as being true if and only if consistent with the axioms of partial orders.

The next level of analysis deals with extension of embedding questions such as density or minimality and, more generally, questions about when a given realization of a partial order in D_{r} can be extended to a specified larger partial order. In D_{T}, the long journey along this road began with Spector’s [1956] construction of a minimal degree. His method can be viewed as using full binary trees in place of finite characteristic functions for the approximations to the desired set. These methods were greatly extended by many researchers to embed more and more lattices as initial segments of D_{T}. We mention a few of the key steps: Lachlan [1968] showed that every countable distributive lattice is isomorphic to an initial segment of D_{T} (and so that its theory is undecidable); Lerman [1971] did the same for all finite lattices; Lachlan and Lebeuf [1976] for countable uppersemilattices (usls) and Abraham and Shore [1986] for all usls of size ℵ_{1}. (Groszek and Slaman [1983] show that it is consistent with ZFC that there are lattices of size ℵ_{2} ≤ 2^{ℵ_{0}} with {x|x ≤ z} countable for every z that can not be embedded in D_{T} as initial segments.) The embedding methods in the countable situations involve approximations by more and more complicated types of trees whose shape is tied to a series of representation theorems for (uppersemi)lattices. The uncountable ones need, in addition, some set theoretic techniques.

At this level of our scaffolding, Lerman’s [1971] result on embedding finite lattices shows that the three quantifier theory of D_{T} is undecidable (Schmerl, see Lerman [1983]). Coupled with the methods of Kleene and Post [1954], it also suffices to establish the decidability of the two quantifier theory of this structure (Shore [1978] and Lerman [1983, VII.4]). The case of countable recursive lattices suffices (Miller, Nies and Shore [2004]) to show the undecidability of the two quantifier theory in the language extended by symbols for both join and infimum with the understanding that the result applies to any total extension of the infimum relation on D_{T} which, by Kleene and Post [1954], is not a lattice. (This proof also supplies another one for the undecidability of the three quantifier theory in the language with just ≤_{T}.)

The same results on embedding as partial orderings and initial segments, and so the corresponding applications to the analysis of their theories, can be proved by quite analogous types of constructions (Cohen and perfect tree forcing) for a range of reducibilities from truth table to arithmetic, A ≤_{a} B ⇔ A ≤_{T} B^{(n)} for some n ∈ ω, (see e.g. Feferman [1965], Nerode and Shore [1980], Odifreddi [1983], M. Simpson [1985]). When one moves from the realm of recursion theory and the natural numbers to set theory and the ordinals, new issues arise.

If we look, for example, at relative constructibility (A ≤_{c} B ⇔ A ∈ L[B] for A, B ⊆ ω) and the constructibility degrees, D_{c}, of subsets of ω, we are faced with the new problem of preserving ω_{1} in our forcing extensions. For Cohen forcing this was part of Cohen’s seminal results and one can carry over (under suitable set theoretic hypotheses which we ignore here) the partial order embedding (Cohen [1966]) and related results to ≤_{c} with little difficulty (see, e.g. Balcar and Hajek [1978], Farrington [1983], [1984] and Abraham and Shore [1986a]). Our ability to preserve ω_{1} for perfect forcing is due to Sacks [1971] and is based on what he calls the fusion lemma. It enabled Sacks [1971] to prove the existence of a minimal degree of constructibility.

The next major steps towards determining the initial segments of D_{c} were taken by Adamowicz who proved first [1976] that all finite lattices can be embedded as initial segments of D_{c} and then [1977] that all countable constructible well founded usls can be so embedded. The extra assumptions Adamowicz needed for her proof turned out to be to some extent necessary. Abraham and Shore [1986a] showed that not every countable well founded distributive lattice is isomorphic to an initial segment of D_{c}. The crucial fact here is that the relation ≤_{c} is itself constructible and so one can get the result by coding nonconstructible sets in distributive lattices. Even if we restrict attention to constructible lattices, some remnants of the well-foundedness assumption remain necessary. Lubarsky [1987] proved that every countable lattice isomorphic to an initial segment of D_{c} is complete. On the positive side, the best results are those of Groszek and Shore [1988] that every countable (dual) algebraic lattice L (i.e. L is complete and generated by its compact elements x for which ∧I ≤ x implies that there is a finite F ⊆ I such that ∧F ≤ x, for every I ⊆ L) is isomorphic to an initial segment of D_{c}. (There is new interesting work, however, by Dorais [2007] on the c-degrees of subsets of ℵ_{1} produced by forcing with Souslin trees instead of countable perfect trees.)

Our concern in this paper is a reducibility and degree notion lying between that of arithmetic and constructible: the hyperarithmetic degrees D_{h}. For Turing reducibility and D_{T} and arithmetic reducibility and D_{a}, the setting is first order arithmetic and the natural numbers or ω. For set theory, we have relative constructibility and ω_{1}. Our setting is second order arithmetic and ω_{1}^{CK}, the first nonrecursive ordinal. It takes the place of ω_{1}, the first uncountable ordinal, as its effective analog. We say that A is hyperarithmetic in B, A ≤_{h} B, if A ≤_{T} B^{(α)} for some ordinal α < ω_{1}^{B}, i.e. the order type of α has a representative recursive in B. Here B^{(α)} is the α^{th} iterate of the Turing jump applied to B where effective (in B) unions are taken at limit levels . For another view, note that Kleene showed (see Sacks [1990, II.1-2]) that A ≤_{h} B if and only if A is Δ_{1}^{1}(B).

In this setting, Feferman [1965] (see also Sacks [1990]) introduced a ramified language for second order arithmetic and the appropriate notion of Cohen forcing. He proved (among other results) that every countable partial order is embeddable in D_{h} (even below the hyperarithmetic degree of Kleene’s O, the complete Π_{1}^{1} set). Some extensions and related results using Cohen forcing are in Thomason [1967] and [1969] and also Odifreddi [1983a]. The crucial fact needed is the preservation of ω_{1}^{CK}, i.e. if G is Cohen generic in this setting then ω_{1}^{G} = ω_{1}^{CK}. (This turns out to be equivalent to Δ_{1}^{1}-comprehension holding in the generic extension.)

One can also adapt perfect forcing to this setting to construct a minimal hyperdegree (Gandy and Sacks [1967] or with more detailed exposition and explanation Sacks [1971] or [1990]). Again the crucial issue is the preservation of ω_{1}^{CK} (or Δ_{1}^{1}-comprehension) by a fusion lemma (see §3 below). Here delicate definability issues and the theory of Π_{1}^{1} sets play a role not seen in either the arithmetic or set theoretic settings. In contrast to all the other degree structures discussed so far, almost nothing more has been known about initial segments of D_{h}.

Thomason [1970] proved that every finite distributive lattice is isomorphic to an initial segment of D_{h} and there matters stood. In his review of this paper, Sacks [1972] writes as follows:

“He raises a methodologically interesting open question: is every countable distributive lattice isomorphic to an initial segment of hyperdegrees? The answer (according to the reviewer) is probably yes, but (as the author points out) the method of the paper does not suffice to prove it.”

Now in 1970 Lerman’s methods for handling nondistributive lattices were not yet available but for the distributive ones there was as much available then as now. Thus the methodological issues were not about the initial segment constructions as used in D_{T} but rather about making the analog of the fusion lemma work in more general settings. Constructing embeddings of infinite lattices required (even in the later Turing degree constructions) imposing more and more restrictions on the trees as the construction progressed (often using finite approximations to the lattice to guide them). This type of forcing condition is not amenable to the arguments for the fusion lemma as the nature of the conditions change as more elements of the lattice are considered and so fusing an infinite sequence of such conditions produces a tree that is not a condition. The argument for the constructibility degrees gets around this problem by restricting attention to constructible lattices so that the entire lattice can be treated at once and so uses trees of a single shape just with branchings that grow to match the uniformly constructible approximations to the given lattice. One can then prove the set theoretic fusion lemma to preserve ω_{1} much as for binary trees.

This approach would work for the hyperdegrees as well but would be restricted to (dual) algebraic hyperarithmetical lattices and so, of course, it would not suffice to embed all the distributive lattices. Now for the constructibility degrees some such restrictions were necessary and not all countable distributive lattices (or even linear orders) are isomorphic to initial segments of D_{c}. This analogy makes it seem less likely that Sacks’s conjecture about the initial segments of D_{h} is true especially since all the available techniques seem to be quite similar.

One thus turns to finding counterexamples. The crucial fact used both in the first examples of distributive lattices not isomorphic to initial segments of D_{c} and in the later proofs of the necessity of completeness was that ≤_{c} is itself a constructible relation. For the Turing degrees, ≤_{T} is far from recursive: it is only a Σ_{3}^{0} relation. The hyperdegrees lie in between (in this sense as well) as ≤_{h} is a Π_{1}^{1} relation and so analogous to Σ_{1}^{0} or r.e. ones in the setting of the Turing degrees. (A ≤_{h} B if and only if both A and its complement are Π_{1}^{1} in B.) Thus the construction of even the basic counterexamples requires more delicacy. We here use the methods of finitely generated successor models introduced in Shore [1981] and used in the setting of D_{h} in Shore [2007], [2008] to prove Slaman and Woodin’s result that D_{h} is rigid and biinterpretable with second order arithmetic by purely degree theoretic arguments that work locally (in jump ideals) rather than just in D_{h} as a whole.

As every initial segment of D_{h} (or any of our degree structures) has a least element we assume that all (upper or lower semi)lattices have a least element 0. As we only consider countable lattices, we also consider only (upper or lower semi)lattices with a greatest element, 1, as well. We think of both 0 and 1 as named by constants in the language and so are preserved under substructures and extensions, even as upper or lower semilattices.

Theorem 1.1. Not every countable lattice is isomorphic to an initial segment of the hyperdegrees.

Proof. Shore [2007, §2] and [2008, §2-3] present a method for taking any set X and constructing a lattice L_{X} such that if f is an embedding of L_{X} into D_{h} then X ≤_{h} f(0_{L_{X}}). Thus if we take X to be, for example, Kleene’s O or any nonhyperarithmetic set, any embedding f of L_{X} as an initial segment of D_{h} would contradict the assumption that X is not hyperarithmetic.

We defer a more detailed explanation of this coding method to §6 where we need an elaboration for a finer result. For now it suffices to state that the lattices constructed contain finitely many elements which generate (using ∨ and ∧) a sequence of incomparable elements of type ω and other parameters that define the subsets of this sequence corresponding to X and its complement. Moreover, the recovery procedure producing X (and its complement) is positively Σ_{1}^{0} in the partial order relation and join operator of the lattice and so Π_{1}^{1} (and so Δ_{1}^{1}) in (by an additional trick) the bottom (and not just top) set of any embedding. Thus these lattices have two seemingly crucial properties that would lead to our contradiction if they could be realized as initial segments of D_{h}. The first is that the lattice is not hyperarithmetic. This is analogous to the first examples in D_{c} except that the coding is more delicate and survives ≤_{h} being only Π_{1}^{1} rather than hyperarithmetic. On the other hand, this same difference makes the direct coding methods into distributive lattices used for D_{c} unavailable in D_{h}. The second aspect of the argument is that the coding (of nonhyperarithmetic information) used here seems to rely on the fact that it is finitely generated as it uses the generators as parameters in the decoding. This type of coding cannot be carried out in distributive lattices as they are all locally finite lattices: every finite subset generates a finite sublattice. This obstacle to constructing counterexamples then revives the possibility of verifying Sacks’s conjecture for distributive lattices.

In fact, we prove that both of these properties (nonhyperarithmetic and not locally finite) are necessary for a countable lattice not to be isomorphic to an initial segment of D_{h}. Perhaps surprisingly, we provide a common generalization of a lattice being either hyperarithmetic or locally finite.

Theorem 1.2. Every sublattice K of any hyperarithmetic lattice L is isomorphic to an initial segment of the hyperdegrees. In fact, it can be realized as an initial segment with top a hyperdegree below that of O ⊕ K.

To see that this is indeed the desired common generalization we need to show that every countable locally finite lattice is isomorphic to a sublattice of a hyperarithmetic lattice.

Proposition 1.3. There is a recursive, universal, locally finite lattice, i.e. a recursive, locally finite lattice into which every countable, locally finite lattice can be embedded.

Proof. With the proper organization of the requirements, the standard Fraissé construction (as in Hodges [1993, 7.1.2] produces the desired lattice once one has the amalgamation property for the class of finite lattices.

Lemma 1.4. The class of finite lattices (with 0 and 1) has the amalgamation property, i.e. if A, B_{0} and B_{1} are finite lattices and f_{0}, f_{1} are embeddings of A into B_{0} and B_{1}, respectively, then there is a finite lattice C and embeddings g_{0} and g_{1} of B_{0} and B_{1}, respectively, into C such that g_{0}f_{0} ↾ A = g_{1}f_{1} ↾ A.

Proof. This should be a known fact but we have not found a reference to the precise form of the amalgamation property that we need. We supply a proof at the end of §5.

As we mentioned above, every distributive lattice is locally finite (this is well known and follows easily from the Stone Representation Theorem (see e.g. Grätzer [2003, p. 85]) that it is isomorphic to a ring of sets). Thus we have our answer to the original question of Thomason [1970] and Sacks [1972].

Corollary 1.5. Every countable locally finite and so, in particular, every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees.

These results also allow us to establish the same fine line between decidability and undecidability in the fragments of the theory of D_{h} as one has for D_{T}.

Theorem 1.6. The two quantifier theory of D_{h} is decidable while the three quantifier theory is undecidable as is the two quantifier theory in the language with both ∨ and ∧ where ∧ denotes any total extension of the infimum relation.

Proof. The proofs for the first two assertions in D_{T} (see Lerman [1983 VII.4, II.4.11 and A.2.9] although some minor corrections are needed) rely only on two facts. First, the structure is an usl with 0 in which all finite lattices can be embedded as initial segments. Second, it requires a Kleene-Post type extension of embedding theorem: Given any finite usl P extended as a partial order by a finite Q and any embedding of P into D_{T} there is an extension of the embedding to one of Q as long as Q respects the usl structure of P and has no new elements below any of those in P. Our results supply the first fact. Cohen forcing in the hyperarithmetic setting supplies the second. (The required extension of the given embedding can easily be constructed from a set of hyperdegrees independent over all the given degrees in the image of P as in the standard construction of an embedding of an arbitrary partial order. Such independent degrees are given by the columns of a Cohen generic set (in the hyperarithmetic sense) by relativizing Feferman [1965] to the top given degree.) The final undecidability result needs only that all recursive lattices are isomorphic to initial segments as in Miller, Nies and Shore [2003, Cor. 3.2].

The crucial aspect of our version of perfect trees (and associated forcing notion) that allows us to prove the required fusion lemma is a type of forgetfulness property (Proposition 3.2). We will use pairs consisting of trees T and a finite sublowersemilattice (slsl) K̂ of L. The shape of the tree is determined in advance by a type of sequential usl representation for L and the second component indicates the congruence relations that must be respected in all further refinements. (All these notions are made precise in §2.) What goes wrong in a naive attempt to transfer the methods of either D_{T} or D_{c} is the variation in the congruences that must be respected. Our forcing will have the property that if some condition forces a sentence of a certain form then the second component is irrelevant and so can be made the same in all the extensions needed in the fusion lemma. While this may seem unlikely, it is possible once one has proven a new lattice representation theorem (Theorem 5.1). Its construction takes into account various requirements for all sublattices at every step. The full lattice structure is exploited here by using a slsl decomposition of L and usl representations for the slsls. (The slsls are actually lattices as they are finite although with elements having possibly different joins than in all of L.)

While all of this could have been done in the setting of D_{T} (and actually gives some simplified proofs for various cases) no new theorems, of course, can be proven this way. On the other hand, given the known counterexamples in D_{c}, it is clear that the methods cannot carry over to that setting. Surprisingly, all the recursion theoretic arguments can be carried over and all the uses of fusion other than to preserve ω_{1}^{CK} can be avoided. (Those used to show that deciding each sentence is dense are, of course, unnecessary. Those to convert reductions to ones resembling Turing ones can be replaced by local Cohen forcing inside the tree parts of the conditions.) Thus it must be that the forcing notion in the set theoretic case analogous to ours, but using constructible trees instead of hyperarithmetic ones, fails to preserve ω_{1} despite the fact that ours preserves ω_{1}^{CK}.

Before beginning the detailed proofs of our results, we also want to make a comment on the coding methods used. While early results using codings in degree structures in general (and later ones for D_{c}) used distributive lattices, later stronger ones have all used nondistributive ones. It turns out that we now have a formal proof of the necessity of moving to nondistributive lattices to get the best results. While one can code arbitrary sets into distributive lattices (e.g. by the venerable lines and diamonds method) the decoding takes a number of quantifiers. In degree structures, however, while join is an effective operation (on indices) meet is not and requires extra quantifiers. Thus to get the best possible results one wants a coding for which the decoding is r.e. in only ≤ and ∨ (with only positive occurrences of ≤ as negative ones also add to the complexity). This is the type of coding used in the many applications of effective successor models from Shore [1981] to [2008]. As explicitly stated in Shore [2007] and [2008] one has a recursive sequence ϕ_{n} of positive Σ_{1} formulas in ≤ and ∨ such that given any set X there is a countable lattice L_{X} (even one recursive in X) such that n ∈ X ⇔ L_{X} ⊧ ϕ_{n}. Our results show that there is no such coding procedure in distributive lattices. Indeed, there is an X (actually the complement of O) such that there is no hyperarithmetic sequence ϕ_{n} of positive Σ_{1} formulas in ≤ and ∨ and no distributive (or even locally finite) countable lattice L_{X} such that n ∈ X ⇔ L_{X} ⊧ ϕ_{n}. To see this, suppose there were such an L. Take an embedding of L as an initial segment of D_{h} with top the degree of some G. As ≤_{h} and ∨ are Π_{1}^{1}(G) on (the indices of) the initial segment of D_{h} below deg_{h}(G), X, the complement of O would be Π_{1}^{1} in G and so O would be hyperarithmetic in G but the hyperdegrees below O do not form a lattice. On the other hand, our coding in Proposition 6.2 shows that there is a recursive sequence ϕ_{n} such that given any X we can find an usl K_{X} which is a susl of a locally finite lattice L_{X} (each recursive in X) such that n ∈ X ⇔ K_{X} ⊧ ϕ_{n}. In a slightly different vein, it seems that using the coding in distributive lattices found in Selivanov [1988] one can code arbitrary sets into distributive lattices in this way if one gives up the requirement that the sentences ϕ_{n} are positive. (Of course, this would increase the absolute complexity of the decoding procedure for D_{T} or D_{h}.)

Our plan now is to present the definitions of usl representations and our forcing notion in §2. We also prove some basic facts and state the representation theorem we need. The actual proof of the theorem we need is given in §5. The crucial fusion lemma is proven in §3 while the lemmas needed for the construction of our generic sequence and the verifications that it gives the desired initial segment of D_{h} are in §4. Finally, we close in §6 with a discussion of the situation for countable usl initial segments of D_{h} and various open questions.

2 Usl representations and the notion of forcing

We are given a hyperarithmetic lattice L and a sublattice K (both with the same 0 and 1). We begin our journey to the required notion of forcing with the definition of an uppersemilattice (usl) representation.

Definition 2.1. Let Θ be a set of maps from an usl L into ω. For α, β ∈ Θ and x ∈ L, we write α ≡_{x} β (α is congruent to β modulo x) if α(x) = β(x). We write α ≡_{x,y} β to indicate that α is congruent to β modulo both x and y and generally use commas conjunctively in this way. Such a Θ is an usl representation of L if it contains the function that is 0 on every input and for every α, β ∈ Θ and x, y, z ∈ L the following properties hold:

1. α(0) = 0.

2. (Differentiation) If x ≰ y then there are γ, δ ∈ Θ such that γ ≡_{y} δ but γ ≢_{x} δ.

3. (Order) If x ≤ y and α ≡_{y} β then α ≡_{x} β.

4. (Join) If x ∨ y = z and α ≡_{x,y} β then α ≡_{z} β.

Notation 2.2. If Θ is an usl representation for L and L̂ ⊆ L then we denote the restriction of Θ to L̂ by Θ ↾ L̂ = {α ↾ L̂|α ∈ Θ}. We also say that Θ is an extension of Θ ↾ L̂.

For those familiar with lattice representations as presented in lattice theory we note that these representations (with the additional requirements for infimum given below in Theorem 5.1 (2)) essentially correspond to ones of the dual lattice by equivalence relations. If the reader prefers to think in terms of equivalence relations on a set then the set is Θ, the relation that corresponds to x ∈ L is ≡_{x} and, for α ∈ Θ, its x-equivalence class is determined by α(x). A further reduction making the set Θ into one of natural numbers can be achieved by identifying the elements α of Θ with their values at the 1 of L (and so some natural number α(1)) as this uniquely determines all the values of α by the order property. However, we find the functional notation convenient for the construction of representations in §5.

Definition 2.3. If Θ′ and Θ are usl representations for L′ and L, respectively, L̂ ⊆ L′ ⊆ L and f : Θ′ → Θ, then f is an L̂-homomorphism if, for all α, β ∈ Θ′ and x ∈ L̂, α ≡_{x} β ⇒ f(α) ≡_{x} f(β).

In §5 we will prove the existence of a special type of representation for our given lattice L that we need to define our forcing conditions.

Theorem 5.1. If L is a countable lattice, then there is an usl representation Θ of L along with a nested sequence of finite slsls L_{i} starting with L_{0} = {0, 1} with union L and a nested sequence of finite subsets Θ_{i} with union Θ with both sequences recursive in L with the following properties:

1. For each i, Θ_{i} ↾ L_{i} is an usl representation of L_{i}.

2. There are meet interpolants for Θ_{i} in Θ_{i+1}, i.e. if α ≡_{z} β, x∧y = z (with α, β ∈ Θ_{i} and x, y, z ∈ L_{i}) then there are γ_{0}, γ_{1}, γ_{2} ∈ Θ_{i+1} such that α ≡_{x} γ_{0} ≡_{y} γ_{1} ≡_{x} γ_{2} ≡_{y} β.

3. For every sublowersemilattice L̂ of L_{i}, L̂ ⊆_{lsl} L_{i}, there are homogeneity interpolants for Θ_{i} with respect to L̂ in Θ_{i+1}, i.e. for every α_{0}, α_{1}, β_{0}, β_{1} ∈ Θ_{i} such that ∀w ∈ L̂(α_{0} ≡_{w} α_{1} → β_{0} ≡_{w} β_{1}), there are γ_{0}, γ_{1} ∈ Θ_{i+1} and L̂-homomorphisms f, g, h : Θ_{i} → Θ_{i+1} such that f : α_{0}, α_{1} ↦ β_{0}, γ_{1}, g : α_{0}, α_{1} ↦ γ_{0}, γ_{1} and h : α_{0}, α_{1} ↦ γ_{0}, β_{1}, i.e. f(α_{0}) = β_{0}, f(α_{1}) = γ_{1} etc.

We point out that the presentations in Lerman [1983] and Lachlan and Lebeuf [1976] are phrased in terms of there being only one element/two functions homogeneity interpolants instead of the two/three we required in our definition. One/two are not sufficient in general and two/three are used in the original proof for finite lattices in Lerman [1971] and ones of size ℵ_{1} in Abraham and Shore [1986]. In addition, we have changed the definition of homogeneity interpolants from the one used in Lerman [1971] and elsewhere in the literature by requiring that g : α_{0}, α_{1} ⟼ γ_{0}, γ_{1} (in place of γ_{1}, γ_{0}). This variation is a different special case than Lerman’s of a more general definition introduced in Kjos-Hanssen [2002], [2003]. (Kjos-Hanssen’s version allows a finite sequence of interpolants γ_{i} and functions f_{i} and is indifferent to order in that sense that it only requires that {f_{i}(α_{0}), f_{i}(α_{1})} = {γ_{i}, γ_{i+1}}.) Adopting our version does not make the construction of the required interpolants (Proposition 5.6) any more difficult but makes our construction of the crucial splitting trees in Proposition 4.7 considerably simpler than the previous ones. (The same simplification would carry over to D_{T} and other degree structures.) All the previous constructions proceed by using only susls and usl representations. We have mixed in the full lattice structure by requiring the decomposition of L to be into slsls instead while still using usl representations. We exploit the full lattice structure at various points in our construction. We will see, moreover, in §6 that this use of the meet structure of L is also necessary (in contrast to the situation in D_{T}). Given such L_{i} and Θ_{i} we next need to define the class of trees that will be eligible to be the first component of our forcing conditions. Each of our trees will be a function from finite strings to finite strings (of elements from the Θ_{i}) with various properties.

Definition 2.4. A tree T (for the sequence ⟨L_{i}, Θ_{i}⟩) is a hyperarithmetic function such that for some k ∈ ω its domain is the empty string ∅ and all strings in the Cartesian

product ∏_{n=0}^{n=m} Θ_{k+n} for each m ∈ ω. We denote this number k by k(T). Moreover, for each

σ ∈ dom T, T (σ) ∈ ∏_{n=0}^{n=q} Θ_{n} for some q ≥ |σ|−1. Moreover, T has the following properties

for all σ, τ ∈ dom T:

1. (Order) σ ⊆ τ ⇒ T (σ) ⊆ T (τ).

2. (Nonorder) σ|τ ⇒ T (σ)|T (τ). In fact, we specifically require that, for every σ ∈

∏_{n=0}^{n=m} Θ_{k+n} and α ∈ Θ_{k+m+1}, T (σˆ α) ⊇ T (σ)ˆ α. (We use | to denote incompatibility

of strings.)

3. (Uniformity) For every fixed length l there is, for each α ∈ Θ_{k+l}, a string ρ_{l,α} so that, for a given l, all the ρ_{l,α} are of the same length independently of α and if |σ| = l then T (σˆ α) = T (σ)ˆ ρ_{l,α}. (We use ˆ to denote concatenation and confuse a single symbol such as α with the string ⟨α⟩ of length one.) Note that by the nonorder property (2), for fixed l and α ≠ β, ρ_{l,α} ≠ ρ_{l,β}, in fact, by our specific requirement, ρ_{l,α}(0) = α.

Thus our trees T have branchings of width |Θ_{k(T)+n}| at level n and obey the usual order and uniformity properties of those used in Lerman [1983] to prove initial segment results for D_{T}. Our definition of S being a subtree of T incorporates the (technically convenient) requirement also used there that the branchings on S follow those on T. The structure of the representations plays no essential role on the range side of our trees and so, if desired, one could view our trees as maps into ω^{<ω} by replacing elements α of the representations by α(1), their values at top element of L, which determine α uniquely by the order property (3) of Definition 2.1.

Definition 2.5. We say that a tree S is a subtree of a tree T, S ⊆ T, if k(S) ≥ k(T) and (∀σ ∈ dom S)(∃τ ∈ dom T)[S(σ) = T (τ)]. Note that by our specific implementation of the nonorder property for trees (Definition 2.4(2)), we also have that (∀α ∈ Θ_{k(S)+|σ|})(S(σˆ α) ⊇ T (τˆ α)).

We note two useful facts that illuminate the structure of subtrees.

Lemma 2.6. If S is a subtree of T then

1. (∀α ∈ Θ_{k(S)+|σ|})(S(σˆ α) ⊇ T (τˆ α)) and

2. ∀l∃ρ_{l,α}∀σ, τ(|σ| = l & S(σ) = T (τ) → S(σˆ α) = T (τˆ ρ_{l,α}) for α ∈ Θ_{k(S)+l}.

Proof. The first fact follows immediately from our specific implementation of the nonorder property for trees (Definition 2.4(2)). The second follows from the uniformity requirements (3) of Definition 2.4 for S and T as well as property (2).

Transitivity of the subtree relation should be clear but a stronger claim is proven in Proposition 2.9. We mention some specific operations on trees that we will need later.

Definition 2.7. If T is a tree and σ ∈ dom T then T_{σ} is defined by T_{σ}(τ) = T (σˆ τ). Clearly, k(T_{σ}) = k(T) + |σ| and T_{σ} ⊆ T. Note that for σ ∈ dom T and τ ∈ dom T_{σ},

(T_{σ})_{τ} = T_{σˆ τ}. For a string μ ∈ ∏_{n=0}^{n=q} Θ_{n} with q ≤ |T (∅)| − 1, we let T^{μ} (the transfer tree

of T over μ) be the tree such that, for every σ ∈ dom T, T^{μ}(σ) is the string gotten from T (σ) by replacing its initial segment of length q + 1 (which is contained in T (∅)) by μ. We write T_{σ}^{μ} for (T_{σ})^{μ}. Finally, if T is a tree with k(T) = k and σ ∈ dom T then we let T_{σ}^{∗} = T_{σ} ↾ dom T. Clearly, k(T_{σ}^{∗}) = k(T) and T_{σ}^{∗} ⊆ T. Note that for σ ∈ dom T and τ ∈ dom T_{σ}^{∗}, (T_{σ}^{∗})_{τ}^{∗} = T_{σˆ τ}^{∗}.

A crucial notion for our constructions is that of preserving the congruences of specified slsls of our given lattice L.

Definition 2.8. If L̂ is a finite slsl of L we say that a subtree S of T preserves the congruences of L̂, S ⊆L̂ T, if L̂ ⊆ L_{k(T)} and, whenever x ∈ L̂, S(σ) = T (τ), α ≡_{x} β, S(σˆ α) = T (τˆ μ) and S(σˆ β) = T (τˆ ν), then μ ≡_{x} ν. Here α and β are members of the appropriate Θ_{i} and μ and ν are sequences (necessarily of the same length m) of elements from the appropriate Θ_{j}’s. We say that such sequences μ and ν are congruent modulo x, μ ≡_{x} ν, if μ(j) ≡_{x} ν(j) for each j < m.

Proposition 2.9. If R ⊆_{L_{1}} S ⊆_{L_{2}} T and then R ⊆_{L_{1}∩L_{2}} T.

Proof. To see that R ⊆ T note first that k(R) ≥ k(S) ≥ k(T). Next suppose that ρ ∈ dom R and α ∈ Θ_{k(R)+|ρ|}. As R ⊆ S we have a σ such that R(ρ) = S(σ) and R(ρˆ α) ⊇ S(σˆ α). As S ⊆ T we have a τ such that S(σ) = T (τ) and S(σˆ α) ⊇ T (τˆ α). Thus R(ρ) = T (τ) and R(ρˆ α) ⊇ T (τˆ α) as required. As for the preservation of L_{1} ∩ L_{2} congruences, suppose R(ρ) = S(σ) = T (τ), x ∈ L_{1} ∩ L_{2}, α_{0}, α_{1} ∈ Θ_{k(R)+|ρ|} and α_{0} ≡_{x} α_{1}. Let R(ρˆ α_{i}) = S(σˆ μ_{i}) = T (τˆ ν_{i}). As x ∈ L_{1} and R ⊆_{L_{1}} S, μ_{0} ≡_{x} μ_{1}. As x ∈ L_{2} and S ⊆_{L_{2}} T it then follows by induction on the (by uniformity, necessarily common) length of μ_{i} that ν_{0} ≡_{x} ν_{1} as required.

The details of this induction follow. Write ν_{i} = ν_{i}^{0}ˆ ⋯ ˆ ν_{i}^{s} where S(σˆ μ_{i}(0) ⋯ ˆ μ_{i}(t)) = T (τˆ ν_{i}^{0} ^{ˆ ···}ˆ ν_{i}^{t}). Then inductively μ_{0}(j) ≡_{x} μ_{1}(j) gives ν_{0}^{j} ≡_{x} ν_{1}^{j}. For j = 0 this follows directly from Definition 2.8. For the inductive step, consider, without loss of generality, the case j = 1. We have S(σˆ μ_{0}(0)ˆ μ_{0}(1)) = T (τˆ ν_{0}^{0}ˆ ν_{0}^{1}) and S(σˆ μ_{1}(0)ˆ μ_{1}(1)) = T (τˆ ν_{1}^{0}ˆ ν_{1}^{1}). Consider S(σˆ μ_{0}(0)ˆ μ_{1}(1)) = T (τˆ ν_{0}^{0}ˆ ν) for some ν. By the uniformity clause (3) of Definition 2.4, there is a ζ such that S(σˆ μ_{0}(0)ˆ μ_{1}(1)) = S(σˆ μ_{0}(0))ˆ ζ and S(σˆ μ_{1}(0)ˆ μ_{1}(1)) = S(σˆ μ_{1}(0))ˆ ζ. Thus T (τˆ ν_{0}^{0}ˆ ν) = T (τˆ ν_{0}^{0})ˆ ζ and T (τˆ ν_{1}^{0}ˆ ν_{1}^{1}) = T (τˆ ν_{1}^{0})ˆ ζ. Again, by the uniformity clause and the uniqueness of the ρ_{l,α} there (iterated |ν| times), ν = ν_{1}^{1}. Finally, by Definition 2.8 again, ν ≡_{x} ν_{0}^{1} as μ_{1}(1) ≡_{x} μ_{0}(1) and so ν_{1}^{1} ≡_{x} ν_{0}^{1} as required.

Definition 2.10. Recall that K is an arbitrary sublattice of L (preserving 0 and 1). Our notion of forcing P_{⟨L_{i},Θ_{i}⟩,K} = P is given first by letting the forcing conditions P be the pairs ⟨T, K̂⟩ where T is a tree for ⟨L_{i}, Θ_{i}⟩ and K̂ is a finite slsl of K ∩ L_{k(T)}. We then say that ⟨T_{1}, K_{1}⟩ extends or refines ⟨T_{0}, K_{0}⟩, ⟨T_{1}, K_{1}⟩ ≤_{P} ⟨T_{0}, K_{0}⟩ if T_{1} ⊆_{K_{0}} T_{0} and K_{1} ⊇ K_{0}. If P = ⟨T, K̂⟩ is a condition we let K(P) = K̂, T r(P) = T and k(P) = k(T). If the notion of forcing is fixed in some context we will often omit the subscript P in ≤_{P}. We sometimes abuse notation by identifying a condition P with T r(P) when K(P) is fixed.

Along these lines, for example, we use P_{σ}, P_{σ}^{∗}, P^{τ} and P_{σ}^{τ} to stand for ⟨T r(P)_{σ}, K(P)⟩, ⟨T r(P)_{σ}^{∗}, K(P)⟩, ⟨T r(P)^{τ}, K(P)⟩ and ⟨T r(P)_{σ}^{τ}, K(P)⟩, respectively. The top element of P consists of the identity tree Id (which has k(Id) = 0) and the slsl L_{0} = {0, 1}.

Lemma 2.11. If T is a tree, σ ∈ dom T and L̂ ⊆ L_{k(T)}, then T_{σ} ⊆L̂ T. So if P = ⟨T, K̂⟩ is a condition, then ⟨T_{σ}, K̂⟩ ≤_{P} ⟨T, K̂⟩ (by letting L̂ = K̂). If σ, τ ∈ dom T are of the same length and ⟨S, K̂⟩ ≤ ⟨T_{σ}, K̂⟩ then ⟨S^{T (τ)}, K̂⟩ ≤_{P} ⟨T_{τ}, K̂⟩. We also have that T_{σ}^{T (τ)} = T_{τ}.

Proof. The first assertions follow directly from the definitions. The last two follow from the uniformity assumption on our trees.

It is easy to see that with trivial genericity requirements any generic filter G determines

a function G ∈ ∏_{n=0}^{∞} Θ_{n} , i.e. a function on ω with G(n) ∈ Θ_{n}. (G = ⋃{T (∅)|T is

the first component of some condition in G}.) On this basis we could naively try to define our embedding of K into the hyperdegrees as follows. For x ∈ K ⊆ L we let G_{x} : ω → ω be defined by G_{x}(n) = G(n)(x). (As G(n) ∈ Θ_{n} ⊆ Θ it is a map from L into ω.) The desired image of x would then be deg_{h}(G_{x}). Now the order and join properties of usl representations guarantee that this embedding preserves order and join (on all of L even). If x ≤ y then by the order property we can (recursively in the hyperarithmetic representation ⟨Θ_{i}⟩) calculate G_{x}(m) from G_{y}(m) by finding any α ∈ Θ_{m} with α(y) = G_{y}(m) and declaring that G_{x}(m) = α(x). (Such an α exists since G(m) is one.) Similarly if x ∨ y = z then, by the join property, we can calculate G_{z}(m) from G_{x}(m) and G_{y}(m) by finding any α ∈ Θ_{m} such that α(x) = G_{x}(m) and α(y) = G_{y}(m) and declaring that G_{z}(m) = α(z). (Again G(m) is such an α.)

Were congruences modulo x always preserved for every x, we could directly carry out the diagonalization and other requirements as well for this definition of G_{x}. (Of course, we cannot allow this to happen as it would produce an embedding of all of L as an initial segment of D_{h} in place of the one wanted of K.) In actuality, not all congruences are preserved as we refine to various subtrees in our construction. Thus we must modify the definition of the images in D_{h} and provide nice representations of the hyperdegrees corresponding to x. To that end we introduce some dense sets that our generic must meet.

Lemma 2.12. For each x ∈ K and k ∈ ω the sets {P |x ∈ K(P)} and {P |k(P) ≥ k} are dense.

Proof. Consider any Q ∈ P, x ∈ K and k ∈ ω. Let K′ be the slsl of K generated by K(Q) and x and let i ≥ k(Q), k be such that K′ ⊆ L_{i}. Define S with k(S) = i by S(σ) = T r(Q)(0^{i−k(Q)}ˆ σ). Clearly, ⟨S, K′⟩ ≤_{P} Q and is in both required sets.

From now on assume that any generic filter G we consider meets the dense sets of Lemma 2.12. They suffice to define our generic G as above. More crucially, they allow us to define nice representatives of the desired images of x in D_{h}.

Definition 2.13. If G is a generic filter meeting the dense sets of Lemma 2.12, G the cor-

responding element of ∏_{n=0}^{∞} Θ_{n}, P ∈ G and x ∈ K(P) then G^{P} is the sequence ⟨α_{n}|n ∈ ω⟩

where T r(P)(⟨α_{n}|n < m⟩) ⊆ G for every m. (Thus ⟨α_{n}⟩ is the path that G follows in the domain of T r(P). In particular, G = G^{Id}. It is obvious from the definitions that G is a path on (i.e. in the range of) T r(Q) for every Q ∈ G.) We define G_{x}^{P} (n) as α_{n}(x). (In the parlance of Lachlan and Lebeuf [1976], G^{P} is the signature of G on T r(P).)

The crucial point is that the hyperdegree of G_{x}^{P} does not depend on P.

Lemma 2.14. If x ∈ K(P), K(Q) for P, Q in a generic G, then G_{x}^{P} ≡_{h} G_{x}^{Q}.

Proof. As there is an R ≤ P, Q in G by the compatibility of all conditions in a generic filter, it suffices to consider the case that Q ≤ P. Let G^{P} = ⟨α_{n}⟩ and G^{Q} = ⟨β_{n}⟩. By the definition of subtree there is for each n an m(n) such that T r(Q)(⟨β_{s}|s < n⟩) = T r(P)(⟨α_{s}|s < m(n)⟩) and we can compute the function m recursively in the trees. (By the uniformity of the trees, there is, for each n, a unique m(n) such that |T r(Q)(σ)| = |T r(P)(τ)| for every σ of length n and every τ of length m(n).) Moreover, by our definition of subtree, β_{n} = α_{m(n)}. Thus G_{x}^{Q}(n) = β_{n}(x) = α_{m(n)}(x) = G_{x}^{P} (m(n)) and so G_{x}^{Q} ≤_{h} G_{x}^{P}. The other direction depends on the congruence preservations for x implied by T r(Q) ⊆_{K(P)} T r(P).

Suppose that we have, by a hyperarithmetic recursion, determined G_{x}^{P} (i) = α_{i}(x) for i ≤ m(n). The next step followed by G in Q is β_{n+1} = α_{m(n)+1}. It corresponds to the sequence ⟨α_{i}|m(n) + 1 ≤ i < m(n + 1)⟩. The definition of ⊆_{K(P)} implies that ⟨α_{i}(x)|m(n) + 1 ≤ i < m(n + 1)⟩ is uniquely determined by β_{n+1}(x) to continue the recursion.

Thus given a generic G we can define a map from K into D_{h} by sending x ∈ K to deg_{h}(G_{x}^{P}) for any P ∈ G with x ∈ K(P). Our naive proofs of the preservation of order and join can now be made precise by simply applying them to G^{P} on T r(P) (in place of G on Id) for any P ∈ G with x, y, z ∈ K(P).

Now we must define, analyze and exploit our forcing language and relation to prove that the embedding corresponding to a sufficiently generic G preserves nonorder and produces an initial segment of the hyperdegrees.

We proceed essentially as for (perfect) forcing with binary trees in Sacks [1990, IV.4]. Our base structure (model) is formally the ramified analytic hierarchy up to ω_{1}^{CK} (Church-Kleene ω_{1}, the first nonrecursive ordinal) which we denote by M. This is the analog of L_{ω}_{1}^{CK} where the language and definitions are set in second order arithmetic instead of set theory. The sets in the structure are, however, just those subsets of ω that appear in L_{ω}_{1}^{CK} or equivalently the hyperarithmetic ones. Our forcing extension will be M(ω_{1}^{CK}, G) which is defined analogously to L_{ω}_{1}^{CK}[G]. If ω_{1}^{G}, the least ordinal not recursive in G, is ω_{1}^{CK} (as will be the case for generic G) then the sets in M(ω_{1}^{CK}, G) are precisely those hyperarithmetic in G. To define and describe the model and forcing relation we have a ramified forcing language as introduced in Feferman [1965] and described in Sacks [1990, III.4] with a term G for the function G (in place of T and the set T) to describe this structure and define the forcing relation. (We are thinking of everything as coded in second order arithmetic.) In addition to the usual paraphernalia of second order arithmetic, the language has ranked set variables X^{ζ} for ordinals ζ < ω_{1}^{CK} which range over the sets constructed by level ζ in M(ω_{1}^{CK}, G). A formula is ranked if all its set variables are ranked. We refer to Sacks [1990, III.4] for the simultaneous recursive definitions of the sets M(ζ, G)), interpretations of terms x̂H(x) for the set of numbers satisfying the ranked formula H and for the truth of ranked and unranked formulas in the structure M(ω_{1}^{CK}, G). The definitions proceed through inductions on a reasonably defined notion of “full ordinal rank” of a formula. Sacks also provides an analysis of the complexity of the satisfaction relation for ranked (and unranked) formulas. Of course, unranked formulas are interpreted as having their unranked variables ranging over all of M(ω_{1}^{CK}, G). As the change from his setting to ours is purely notational, going from a set (element

of 2^{ω}) to a function in ∏_{n=0}^{∞} Θ_{n}, the development there carries over with only notational

changes.

The crucial starting point of the definition of the forcing is that ⟨T, K̂⟩ ⊩ F for a ranked formula F if and only if M(ω_{1}^{CK}, G) ⊧ F for every G ∈ [T] (the paths through T). The relation is then defined on the unranked formulas by induction on the usual complexity of formulas. The clauses for conjunction and negation are standard: P ⊩ F ∧ H ⇔ P ⊩ F and P ⊩ H; P ⊩ ¬F ⇔ (∀Q ≤ P)(Q ⊮ F). There are three cases for the existential quantifiers: P ⊩ ∃xF(x) ⇔ P ⊩ F(\underline{n}) for some numeral \underline{n}; P ⊩ ∃X^{ζ}F(X^{ζ}) for ζ < ω_{1}^{CK} ⇔ P ⊩ F(x̂H(x)) for some H of rank at most ζ; P ⊩ ∃XF(X) ⇔ P ⊩ ∃X^{ζ}F(X^{ζ}) for some ζ < ω_{1}^{CK}.

The key complexity theoretic fact from Sacks [1990, IV.4] is that when restricted to conditions P with a fixed K(P) and Σ_{1}^{1} sentences F (those with initial unranked existential set quantifiers followed by a ranked formula), the forcing relation P ⊩ F is a Π_{1}^{1} relation uniformly in K(P). This fact is again established quite abstractly and is still true by the same simple argument for our new definition of forcing conditions. The crucial property of perfect forcing in Sacks [1990] that now allows one to prove that for generic G forcing equals truth and ω_{1}^{CK} is preserved (i.e. ω_{1}^{G} = ω_{1}^{CK}) is the fusion lemma to which we now turn.

3 The fusion lemma

We can view the problem of preserving ω_{1}^{CK} as preserving admissibility in L_{ω}_{1}^{CK} when we add on the new function G. From this point of view, we want to preserve Σ_{1} replacement, i.e. L_{ω}_{1}^{CK}[G] ⊧ ∀n ∈ ω∃Xφ(n, X) → ∃X∀n ∈ ω(φ(n, X^{[n]}). Translated into our setting of second order arithmetic and M(ω_{1}^{CK}, G) this is equivalent to preserving Δ_{1}^{1}-comprehension. The key in either case is what is called the fusion lemma. It it is a natural step from the replacement version when one replaces satisfaction by forcing and wants to prove that one can densely decide sentences of the desired form (as is needed to show the usual equivalence between forcing and truth).

Lemma 3.1 (Fusion). Let P = ⟨T, K̂⟩ be a forcing condition and ∃X̄_{n}F_{n}(X̄_{n}) a hyperarithmetic sequence of Σ_{1}^{1} sentences with their unranked quantifiers displayed such that ∀n∀Q ≤ P ∃R ≤ Q[R ⊩ ∃X̄_{n}F_{n}(X̄_{n})]. Then there is a Q ≤ P, and even one with k(Q) = k(P) and K(Q) = K(P), such that ∀n(Q ⊩ ∃X̄_{n}F_{n}(X̄_{n})). Moreover, there is a ζ < ω_{1}^{CK} such that ∀n(Q ⊩ ∃X̄_{n}^{ζ}F_{n}(X̄_{n}^{ζ})).

Now what goes wrong with an attempted proof of this theorem if we use some standard type of sequential representations Θ_{i} for L_{i} and the associated trees? When we try to prove the fusion lemma, we thin out our given tree (above each node successively) and get conditions that are trees for Θ_{i} for larger and larger i as we treat each F_{n} in turn. As the trees are of different shapes for each i and the representations not nicely nested, there is no way to combine (fuse) the subtrees into the single condition Q required. The first crucial property of our representation is that it allows us to use trees that are essentially (i.e. eventually) of the same shape with splittings for a cofinal segment of the Θ_{i}. (Our construction of the required nested representations in §5 relies on the fact that the L_{i} are slsls of L and so preserve infimum.) We now turn to the basic lemma that conveys the other technical facts about our notion of forcing that enables us to overcome this problem. It was for this application that our lattice representation theorem (Theorem 5.1) was designed.

Proposition 3.2. If ⟨T_{1}, K_{1}⟩ ≤_{P} ⟨T_{0}, K_{0}⟩ then ⟨T_{1}, K_{0}⟩ ≤_{P} ⟨T_{0}, K_{0}⟩. Moreover, we can get an S with [S] ⊆ [T_{1}] such that k(S) = k(T_{0}) and ⟨S, K_{0}⟩ ≤_{P} ⟨T_{0}, K_{0}⟩. Thus, if F is a ranked formula, P is a condition, Q ≤ P and Q ⊩ F, then there is an R ≤ P such that R ⊩ F, k(R) = k(P) and K(R) = K(P).

Proof. That ⟨T_{1}, K_{0}⟩ ≤_{P} ⟨T_{0}, K_{0}⟩ is clear from the definition of extension. The required S is simply T_{1} ↾ dom T_{0}. So for every σ in its domain S(σ) = T_{1}(σ). It is then clear that [S] ⊆ [T_{1}], k(S) = k(T_{0}) and ⟨S, K_{0}⟩ ≤_{P} ⟨T_{0}, K_{0}⟩ as required. Now if Q ≤ P and Q ⊩ F with F ranked then this argument gives us an R ≤ P with [R] ⊆ [Q], k(R) = k(P) and K(R) = K(P). As F is ranked and Q ⊩ F, [R] ⊆ [Q] implies that R ⊩ F as well by the definition of forcing for ranked sentences.

For those familiar with the proof of the fusion lemma in other settings, we note how our special representation allows us to avoid changing the shape of the trees or increasing the slsl K̂ with respect to which we are preserving congruences. The point is that when we have some condition P = ⟨T_{0}, K_{0}⟩ and ask if there is any Q = ⟨T_{1}, K_{1}⟩ extending P that forces some ranked formula F we can restrict ourselves to those with k(T_{1}) = k(T_{0}) and K_{1} = K_{0} by Proposition 3.2. This idea is really the only new one needed to carry out the proof of the fusion lemma.

Proof of Fusion Lemma. As when K(P) is fixed, the forcing relation for Σ_{1}^{1} sentences is Π_{1}^{1} and extension is arithmetic by definition, the relation R ≤ Q & k(R) = k(P) & K(R) = K(P) & R ⊩ ∃X̄_{n}F_{n}(X̄_{n}) is Π_{1}^{1} and it can be uniformized to a partial Π_{1}^{1} function R(n, Q) by Kreisel uniformization (Sacks [1990 II.2.6]). Our hypothesis and Proposition 3.2 together imply that R is defined for every ⟨n, Q⟩ with Q ≤ P and K(Q) = K(P). We now define a tree S by recursion so that ⟨S, K̂⟩ is the forcing condition required in the Lemma. In fact, along with the definition of S(σ) by induction on the length n of σ we define an auxiliary sequence of conditions ⟨U_{n,i}, K̂⟩ ≤ P with k(U_{n,i}) = k(P) and |U_{n,i}(∅)| = |S(σ)| (which depends only on n by uniformity) for i ≤ m(n) where m(n) is one less than the number of branches on T at level n. Indeed we will have that ⟨U_{n,i}^{T (σ)}, K̂⟩ ≤ P for each σ of length n. (Recall Definition 2.7 and Lemma 2.11.) We begin with S(∅) = T (∅). Suppose we have defined S(σ) for all σ with length n and have the corresponding U_{n,m(n)}. For any σ of length n and any appropriate α we let S(σˆ α) = U_{n,m(n)}^{S(σ)}(0^{n}ˆ α). Thus S (up to this level) is clearly uniform and a subtree of T that preserves the congruences in K̂. Note that we have now defined S(σ) for all σ of length n + 1 and have intuitively thinned out the still possible nodes above each such σ to a subtree of U_{n,m(n)}. Before defining the next level of S, we further thin them out to force the values at n + 1 while (by an iterated nesting procedure) still maintaining uniformity across the level. To do this, we define the U_{n+1,i} for i ≤ m(n + 1) by induction on i. We begin with σ_{0} = ρˆ α (for some ρ of length n and some α in the appropriate Θ_{j}). We let U_{n+1,0} be the first component of R(n + 1, (U_{n,m(n)})_{0^{n}ˆ α}^{S(σ_{0})}). Given U_{n+1,i} and σ_{i+1} we let U_{n+1,i+1} be the first component of R(n + 1, U_{n+1,i}^{S(σ_{i})}). (So, by induction, ⟨U_{n+1,i}, K̂⟩ ≤ P and ⟨U_{n+1,i}, K̂⟩ ⊩ F_{n+1}.) This completes the inductive definition of the U_{n+1,i} and so of S. The crucial fact about S is that for each n and σ of length n every path on S that contains S(σ) is a path on U_{n,i} for some i and so makes F_{n} true by our choice of U_{n,i} as the first component of R(n, U) for some U with ⟨U, K̂⟩ ≤ P. Thus F_{n} is true of every path on S for every n, i.e. ∀n(⟨S, K̂⟩ ⊩ F_{n}).

Given the fusion lemma for our forcing, the remaining development of the basic facts about our forcing is routine and follows Sacks [1990, IV.4]. In particular, essentially the same proofs show first that for every P and F there is a Q ≤ P that decides F, i.e. Q ⊩ F or Q ⊩ ¬F and then that for any generic filter G (i.e. one such that for every F there is a P ∈ G that decides F) forcing equals truth in the sense that, for every F, M(ω_{1}^{CK}, G) ⊧ F ⇔ (∃P ∈ G)(P ⊩ F).

In addition to meeting the dense sets of conditions deciding each F, we explicitly meet certain other sets of conditions to assure that we can define our embedding on all of K and show that it is a one-one map onto the hyperdegrees below that of the generic G = G^{Id} ≡_{h} G^{P} ≡_{h} G_{1}^{P} for any P in the generic filter.

4 Initial segment verifications

To simplify our notation for the sets hyperarithmetic in G, i.e. those in M(ω_{1}^{CK}, G), and to emphasize the analogy to the Turing degree constructions of initial segments, we number the terms x̂H of our language by ordinals δ < ω_{1}^{CK} and denote the characteristic function of the set they stand for by {δ}^{G}. (Note that, in contrast to the situation with Turing reductions, these are all total functions but, of course, the list is only recursive in O.) We at times use δ_{x}^{P} to name the reduction such that {δ_{x}^{P} }^{G} = {δ}^{G_{x}^{P}}.

To assure that our embedding preserves nonorder we want to show for any x ≰ y in K, condition P with x, y ∈ K(P) and δ < ω_{1}^{CK}, that {Q|Q ⊩ {δ_{y}^{P} }^{G} ≠ G_{x}^{P} } is dense below P. In addition we want to show that {Q|∃x ∈ K(Q ⊩ {δ}^{G} ≡_{h} G_{x}^{Q})} is also dense for each δ. These two results would then finish the proof of our theorem. We begin with an auxiliary collection of dense sets that make our task much simpler. They correspond to the total subtrees of Lerman [1983] and allow us to convert the arguments for D_{T} to our setting of D_{h}.

Definition 4.1. A condition Q decides {δ}^{G} via q (a map into {0, 1}), if, for every x and σ ∈ dom Q of length x, Q_{σ} ⊩ \{δ\}^{G}(x) = \underline{q(x, σ)}.

Lemma 4.2. If Q decides {δ}^{G} via q then q is hyperarithmetic.

Proof. This follows immediately from the fact that the relevant instances of the forcing are uniformly Π_{1}^{1}.

Lemma 4.3 (Totality). For each condition P and δ < ω_{1}^{CK} there is a Q ≤ P which decides {δ}^{G}.

Proof. For any Q ≤ P and any m there is clearly an R ≤ Q and an n ∈ {0, 1} for which R ⊩ \{δ\}^{G}(\underline{m}) = \underline{n}. (Otherwise by the density of deciding formulas we could find R_{1} ≤ R_{0} ≤ Q such that R_{n} ⊩ \{δ\}^{G}(\underline{m}) ≠ \underline{n} (for n = 0, 1) contradicting one of the basic facts about forcing.) Now applying the construction of the fusion lemma, with the Π_{1}^{1} operator taking m, Q to such an R (and n) for the nodes at level m, gives the desired condition.

Proposition 4.4 (Diagonalization). For any x ≰ y in K, δ < ω_{1}^{CK} and condition P with x, y ∈ K(P), there is an R ≤ P such that R ⊩ {δ_{y}^{P} }^{G} ≠ G_{x}^{P}.

Proof. We begin by taking a Q ≤ P which decides {δ_{y}^{P} }^{G} by Lemma 4.3. We then choose any α_{0}, α_{1} ∈ Θ_{k(P)} such that α_{0} ≡_{y} α_{1} but α_{0} ≢_{x} α_{1}. Such α_{0} and α_{1} exist by the differentiation property of usl representations. Suppose T r(Q)(∅) = T r(P)(σ) and so T r(Q)(α_{i}) ⊇ T r(P)(σˆ α_{i}) for i ∈ {0, 1}. Now clearly any condition Q_{i} ≤ Q_{α_{i}} forces G_{x}^{P} (|σ|) = α_{i}(x). Let β_{i} = (α_{i})^{|σ|}, i.e. the concatenation of |σ| many copies of α_{i}. Consider then the conditions Q_{β_{i}}. They still force G_{x}^{P} (|σ|) = α_{i}(x). On the other hand by Lemma 4.3 they each force a value for {δ_{y}^{P} }^{G} at |σ|.

As the β_{i}, for i = 0, 1, are congruent modulo y and y ∈ K(P), the initial segments of G_{y}^{P} that Q_{β_{i}}(∅) determine are congruent modulo y as well. If G is any path through Q_{β_{0}} then (by uniformity of T r(Q)) changing its initial segment Q_{β_{0}}(∅) to Q_{β_{1}}(∅) produces a path G′ through Q_{β_{1}} and so a corresponding one through T r(P) that is congruent to G^{P} modulo y. As the value of {δ}^{G_{y}^{P}} = {δ_{y}^{P} }^{G} is determined by G_{y}^{P} the two conditions must force the same value for {δ}^{G_{y}^{P}} (|σ|). This value must be different from one of α_{i}(x) = 0, 1. Thus one of the Q_{β_{i}} extends Q (and so P) and forces {δ}^{G_{y}^{P}} = {δ_{y}^{P} }^{G} ≠ G_{x}^{P} as required.

We turn now to the requirement that the image of K under our embedding form an initial segment of D_{h}. This argument is somewhat more complicated than those above and uses both the meet and homogeneity interpolants. Still, given Lemma 4.3, we present an argument that would work for D_{T} as well. In that setting it would be simpler than the existing proofs in the literature because of our changes to the definition of the homogeneity interpolants.

We begin with the notion of a δ-splitting and a lemma about such splittings.

Definition 4.5. Given a reduction δ and a condition Q that decides {δ}^{G} via q (and a w ∈ K(Q)), we say that σ and τ (of the same length) are a δ-splitting (or δ-split) on Q (modulo w) if (σ ≡_{w} τ and) there is an n ≤ |σ| such that q(n, σ ↾ n) ≠ q(n, τ ↾ n). (So for any paths G_{0} and G_{1} on Q extending T r(Q)(σ) and T r(Q)(τ), respectively, {δ}^{G_{0}}(n) ≠ {δ}^{G_{1}}(n).) If R ≤ Q, R(μ) = Q(σ), R(ν) = Q(τ) and σ and τ δ-split (modulo w) on Q then we also say that μ and ν δ-split on R (modulo w).

Lemma 4.6. Given a reduction δ and a condition Q that decides {δ}^{G}, there is a ρ ∈ dom Q such that the set Sp(ρ) = {w ∈ K(Q)| there are no σ, τ that δ-split on Q_{ρ}^{∗} modulo w} is maximal. Moreover, this maximal set is closed under meet and so has a least element z.

Proof. Let k = k(Q) = k(P) and K̂ = K(P) = K(Q). As K̂ is finite there is clearly a ρ such that Sp(ρ) is maximal. Note that then Sp(μ) = Sp(ρ) for any μ ⊇ ρ with μ\ρ ∈ dom T r(Q)_{ρ}^{∗} as T r(Q)_{μ}^{∗} ⊆K̂ T r(Q)_{ρ}^{∗}. Consider any x, y ∈ Sp(ρ) with x ∧ y = w. As K̂ ⊆_{lsl} L, w ∈ K̂. To show that Sp(ρ) is closed under meet it suffices (by the maximality of Sp(ρ)) to show that there is no δ-splitting on Q_{ρˆ 0}^{∗} modulo w. Remember that, by definition, k = k(Q_{ρˆ 0}^{∗}) = k(Q_{ρ}^{∗}) = k(Q). Suppose there were such a split μ̄ and ν̄ which

we may take to be of the same length m. By our definition of Q_{ρˆ 0}^{∗}, μ̄, ν̄ ∈ ∏_{n=0}^{n=m} Θ_{k+n} . In

Q_{ρ}^{∗} at the corresponding levels, however, there are branchings for all elements of Θ_{k+n+1}. (That is there are, for example, successors of T r(Q_{ρ}^{∗})(0ˆ μ ↾ n + 1) for every element of Θ_{k+n+1} while in T r(Q_{ρ}^{∗})(μ ↾ n+1) there are ones only for the elements of Θ_{k+n}.) Thus, by

the existence of meet interpolants for Θ_{k+n} in Θ_{k+n+1}, there are γ̄_{0}, γ̄_{1}, γ̄_{2} ∈ ∏_{n=0}^{n=m} Θ_{k+n+1}

such that for each j ≤ m, the γ̄_{i}(j) for i ∈ {0, 1, 2} are meet interpolants for μ̄(j) and ν̄(j), i.e. μ̄ ≡_{x} γ̄_{0} ≡_{y} γ̄_{1} ≡_{x} γ̄_{2} ≡_{y} ν̄. As μ̄ and ν̄ form a δ-splitting on Q_{ρˆ 0}^{∗} so do one of the successive pairs such as 0 ˆ γ̄_{0}, 0 ˆ γ̄_{1} on Q_{ρ}^{∗}. But then 0 ˆ γ̄_{0} and 0 ˆ γ̄_{1} would be a δ-split on Q_{ρ}^{∗} congruent modulo y for a contradiction. (The situations for the other pairs are the same but perhaps with x in place of y.)

We now build the analog of what is often called a δ-splitting tree in the Turing degree setting. It is in the construction of these trees that our new definition of homogeneity interpolants simplifies the construction as compared, for example, to that of Lerman [1983, VII.3].

Proposition 4.7 (Splitting trees). Given a Q with k(Q) = k and K(Q) = K̂ that decides {δ}^{G} with ρ and z as in Lemma 4.6, there is a condition ⟨S, K̂⟩ ≤ Q_{ρ}^{∗} such that any σ, τ ∈ dom S(= dom T r(Q)) with σ ≢_{z} τ δ-split on S. (Of course, by the choice of ρ and z there are no δ-splits on Q_{ρ}^{∗} which are congruent modulo z.) Such a tree S is called a z − δ-splitting tree.

Proof. We define S(σ) (with k(S) = k) by induction on |σ| beginning, of course, with S(∅) = Q_{ρ}^{∗}(∅). Suppose we have defined S(σ) = Q_{ρ}^{∗}(τ_{σ}) for all σ of length n. We must define S(σˆ α) for all such σ and appropriate α as extensions Q_{ρ}^{∗}(τ_{σˆ α}) of Q_{ρ}^{∗}(τ_{σ}ˆ α) obeying all the congruences in K̂, i.e. if x ∈ K̂ and α ≡_{x} β then τ_{σˆ α} ≡_{x} τ_{σˆ β}. We

list the σ of length n + 1 as σ_{i}ˆ α_{i} for i < m = | ∏_{j=0}^{j=n} Θ_{k+j}| and define by induction on

r < l = m(m + 1)/2 (the number of pairs {i, j} with i, j < m) strings ρ_{i,r} simultaneously for all i < m. At the end of our induction we will set τ_{σ_{i}ˆ α_{i}} = τ_{σ_{i}}ˆ α_{i}ˆ ρ_{i,0}ˆ … ˆ ρ_{i,l−1}. For this to succeed it suffices to maintain uniformity and guarantee, for every i, j < m and w ∈ K̂, that α_{i} ≡_{w} α_{j} ⇒ ρ_{i,r} ≡_{w} ρ_{j,r} for every r < l and that if α_{i} ≢_{z} α_{j} then τ_{σ_{i}}ˆ α_{i}ˆ ρ_{i,0}ˆ … ˆ ρ_{i,r} and τ_{σ_{j}}ˆ α_{j}ˆ ρ_{j,0}ˆ … ˆ ρ_{j,r} δ-split on Q_{ρ}^{∗} where r < l is (the code for) {i, j}.

By induction on r < l we suppose we have τ_{σ_{i}}ˆ ρ_{i,0}ˆ … ˆ ρ_{i,r−1} = ν_{i} for all i < m and that {p, q} is pair number r. If α_{p} ≡_{z} α_{q} there is no requirement to satisfy and we let ρ_{i,r} = ∅ for every i. Otherwise, let w be the largest y ∈ L_{k+n} such that α_{p} ≡_{y} α_{q}. (To see that there is a largest such y, first note that L_{k+n} is a lattice as it is a finite lsl. As Θ_{k+n} is an usl representation for L_{k+n}, if α_{p} ≡_{u,v} α_{q} for u, v ∈ L_{k+n} then α_{p} ≡_{t} α_{q} where t is the least element of L_{k+n} above both u and v (their join from the viewpoint of L_{k+n}). Thus, there is a largest y as desired.) Of course, z ≰ w. By our choice of z there are

σ, τ ∈ ∏_{t=0}^{t=c} Θ_{k+t} such that ν_{p} extended by σ and τ form a δ-splitting congruent modulo w

on Q_{ρ}^{∗}. (We can find such a split on Q_{ν_{p}}^{∗} by the definition of ρ and z and our assumption on w. It translates into such σ and τ.) Consider ν_{q}ˆ τ. It must form a δ-splitting on Q_{ρ}^{∗} with one of ν_{p}ˆ σ and ν_{p}ˆ τ by the basic properties of Q. If it splits with the latter string then we can set ρ_{i,r+1} = τ and clearly fulfill the requirements for this pair {p, q} both for congruence modulo w (as all new extensions are identical) and δ-splitting. Of course, uniformity is maintained as the ρ_{i,r+1} are the same for all i. Thus we assume that ν_{p}ˆ σ and ν_{q}ˆ τ δ-split on Q_{ρ}^{∗}. We now use our homogeneity interpolants.

We know that w is the largest y ∈ L_{n+k} such that α_{p} ≡_{y} α_{q} and that σ ≡_{w} τ. Thus for any x ∈ K̂ ⊆ L_{k+n} if α_{p} ≡_{x} α_{q} then x ≤ w and so σ ≡_{x} τ. By Theorem 5.1(3) we can now find homogeneity interpolants γ_{0}(s), γ_{1}(s) in Θ_{k+s+1} and associated K̂-homomorphisms f_{s}, g_{s}, h_{s} : Θ_{k+s} → Θ_{k+s+1} such that f_{s} : α_{p}, α_{q} ↦ σ(s), γ_{1}(s), g_{s} : α_{p}, α_{q} ↦ γ_{0}(s), γ_{1}(s) and h_{s} : α_{p}, α_{q} ↦ γ_{0}(s), τ(s) for each s < |σ| = |τ|. (We let α_{0} = α_{p}, α_{1} = α_{q}, β_{0} = σ(s), β_{1} = τ(s), L̂ = K̂ and i = k + s in the Theorem.) Note that the branchings in Q_{ρ}^{∗} are at some levels up from the corresponding ones in Q_{ν_{p}}^{∗} or Q_{ν_{q}}^{∗} on which we chose σ and τ. Thus these homogeneity interpolants are available within the branchings in Q_{ρ}^{∗}. As ν_{p}ˆ σ and ν_{q}ˆ τ δ-split on Q_{ρ}^{∗} one of the pairs ν_{p}ˆ σ, ν_{q} ˆ γ̄_{1}; ν_{p} ˆ γ̄_{0}, ν_{q} ˆ γ̄_{1} and ν_{p} ˆ γ̄_{0}, ν_{q}ˆ τ must also δ-split on Q_{ρ}^{∗}. Suppose for the sake of definiteness it is the second pair ν_{p} ˆ γ̄_{0}, ν_{q} ˆ γ̄_{1}. In this case we let ρ_{i,r+1}(s) = g_{s}(α_{i}) for every i and s. Note that uniformity is maintained as ρ_{i,r+1}(s) depends only on α_{i}. We use f_{s} or h_{s} in place of g_{s} if the δ-splitting pairs are ν_{p}ˆ σ, ν_{q} ˆ γ̄_{1} or ν_{p} ˆ γ̄_{0}, ν_{q}ˆ τ, respectively. By the homomorphism properties of the interpolants these extensions preserve all the congruences in K̂ between any α_{i} and α_{j} as required to complete the induction and our construction of a δ-splitting tree .

We now conclude the proof that {Q|Q ⊩ ∃x ∈ K(Q ⊩ {δ}^{G} ≡_{h} G_{x}^{Q})} is dense for each δ by proving that any z − δ-splitting tree S forces that {δ}^{G} ≡_{h} G_{z}^{S}. This will show that our embedding maps onto an initial segment of D_{h}. The required fact is generally called the Computation Lemma. We supply the standard proof.

Lemma 4.8 (Computation Lemma). If S is a z − δ-splitting tree then S ⊩ {δ}^{G} ≡_{h} G_{z}^{S}.

Proof. Let G ∈ [S]. We first show that {δ}^{G} ≤_{h} G_{z}^{S}. Consider any n. Using G_{z}^{S} we can find all the σ ∈ dom S of length n such that σ(l) = G_{z}^{S}(l) for every l ≤ n. All of these σ are congruent modulo z and so all S_{σ} force the same value for {δ}^{G} at n. As S(σ) is an initial segment of G for one of these σ, this value must be {δ}^{G}(n). We next argue that G_{z}^{S} ≤_{h} {δ}^{G}. Consider all σ, τ ∈ dom S of length n. If σ ≢_{z} τ then S_{σ} and S_{τ} force different values for {δ}^{G} at some l < n. Thus using {δ}^{G} ↾ n we can find the unique congruence class modulo z consisting of those σ such that S(σ) is not ruled out as a possible initial segment of G. For one σ in this class, S(σ) is an initial segment of G and as all the σ in this class are congruent modulo z, they all determine the same values of G_{z}^{S} ↾ n which must then be the correct value.

We have now completed the proof that any generic filter G (deciding all sentences and meeting the dense sets provided by Lemma 4.3 and Propositions 4.4 and 4.7) provides an embedding of K onto an initial segment of D_{h} that sends x ∈ K to deg_{h}(G_{x}^{P}) (for any P ∈ G).

Forcing ranked sentences (for conditions P with a fixed K(P)) is a Π_{1}^{1} relation (and so recursive in O) uniformly in K(P) and the inductive definition of forcing thereafter proceeds by the standard definition quantifying over previous levels of the forcing relation. (Remember that existential quantification is reduced to quantification over ordinals and terms below ω_{1}^{CK} and so to quantification over O, while negation requires quantification over forcing conditions and so over O ⊕ K.) Thus the forcing relation for arbitrary sentences is arithmetic in O⊕K (at a level simply related to the complexity of the sentence). Thus one can, as usual, construct a generic filter that decides all sentences hyperarithmetically in O ⊕ K. The steps for meeting the requirements of totality, diagonalization and splitting are also obviously computable in the forcing relation once one has proven the existence of the desired extensions (Lemma 4.3, Proposition 4.4 and 4.7). Thus we can find our generic G ≡_{h} G_{1}^{Id} (remember, 1 is the top element of our lattice), such that the hyperdegrees below that of G are isomorphic to our given K, hyperarithmetically in O ⊕ K. This establishes Theorem 1.2 given our lattice representation theorem to whose proof we now turn.

5 The lattice representation theorem

Theorem 5.1. If L is a countable lattice then there is an usl representation Θ of L along with a nested sequence of finite slsls L_{i} starting with L_{0} = {0, 1} with union L and a nested sequence of finite subsets Θ_{i} with union Θ with both sequences recursive in L with the following properties:

1. For each i, Θ_{i} ↾ L_{i} is an usl representation of L_{i}.

2. There are meet interpolants for Θ_{i} in Θ_{i+1}, i.e. if α ≡_{z} β, x ∧ y = z (in Θ_{i} and L_{i}, respectively) then there are γ_{0}, γ_{1}, γ_{2} ∈ Θ_{i+1} such that α ≡_{x} γ_{0} ≡_{y} γ_{1} ≡_{x} γ_{2} ≡_{y} β.

3. For every L̂ ⊆_{lsl} L_{i} there are homogeneity interpolants for Θ_{i} with respect to L̂ in Θ_{i+1}, i.e. for every α_{0}, α_{1}, β_{0}, β_{1} ∈ Θ_{i} such that ∀w ∈ L̂(α_{0} ≡_{w} α_{1} → β_{0} ≡_{w} β_{1}), there are γ_{0}, γ_{1} ∈ Θ_{i+1} and L̂-homomorphisms f, g, h : Θ_{i} → Θ_{i+1} such that f : α_{0}, α_{1} ↦ β_{0}, γ_{1}, g : α_{0}, α_{1} ↦ γ_{0}, γ_{1} and h : α_{0}, α_{1} ↦ γ_{0}, β_{1}.

Proof. We first define the sequence L_{i} of slsls of L beginning with L_{0} which consists of the 0 and 1 of L. We let the other elements of L be x_{n} for n ≥ 1 and L_{n} be the (necessarily finite) slsl of L generated by {0, 1, x_{1}, …, x_{n}}. As for Θ, we choose a countable set α_{i} and stipulate that Θ = {α_{i}|i ∈ ω}. We begin defining the (values of) the α_{i} by setting α_{0}(x) = 0 for all x ∈ L and α(0) = 0 for all α ∈ Θ. We will now define Θ_{n} and the values of α ∈ Θ_{n} (other than α_{0}) on the elements of L_{n} (other than 0) by recursion. For Θ_{0} we choose a new element β of Θ and let Θ_{0} = {α_{0}, β} and set β(1) = 1. Given Θ_{n} and the values for its elements on L_{n} we wish to enlarge Θ_{n} to Θ_{n+1} and define the values of α(x) for α ∈ Θ_{n+1} and x ∈ L_{n+1} so that the requirements of the Theorem are satisfied. To do this we prove a number of general extension theorems for usl representations in the Propositions below that show that we can make simple extensions to satisfy any particular meet or homogeneity requirement and also extend usl representations from smaller to larger slsls of L. To be more specific, we first apply Proposition 5.5 successively for each choice of x ∧ y = z in L_{n} and α, β ∈ Θ_{n} with α ≡_{z} β choosing new elements of Θ to form Θ′_{n} extending Θ_{n} and defining them on L_{n} so that Θ′_{n} ↾ L_{n} is an usl representation for L_{n} containing Θ_{n} and the required meet interpolants for every such x, y, z, α and β. We then apply Proposition 5.6 successively for each L̂ ⊆_{lsl} L_{n} and each α_{0}, α_{1}, β_{0}, β_{1} ∈ Θ_{n} such that ∀w ∈ L̂(α_{0} ≡_{w} α_{1} → β_{0} ≡_{w} β_{1}) to get larger subset Θ′′_{n} of Θ which we also define on L_{n} so as to have an usl representation Θ′′_{n} ↾ L_{n} for L_{n} that has the required homogeneity interpolants and L̂-homomorphisms from Θ_{n} into Θ′′_{n} for every such α_{0}, α_{1}, β_{0}, β_{1} ∈ Θ_{n}. Finally, we apply Proposition 5.4 to define the elements of Θ′′_{n} on L_{n+1} and further enlarge it to our desired finite Θ_{n+1} ⊆ Θ with all its new elements also defined on L_{n+1} so as to have an usl representation of L_{n+1} with all the properties required by the Theorem. It is now easy immediate from the definitions that the union Θ of the Θ_{n} is an usl representation of L.

Notation 5.2. If a finite L̂ is a slsl of L, L̂ ⊆_{lsl} L, and x ∈ L then we let x̂ denote the least element of L̂ above x. The desired element of L̂ exists because L̂ is a slsl of L and so the infimum (in L̂ or, equivalently, in L) of {u ∈ L̂|x ≤ u} is in L̂ and is the desired x̂. As L̂ is finite it is also a lattice but join in L̂ may not agree with that in L. We denote them by ∨L̂ and ∨_{L} respectively when it is necessary to make this distinction.

Lemma 5.3. With the notation as above, x̂ = x for x ∈ L̂ and so it is an idempotent operation. If x ≤ y are in L then x̂ ≤ ŷ. If x ∨_{L} y = z are in L then ẑ = x̂ ∨L̂ ŷ.

Proof. The first two assertions follow immediately from the definition of x̂. The third is only slightly less immediate: x, y ≤ x ∨_{L} y = z and so by the second assertion, x̂, ŷ ≤ ẑ and so x̂ ∨L̂ ŷ ≤ ẑ. For the other direction, note that as x ≤ x̂, y ≤ ŷ, we have that z = x ∨_{L} y ≤ x̂ ∨_{L} ŷ ≤ x̂ ∨L̂ ŷ ∈ L̂ and so ẑ ≤ x̂ ∨L̂ ŷ.

Proposition 5.4. If Θ is a finite usl representation for L̂ ⊆_{lsl} L (finite) then there are extensions for each α ∈ Θ to maps with domain L and finitely many further functions β with domain L such that adding them on to our extensions of the α ∈ Θ provides an usl representation Θ′ of L with Θ ⊆ Θ′ ↾ L̂. Moreover, these extensions can be found uniformly recursively in the given data (Θ, L̂ and L).

Proof. For α ∈ Θ and x ∈ L set α(x) = α(x̂). We first check that we have maintained the order and join properties required of an usl representation. If x ≤ y are in L, α, β ∈ Θ and α ≡_{y} β then by definition α ≡ŷ β and so α ≡x̂ β as x̂ ≤ ŷ by Lemma 5.3 and Θ’s being an usl representation of L̂. Thus, by definition, α ≡_{x} β as required.

Next, if x ∨_{L} y = z are in L and α ≡_{x,y} β we wish to show that α ≡_{z} β. Again by definition α ≡_{x̂,ŷ} β. By Lemma 5.3, x̂ ∨L̂ ŷ = ẑ, so by Θ being an usl representation for L̂, α ≡ẑ β and so by definition, α ≡_{z} β.

All that remains is to show that we can add on new maps with domain L that provide witnesses for the differentiation property for elements of L−L̂ while preserving the order and join properties. This is a standard construction. For each pair x ≰ y (in L but not both in L̂) in turn we add on new elements α_{x,y} and β_{x,y} with all new and distinct values at each z ∈ L except that they agree on all z ≤ x (and at 0, of course, have value 0). These new elements obviously provide the witnesses required for the differentiation property for an usl representation. It is easy to see that they also cause no damage to the order or join properties. There are no new nontrivial instances of congruences between them and the old ones in Θ (extended to L). Among the new elements the only instances to consider are ones between α_{x,y} and β_{x,y} for the same pair x, y and for lattice elements z less than or equal to x. As α_{x,y} ≡_{z} β_{x,y} for all z ≤ x, the order and join properties are immediate.

Proposition 5.5. If α, β ∈ Θ, an usl representation for a finite lattice L, α ≡_{z} β and x ∧ y = z in L then there are γ_{0}, γ_{1}, γ_{2} such that α ≡_{x} γ_{0} ≡_{y} γ_{1} ≡_{x} γ_{2} ≡_{y} β and Θ ∪ {γ_{0}, γ_{1}, γ_{2}} is still an usl representation for L. Moreover, these extensions can be found uniformly recursively in the given data.

Proof. This is a standard fact going back to Jónsson [1953] and can be found in Lerman [1983, Appendix B.2.5]. If x ≤ y, there is nothing to be proved. Otherwise, the interpolants can be defined by letting γ_{0}(w) be α(w) for w ≤ x and new values for w ≰ x; γ_{1}(w) = γ_{0}(w) for w ≤ y and new values otherwise; and γ_{2}(w) = β(w) for w ≤ y, γ_{2}(w) = γ_{1}(w) if w ≤ x but w ≰ y and new otherwise.

Proposition 5.6. If L̂ ⊆_{lsl} L, a finite lattice, and Θ is an usl representation for L with α_{0}, α_{1}, β_{0}, β_{1} ∈ Θ such that ∀w ∈ L̂(α_{0} ≡_{w} α_{1} → β_{0} ≡_{w} β_{1}), then there is an usl representation Θ̃ ⊇ Θ for L with γ_{0}, γ_{1} ∈ Θ̃ and L̂ homomorphisms f, g, h : Θ → Θ̃ such that f : α_{0}, α_{1} ↦ β_{0}, γ_{1}, g : α_{0}, α_{1} ↦ γ_{0}, γ_{1} and h : α_{0}, α_{1} ↦ γ_{0}, β_{1}. Moreover, these extensions can be found uniformly recursively in the given data.

Proof. For each α ∈ Θ and x ∈ L we set f(α)(x) = β_{0}(x) if α ≡x̂ α_{0} and otherwise we let it be a new number that depends only on α(x̂), e.g. α(x̂)^{∗}. Note that which case of the definition applies for f(α)(x) depends only on α(x̂) and it can be an “old” value (i.e. one of some β ∈ Θ) only in the first case. Thus, for α, β ∈ Θ,

(a) α ≡x̂ β ⇔ f(α) ≡_{x} f(β) and (b) f(α) ≡_{x} β ⇒ α ≡x̂ α_{0} ⇒ f(α) ≡_{x} β_{0}. (1)

Let Θ_{1} = Θ ∪ f[Θ]. We claim that Θ_{1} is an usl representation for L and f is an L̂- homomorphism from Θ into Θ_{1}. That f is an L̂-homomorphism is immediate from the first clause in (1) and the fact (Lemma 5.3) that x̂ = x for x ∈ L̂. We next check that Θ_{1} satisfies the properties required of an usl representation. Of course, f(α)(0) = 0 by definition for every α and differentiation is automatic as it extends Θ.

First, to check the order property for Θ_{1} we consider any x ≤ y in L. As Θ is already an usl representation for L, it suffices to consider two cases for the pair of elements of Θ_{1} which are given as congruent modulo y and show that in these two cases they are also congruent modulo x. The two cases are that (a) both are in f[Θ] and that (b) one is in f[Θ] and the other in Θ. Thus it suffices to consider any α, β ∈ Θ, assume that (a) f(α) ≡_{y} f(β) or (b) f(α) ≡_{y} β and prove that (a) f(α) ≡_{x} f(β) and (b) f(α) ≡_{x} β, respectively. For (a), we have by (1) that α ≡ŷ β and so by the order property for Θ, α ≡x̂ β. Thus f(α) ≡_{x} f(β) by definition as required. As for (b), (1) tells us here that α ≡ŷ α_{0} and β ≡_{y} f(α) ≡_{y} β_{0} (and therefore β ≡_{x} β_{0}). Now by Lemma 5.3 α ≡x̂ α_{0} so f(α) ≡_{x} β_{0} and so f(α) ≡_{x} β as required.

Next we verify the join property for x ∨ y = z in L and two elements of Θ_{1} (not both in Θ) in the same two cases. For (a) we have that f(α) ≡_{x,y} f(β) and so as above α ≡_{x̂,ŷ} β. Now by the join property in Θ and Lemma 5.3, α ≡ẑ β and so f(α) ≡_{z} f(β) as required. For (b) using (1b) and Lemma 5.3 again we have that f(α) ≡_{x,y} β ⇒ α ≡_{x̂,ŷ} α_{0} ⇒ α ≡ẑ α_{0} ⇒ f(α) ≡_{z} β_{0} while it also tells us that β ≡_{x,y} f(α) ≡_{x,y} β_{0} as required. Note that clearly f(α_{0}) = β_{0}. We let γ_{1} = f(α_{1}) and so have the first function and (partial) extension of Θ required in the Proposition.

We now define h on Θ_{1} as we did f on Θ using α_{1} and β_{1} in place of α_{0} and β_{0}, respectively: h(α)(x) = β_{1}(x) if α ≡x̂ α_{1} and otherwise we let it be a new number that depends only on α(x̂), e.g. α(x̂)^{∗∗}. Let Θ_{2} = Θ_{1} ∪ h[Θ_{1}]. As above, Θ_{2} is an usl representation for L and h is an L̂-homomorphism from Θ_{1} (and so Θ) into Θ_{2} taking α_{1} to β_{1}. We let γ_{0} = h(α_{0}) and so have the third function and (partial) extension of Θ required in the Proposition. As above in (1), we have for any α, β ∈ Θ_{1} and x ∈ L,

(a) α ≡x̂ β ⇔ h(α) ≡_{x} h(β) and (b) h(α) ≡_{x} β ⇒ α ≡x̂ α_{1} ⇒ h(α) ≡_{x} β_{1}. (2)

Applying the second clause to γ_{0} = h(α_{0}) and first to any β ∈ Θ_{1} and then, in particular to γ_{1} we have

(a) γ_{0} ≡_{x} β ⇒ α_{0} ≡x̂ α_{1} ⇒ f(α_{1}) = γ_{1} ≡_{x} β_{0} and (b) γ_{0} ≡_{x} γ_{1} ⇔ α_{0} ≡x̂ α_{1}. (3)

To see the right to left direction of the second clause, note that α_{0} ≡x̂ α_{1} implies that γ_{0} ≡_{x} β_{1} and γ_{1} ≡_{x} β_{0} by the definitions of h and f, respectively, while it also implies that β_{0} ≡x̂ β_{1} by the basic assumption of the Proposition. Thus, as Θ is an usl representation of L and x ≤ x̂, β_{0} ≡_{x} β_{1} and γ_{0} ≡_{x} γ_{1}.

Finally, we define g on α ∈ Θ_{2} by setting g(α)(x) = γ_{0}(x) if α ≡x̂ α_{0}. If α ≢x̂ α_{0} but α ≡x̂ α_{1} then g(α)(x) = γ_{1}(x). Otherwise, we let g(α)(x) be a new number that depends only on α(x̂), e.g. α(x̂)^{∗∗∗}. Note that if α ≡x̂ α_{1} then we always have g(α) ≡_{x} γ_{1} as if α ≡x̂ α_{0} as well then, by (3b), γ_{0} ≡_{x} γ_{1}. Thus g(α_{0}) = γ_{0} and g(α_{1}) = γ_{1} as required. It is also obvious that g is an L̂-homomorphism of Θ_{2} (and so Θ) into Θ_{3} = Θ_{2} ∪ g[Θ_{2}] as by definition and Lemma 5.3, α ≡x̂ β ⇒ g(α) ≡x̂ g(β) for any x ∈ L. Indeed, for any α, β ∈ Θ_{2} and x ∈ L

α ≡x̂ β ⇔ g(α) ≡_{x} g(β).  (4)

To see the right to left direction here, note that if either of g(α) or g(β) is new for g at x (i.e. of the form δ(ŷ)^{∗∗∗}) then clearly both are. In this case, α ≡x̂ β by definition.

Otherwise, either they are both congruent to α_{0} or both to α_{1} and so congruent to each other mod x̂. The point here is that if one is congruent to α_{0} and the other to α_{1} but not α_{0} at x̂ then by definition γ_{0} ≡_{x} γ_{1} and so by (3b), α_{0} ≡x̂ α_{1} for a contradiction.

Thus we only need to verify that Θ_{3} is an usl representation of L. We consider any α, β ∈ Θ_{2} and divide the verifications into cases (a) and (b) as before with the former considering g(α) and g(β) and the latter g(α) and β. These cases may then be further subdivided.

We begin with the order property and so x ≤ y in L.

(a) If g(α) ≡_{y} g(β) then, by (4), α ≡ŷ β and so α ≡x̂ β as x̂ ≤ ŷ (Lemma 5.3) and Θ_{2} is an usl representation of L. Thus, again by (4) g(α) ≡_{x} g(β) as required.

(b) If g(α) ≡_{y} β then by definition they are congruent modulo y to γ_{i} (for some i ∈ {0, 1}) and α is congruent to α_{i} at ŷ. Thus α ≡x̂ α_{i} as x̂ ≤ ŷ and Θ_{2} is an usl representation so g(α) ≡_{x} γ_{i} by definition. Similarly, as x ≤ y, β ≡_{x} γ_{i} as well.

Now for the join property for x ∨ y = z in L.

(a) If g(α) ≡_{x,y} g(β) then, as above, α ≡_{x̂,ŷ} β. As x̂ ∨ ŷ = ẑ by Lemma 5.3 and Θ_{2} is an usl representation, α ≡ẑ β and so by (4) g(α) ≡_{z} g(β) as required.

(b) If g(α) ≡_{x,y} β then again α ≡x̂ α_{i} and α ≡ŷ α_{j} for some i, j ∈ {0, 1} and g(α) ≡_{x} β ≡_{x} γ_{i} while g(α) ≡_{y} β ≡_{y} γ_{j}. If i = j then α ≡_{x̂,ŷ} α_{i} and so α ≡ẑ α_{i} and g(α) ≡_{z} γ_{i} ≡_{z} β as required.

On the other hand, suppose, without loss of generality, that (∗) α ≡x̂ α_{0} and so β ≡_{x} g(α) ≡_{x̂,x} γ_{0} = h(α_{0}) while α_{0} ≢ŷ α ≡ŷ α_{1} and so β ≡_{y} g(α) ≡_{ŷ,y} γ_{1} = f(α_{1}). If β ∈ Θ_{1} then by (4a) α_{0} ≡x̂ α_{1} and so α ≡x̂ α_{1}. As our assumption is that α ≡ŷ α_{1} we have (by the join property in Θ_{2}) that α ≡ẑ α_{1} and so g(α) ≡_{z} γ_{1}. As α_{0} ≡x̂ α_{1} (3b) tells us that γ_{0} ≡_{x} γ_{1}. Our assumptions then say that β ≡_{x,y} γ_{1} and so β ≡_{z} γ_{1} as required. Thus we may assume that β = h(δ) for some δ ∈ Θ_{1}.

We now have h(δ) = β ≡_{x} g(α) ≡_{x} γ_{0} = h(α_{0}) ∈ Θ_{1} and so by (2a) applied to h(δ) ≡_{x} h(α_{0}) with δ for α and α_{0} for β we see that δ ≡x̂ α_{0}. We also have h(δ) = β ≡_{y} g(α) ≡_{ŷ,y} γ_{1} = f(α_{1}). Applying (2b) to h(δ) ≡_{y} γ_{1} with δ for α and γ_{1} ∈ Θ_{1} for β, we see that δ ≡ŷ α_{1}and h(δ) ≡_{y} β_{1} and so β_{1} ≡_{y} γ_{1} = f(α_{1}). Now applying (1b) with α_{1} for α and β_{1} ∈ Θ for β, we have that α_{1} ≡ŷ α_{0}. As this contradicts (∗), we are done.

We complete our lattice theoretic material by supplying a proof of Lemma 1.4. Lemma 1.4: The class of finite lattices (with 0 and 1) has the amalgamation property, i.e. if A, B_{0} and B_{1} are finite lattices and f_{0}, f_{1} are embeddings of A into B_{0} and B_{1}, respectively, then there is a finite lattice C and embeddings g_{0} and g_{1} of B_{0} and B_{1}, respectively, into C such that g_{0}f_{0} ↾ A = g_{1}f_{1} ↾ A.

Proof. To simplify the notation we assume without loss of generality that the embeddings f_{0} and f_{1} are the inclusion maps and that the elements of A are the only ones that B_{0} and B_{1} have in common. We begin with a partial lattice P whose universe is the union of those of B_{0} and B_{1}. We define an order on P that coincides with the one on B_{i} for x, y both in one B_{i} and otherwise (say x ∈ B_{i} − A and y ∈ B_{1−i} − A) we set x < y ⇔ ∃a ∈ A(x <_{B_{i}} a & a <_{B_{1−i}} y). This relation is clearly transitive and we claim it preserves both join and meet from each B_{i}. First, if x, y ∈ B_{i} and x ∧ y = z in B_{i} then z is also the greatest lower bound of x and y in P. Clearly z ≤ x, y. So suppose w ≤ x, y is in P. If w ∈ B_{i} then, of course, w ≤ z. If w ∈ P − B_{i} then there are a_{x}, a_{y} ∈ A such that w < a_{x} ≤ x and w < a_{y} ≤ y so w ≤ a_{x} ∧_{A} a_{y} ≤ a_{x} ∧_{B_{i}} a_{y} ≤ x ∧_{B_{i}} y = z. The argument for preserving join is similar.

Now let C be the set of ideals of P, i.e. the subsets of P closed downward and under join when defined in P. We first note that C is clearly a lattice with order given by containment and the operations on X, Y ∈ C given by X ∧ Y = X ∩ Y and X ∨ Y equals the ideal in P generated by X ∪ Y (i.e. we close downward and under join when defined).

Finally, we define the required maps g_{i} : B_{i} → C as the restrictions (to B_{i}) of a single one-one g : P → C defined by sending p ∈ P to {q ∈ P|q ≤_{P} p} (the ideal generated by p). We show that g preserves join and meet in P when they exist and so its restrictions to B_{i} are lattice embeddings. If p ∧ q = r in P then it is clear that g(p) ∩ g(q) = g(r) by the definition of meet in P as required. As for join, if p ∨ q = r in P then g(r) is an ideal of P that contains both g(p) and g(q). On the other hand, any ideal of P containing both p and q must contain r by the definition of ideals in P. Thus g(r) = g(p) ∨_{C} g(q) as required.

6 Usls and other questions

There are now two obvious questions about the possible countable initial segments of the hyperdegrees. The first asks about lattice initial segments.

Question 6.1. What are the lattice initial segments of D_{h}? In particular, are there any which are not sublattices of some hyperarithmetic lattice?

We do not even have any candidates for additional lattices isomorphic to initial segments of D_{h}.

The second natural line of inquiry asks about usl initial segments. In D_{T}, there is no difference in the results: Every countable usl is isomorphic to an initial segment of D_{T}. Of course, we have seen (Theorem 1.1) that not every countable lattice is isomorphic to an initial segment of D_{h}. Given our Theorem 1.2, however, the conjecture might be that every subuppersemilattice (susl) of a hyperarithmetic lattice is isomorphic to an initial segment of D_{h}. Now our proof actually makes significant use of the existence of infima in L at various points. As it turns out, the assumption is essential, at least at this level of generality even if we require L to be locally finite as well.

Proposition 6.2. There is a susl L′ of a locally finite recursive lattice L which is not isomorphic to any initial segment of D_{h}.

Proof. The construction is an elaboration of that referred to in Theorem 1.1 that exploits the possibility of exact pairs for ideals in usls to make the initial lattice locally finite. The basic construction of the finitely generated successor model of Shore [1981] as modified in Shore [2007], [2008] begins with special elements designated by d_{0}, e_{0}, e_{1,}f_{0}, f_{1}, p and q. They contain a sequence d_{n} of elements of order type ω generated by the special elements as follows:

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

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

In addition we require that p ≱ q and p ∨ d_{n} ≥ q for each n. We then code a set X by adding two additional special elements 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. (So, in particular, ∃x(0 < x ≤ d_{n}, c_{X}) → d_{n} ≤ c_{X} and ∃x(0 < x ≤ d_{n}, c̄_{X}) → d_{n} ≤ c̄_{X}.)

We adjust this procedure to make the lattice locally finite. In place of d_{0} we have a set of elements d_{i,0} for i ∈ ω. For each i the sequence generated by the schemes (∗) and (∗∗) now terminates after i steps producing sequences d_{i,0}, …, d_{i,i} of length i + 1 by having (d_{i,i} ∨ e_{0}) ∧ f_{1} = 0 if i is even and (d_{i,i} ∨ e_{1}) ∧ f_{0} = 0 if i is odd. We now require that p ∨ d_{i,j} ≥ q for every j ≤ i ∈ ω and add on new elements p̂ ≱ q̂ such that p̂∨ d_{i,j} ≥ q̂ if and only if j = i. In place of c_{X} and c̄_{X} we have one fixed pair c and c̄ that are above all the d_{i,0} and no other of the previously mentioned elements. We complete this description to a lattice L in a way that respects the given ordering and specified join and meet relations and makes c ∧ c̄ a minimal upper bound of the ideal generated by the d_{i,0} with no other nonzero elements below it. We give more details after we see what properties are needed to make our coding of sets in a susl of L be sufficiently flexible to show that some such are not isomorphic to initial segments of D_{h}.

Given a set X we want to code X into a susl K of L by taking the susl of L generated by the special elements c, c̄, e_{0}, e_{1,}f_{0}, f_{1}, p, q, p̂ and q̂ and the d_{i,j} for i ∈ X. In particular, c and c̄ will now be an exact pair for the ideal generated by the d_{i,0} for i ∈ X. We want to guarantee that n ∈ X ⇔ there is a sequence x_{0}, …, x_{n} with x_{0} ≤ c, c̄; x_{2m+1} ≤ x_{2m}∨e_{0}, f_{1} and x_{2m+2} ≤ x_{2m+1} ∨ e_{1}, f_{0} for 2m + 1, 2m + 2 ≤ n; x_{m} ∨ p ≥ q for m ≤ n and x_{n} ∨ p̂ ≥ q̂.

We claim that in this case X is Π_{1}^{1} in the top G of any embedding of K as an initial segment. As existential quantification over sets hyperarithmetic in G and the relation A ≤_{h} B for sets given as hyperarithmetic in G are both Π_{1}^{1} in G and the join operator is recursive (on indices), it is clear that the specified relation on n is Π_{1}^{1}(G) and that it holds of every n ∈ X. What remains to verify is that it holds only of n ∈ X. So suppose there are x_{0}, …, x_{n} as described. For x_{0} ≤ c, c̄, we want x_{0} to be the join of finitely many d_{i,0} by making these the only elements of K below both c and c̄. Say for definiteness that x_{0} = d_{i_{1},0} ∨ ⋯ ∨ d_{i_{k},0}. We also arrange our lattice so that (x_{0} ∨ e_{0}) ∧ f_{1} = d_{i_{1},1} ∨ ⋯ ∨ d_{i_{k},1} and so x_{1} ≤ d_{i_{1},1} ∨ ⋯ ∨ d_{i_{k},1}. In general, we arrange our lattice so that (x_{2n} ∨ e_{0}) ∧ f_{1} = d_{i_{1},2n+1} ∨ ⋯ ∨ d_{i_{k},2n+1} and (x_{2n+1} ∨ e_{1}) ∧ f_{0} = d_{i_{1},2n+2} ∨ ⋯ ∨ d_{i_{k},2n+2} where we understand that for m > i, d_{i,m} = 0. Thus x_{m} ≤ d_{i_{1},m} ∨⋯∨d_{i_{k},m}. The requirements that x_{m} ∨p ≥ q guarantee that x_{m} > 0 and, by making the d_{i,j} minimal elements of the lattice, they must be above some nonzero d_{i_{k},m}. Finally, we guarantee that the only way such an x_{m} can join p̂ above q̂ is for it to be above some d_{i_{k},i_{k}} but these elements are in K if and only if i_{k} ∈ X as required.

Now to be more specific about the structure of L we specify its elements and the order on them that will give a lattice with all the desired properties. We begin, of course, with 0 and 1. The elements e_{0}, e_{1}, p, q, p̂, q̂ and d_{i,j} (for j ≤ i ∈ ω) are minimal nonzero elements of L. We extend the d_{i,j} freely to an usl L′ by taking all formal finite joins. This imposes a lattice structure on this set as well since each of the new elements has only finitely many elements below it. We next let p̂ act on the usl L′ as an order isomorphism under join (so for x, y ∈ L′, x ∨ p̂ ≤ y ∨ p̂ ⇔ x ≤ y). Let L′′ be the susl of L′ generated by the d_{i,j} with j < i. For x ∈ L′′, no elements other than p̂ and those y ≤ x are below x ∨ p̂. For x ∈ L′ − L′′ we also put x ∨ p̂ ≥ q̂. Joining e_{0} with members of L′ also acts as an order isomorphism except that, for any m ∈ ω and ⟨i_{k}⟩, ⟨j_{k}⟩ ∈ ω^{m} such that ∀k < m(j_{k} ≤ i_{k}), we make the following identification:

e_{0} ∨ ⋁{d_{i_{k},j_{k}}|k < m} = e_{0} ∨ ⋁{d_{i_{k},j_{k}}|k < m} ∨ ⋁{d_{i_{k},j_{k}+1}|k<m, j_{k} < i_{k} and j_{k} is even}.

We do the same for joining with e_{1} except that we change “even” to “odd”. We let f_{0} (f_{1}) be above the usl generated by the d_{i,j} for odd (even) j ≤ i and put in a new element c ∧ c̄ (below both c and c̄) which is above the usl generated by the d_{i,0}. Any order relation x ≤ y not dictated by these definitions is taken to be false. So for example, e_{0} ∨ e_{1} = 1 = f_{0} ∨ f_{1}, e_{0} ∧ e_{1} = 0 = f_{0} ∧ f_{1}, x ∨ p = 1 for any x ≠ 0, d_{i,i} ∨ p̂ = 1 for every i, etc. It is tedious but straightforward to verify that the partial order so defined imposes on the elements described a lattice structure L (i.e. for every x, y ∈ L there is a least upper bound and a greatest lower bound for the pair in the defined ordering) that has all the desired properties.

If we now take X to be, for example, the complement of O, then the top of any embedding of K as an initial segment would be above O and so the degrees below it could not be isomorphic to K (as, for example, every countable partial order can be embedded in D_{h} below deg_{h} O by Feferman [1965]).

On the other hand, there are initial segments of D_{h} which are not lattices. Indeed, the usual proof that D_{T} is not a lattice can be carried out for D_{h} by using Cohen forcing in the hyperarithmetic setting to show that the degrees below O are not a lattice (as is pointed out in Odifreddi [1983a, Proposition 8.3(b)]. Thus we have our next question.

Question 6.3. Which countable usls are isomorphic to initial segments of D_{h}?

This question seems wide open and, by the above Proposition, must need some new construction technique. One attractive possibility would be a positive answer to the following.

Question 6.4. Is every hyperarithmetic usl isomorphic to an initial segment of D_{h}?

Here even the simplest example seems to need some new idea.

Question 6.5. Is the usl consisting precisely of an initial segment x_{n} of type ω with an exact pair x, y and their join (i.e. 0 = x_{0}, ∀n(x_{n} < x_{n+1} ≤ x, y) and x∨y = 1) isomorphic to an initial segment of D_{h}?

On the other hand, we have no particularly plausible candidate for a counterexample to Question 6.4.

References

[1] Abraham, U. and Shore, R. A. [1986], Initial segments of the degrees of size ℵ_{1}, Israel J. Math. 53, 1-51.

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

[3] Adamowicz, Z. [1976], On finite lattices of degrees of constructibility, J. Symb. Logic 41, 313-322.

[4] Adamowicz, Z. [1977], Constructible semi-lattices of degrees of constructibility, in Set Theory and Hierarchy Theory V, Lachlan, Srebny and Zarach eds., LNM 619, Springer-Verlag, Berlin.

[5] Balcar, B. and Hajek, P. [1978], On sequences of degrees of constructibility, Z. Math. Logik Grundlag. Math. 24, 291-296.

[6] Cohen, P. [1966], Set Theory and the Continuum Hypothesis, Benjamin, New York.

[7] Dorais, F. [2007], Souslin Trees and Degrees of Constructibility, Ph.D. Thesis, Dartmouth College.

[8] Farrington, P. [1983], Hinges and automorphisms of the degrees of constructibility, J. Lon. Math. Soc. (2) 28, 193-202.

[9] Farrington, P. [1984], First order theory of the c-degrees, Z. Math. Logik Grundlag. Math. 30, 437-446.

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

[11] Gandy, R. O. and Sacks, G. E. [1967], A minimal hyperdegree, Fund. Math. 61, 215-223.

[12] Grätzer, G. [2003], General Lattice Theory, 2nd ed., Birkhäuser Verlag, Basel.

[13] Groszek, M. S. and Shore, R. A. [1988], Initial segments of the degrees of constructibility, Israel J. Math. 63, 149-177.

[14] Groszek, M. S. and Slaman, T. A. [1983], Independence results on the global structure of the Turing degrees, Trans. Am. Math. Soc. 277, 579-588.

[15] Hodges, W. [1993], Model Theory, Encyclopedia of Mathematics and its Applications 42, Cambridge University Press, Cambridge, England.

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

[17] Kjos-Hanssen, B. [2002], Lattice initial segments of the Turing degrees, Ph.D. Thesis, University of California, Berkeley.

[18] Kjos-Hanssen, B. [2003], Local initial segments of the Turing degrees, B. Symb. Logic 9, 26-36.

[19] Kleene, S. C. and Post, E. L. [1954], The upper semi-lattice of degrees of recursive unsolvability, Ann. Math. (2) 59, 379–407.

[20] Lachlan, A. H. [1968], Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grund. Math. 14, 457-472.

[21] Lachlan, A. H. and Lebeuf, R. [1976], Countable initial segments of the degrees of unsolvability, J. Symb. Logic 41, 289-300.

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

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

[24] Lubarsky, R. [1987], Lattices of c-degrees, Ann. Pure and Applied Logic 36, 115-118.

[25] Miller, R. G., Nies, A. O. and Shore, R. A. [2004], The ∀∃-theory of R(≤, ∨, ∧) is undecidable, Trans. Am. Math. Soc. 356, 3025-3067.

[26] Nerode, A. and Shore, R. A. [1980], Second order logic and first order theories of reducibility orderings, in The Kleene Symposium, J. Barwise, H. J. Keisler and K. Kunen, eds., North-Holland, Amsterdam, 181-200.

[27] Odifreddi, P. [1983], Forcing and reducibilities, J. Symb. Logic 48, 288-310.

[28] Odifreddi, P. [1983a], Forcing and reducibilities II: forcing in fragments of analysis, J. Symb. Logic 48, 724-743.

[29] Sacks, G. E. [1963], Degrees of unsolvability, Annals of Math. Studies 55, Princeton Univ. Press, Princeton, New Jersey.

[30] Sacks, G. E. [1971], Forcing with perfect closed sets, in Axiomatic set Theory, Proc. Symp. Pure Math. XII, Part 1, AMS, Providence, Rhode Island.

[31] Sacks, G. E. [1972], review of Thomason [1970], Math. Reviews, issue 2, MR0288027(44#5225).

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

[33] Selivanov, V. L. [1988], Algorithmic complexity of algebraic systems, Mat. Zametki 44, 823–832, 863; translation in Math. Notes 44 , 944–950 (1989)

[34] Shore, R. A. [1978], On the ∀∃-sentences of α-recursion theory, in Generalized Recursion Theory II, J. E. Fenstad, R. O. Gandy and G. E. Sacks eds., Studies in Logic and the Foundations of Mathematics 94, North-Holland, Amsterdam, 331-354.

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

[36] Shore, R. A. [2007], Local definitions in degree structures: the Turing jump, hyperdegrees and beyond, B. Symb. Logic 13, 226-239.

[37] Shore, R. A. [2008], Rigidity and biinterpretability in the hyperdegrees, in Computational Prospects of Infinity, Part II: Presented Talks, Lecture Notes Series 15, Institute for Mathematical Sciences, National University of Singapore, C. T. Chong, F. Qi and Y. Yang eds., World Scientific Publishing Co., Singapore, 2008.

[38] Simpson, M. F. [1985], Arithmetic Degrees: Initial Segments, ω-REA Operators and the ω-jump, Ph. D. thesis, Cornell University.

[39] Spector, C. [1956], On degrees of recursive unsolvability, Ann. Math. (2) 64, 581-592.

[40] Thomason, S. K. [1967], The forcing method and the upper semilattice of hyperdegrees, Trans. Am. Math. Soc. 129, 38-57.

[41] Thomason, S. K. [1969], A note on non-distributive sublattices of degrees and hyperdegrees, Canad. J. Math. 21, 147-148.

[42] Thomason, S. K. [1970], On initial segments of hyperdegrees, J. Symb. Logic 35, 189-197.