Π_{1}^{1} relations and paths through O^{∗}

Sergey S. Goncharov Academy of Sciences, Siberian Branch Mathematical Institute 630090 Novosibirsk, Russia gonchar@math.nsc.ru

Valentina S. Harizanov Department of Mathematics The George Washington University Washington, D.C. 20052, U.S.A. harizanv@gwu.edu

Julia F. Knight Department of Mathematics University of Notre Dame

Notre Dame, IN 46556, U.S.A. julia.f.knight.1@nd.edu

Richard A. Shore Department of Mathematics Cornell University Ithaca, NY 14853, U.S.A. shore@math.cornell.edu

February 26, 2004

1 Introduction

When bounds on complexity of some aspect of a structure are preserved under isomorphism, we refer to them as intrinsic. Here, building on work of Soskov [33], [34], we give syntactical conditions necessary and sufficient for a relation to be intrinsically Π_{1}^{1} on a structure. We consider some examples of computable structures A and intrinsically Π_{1}^{1} relations R. We also consider a general family of examples of intrinsically Π_{1}^{1} relations arising in computable structures of maximum Scott rank.

For three of the examples, the maximal well-ordered initial segment in a Harrison ordering, the superatomic part of a Harrison Boolean algebra, and the height-possessing part of a Harrison p-group, we show that the Turing degrees of images of the relation in computable copies of the structure are the same as the Turing degrees of Π_{1}^{1} paths through Kleene’s O. With this as motivation, we investigate the possible degrees of these paths. We show that there is a Π_{1}^{1} path in which ∅′ is not computable. In fact, there is one in which no noncomputable hyperarithmetical set is computable.^{1} There are paths that are Turing incomparable, or Turing incomparable over a given hyperarithmetical set. There is a pair of paths whose degrees form a minimal pair. However, there is no path of minimal degree.

∗The first three authors gratefully acknowledge support from the National Science Foundation under binational Grant DMS-0075899. The second author was partially supported by UFF grant of the George Washington University. The fourth author was partailly supported by NSF grant DMS-0100035.

In Section 2, we summarize earlier results on intrinsically c.e. and intrinsically Σ_{α}^{0} relations. In Section 3, we rework Soskov’s results, and we give our result on intrinsically Π_{1}^{1} relations. In Section 4, we describe the examples. In Section 5, we show that for the well-ordered initial segment of the Harrison ordering and related examples, the degrees of images of the relation in computable copies of the structure match those of Π_{1}^{1} paths through O. In Section 6, we give results on degrees of paths through O. In the remainder of the present section, we give some background. Most of this material may be found in the book by Ash and Knight [3].

1.1 Kleene’s O

We give a brief description of Kleene’s system of notation for computable ordinals. Further details may be found in [29] or [3]. The system consists of a set O of notations, together with a partial ordering <_{O}. The ordinal 0 gets notation 1. If a is a notation for α, then 2^{a} is a notation for α + 1. Then a <_{O} 2^{a}, and also, if b <_{O} a, then b <_{O} 2^{a}. Suppose α is a limit ordinal. If φ_{e} is a total function, giving notations for an increasing sequence of ordinals with limit α, then 3·5^{e} is a notation for α. For all n, φ_{e}(n) <_{O} 3 · 5^{e}, and if b <_{O} φ_{e}(n), then b <_{O} 3 · 5^{e}.

We may write |a| for the ordinal with notation a. If a ∈ O, then the restriction of <_{O} to the set pred(a) = {b ∈ O : b <_{O} a} is a well ordering of type |a|. For a ∈ O, pred(a) is c.e., uniformly in a. The set O is Π_{1}^{1} complete. A Π_{1}^{1} subset of O is Δ_{1}^{1} iff it is contained in a set of the form O_{α} = {b ∈ O : |b| < α}, where α is a computable ordinal.

1.2 Computable infinitary formulas

Next, we say a little about computable infinitary formulas. Roughly speaking, the computable infinitary formulas are infinitary formulas with disjunctions and conjunctions over c.e. sets. Taken all together, the computable infinitary formulas have the same expressive power as the formulas in the least admissible fragment of L_{ω_{1}ω}. It is useful to classify elementary first order formulas, in prenex normal form, as Σ_{n} or Π_{n}. For infinitary formulas, there is no prenex normal form, but we have the following.

Classification of computable infinitary formulas 1. A computable Σ_{0}, or Π_{0} formula is a finitary open formula.

1This provides a new solution to Problem 71 on H. Friedman’s list [10].

2. Suppose α > 0, where α is a computable ordinal.

(a) A computable Σ_{α} formula is a c.e. disjunction of formulas ∃\overline{u} ψ(\overline{x}, \overline{u}), where ψ is computable Π_{β} for some β < α.

(b) A computable Π_{α} formula is a c.e. conjunction of formulas ∀\overline{u} ψ(\overline{x}, \overline{u}), where ψ is computable Σ_{β} for some β < α.

The description above is sufficient for our purposes. To make precise what is a c.e. set of infinitary formulas, we would assign indices (based on ordinal notation) to the formulas. For more about computable infinitary formulas, see [3].

We consider only languages that are computable. This means that we can decide what is a symbol, and we can effectively determine the type (relation symbol or function symbol) and arity. We identify formulas with their Gödel numbers. Our structures will all be countable, with universe a subset of ω, which we think of as a computable set of constants. In measuring complexity of structures, we identify A with its atomic diagram D(A). Thus, the standard model of arithmetic—the natural numbers with the usual addition and multiplication—is a computable structure.

The most important feature of computable infinitary formulas is given in the result below.

Theorem 1.1 (Ash) For any structure B, the relation defined in B by a computable Σ_{α} formula is Σ_{α}^{0} relative to B, and the relation defined by a computable Π_{α} formula is Π_{α}^{0} relative to B. Moreover, this is true with all possible uniformity.

Below, we state a Compactness Theorem. Kreisel [23] stated a version of the result for ω-logic, and Barwise [7] (independently) gave a more general result for arbitrary admissible fragments of L_{ω_{1},ω}. The precise statement below is given in [3].

Theorem 1.2 (Kreisel, Barwise) Let Γ be a Π_{1}^{1} set of computable infinitary sentences. If every Δ_{1}^{1} subset of Γ has a model, then Γ has a model.

Theorem 1.2 can be used to produce computable structures.

Corollary 1.3 Let Γ be a Π_{1}^{1} set of computable infinitary sentences. If every Δ_{1}^{1} set Γ′ ⊆ Γ has a computable model, then Γ has a computable model.

The following is a special case of a result of Ressayre [28].

Theorem 1.4 (Ressayre) Suppose A is a hyperarithmetical structure. Let Γ be a Π_{1}^{1} set of computable infinitary sentences in a finite expansion of the language of A, and suppose that for each Δ_{1}^{1} set Γ′ ⊆ Γ, A can be expanded to a model of Γ′. Then A can be expanded to a model of Γ.

Corollary 1.5 Let A be a hyperarithmetical structure. If \overline{a} and \overline{b} are tuples in A satisfying the same computable infinitary formulas, then there is an automorphism of A taking \overline{a} to \overline{b}.

These results are all given in [3].

2 Intrinsically c.e. and intrinsically Σ_{α}^{0} relations

Below, we give some basic definitions. The first is from [5], and the second is from [4], [8].

Definition 2.1 Let A be a computable structure, and let R be a relation on A.

1. R is intrinsically c.e. on A if in all computable copies of A, the image of R is c.e.

2. R is relatively intrinsically c.e. on A if in all copies B of A (not just computable copies), the image of R is c.e. relative to B.

If, in the previous definitions, we replace c.e. by Σ_{α}^{0}, Δ_{1}^{1}, Π_{1}^{1}, then we obtain definitions of intrinsically, and relatively intrinsically, Σ_{α}^{0}, Δ_{1}^{1}, Π_{1}^{1}.

Ash and Nerode [5] gave a syntactical condition sufficient for a relation to be intrinsically c.e. on a structure A. They showed that, with some added effectiveness, on a single copy of A, the condition is also necessary. The syntactical condition is in the following definition.

Definition 2.2 A relation R is formally c.e. on a structure A if it is defined by a computable Σ_{1} formula; i.e., a c.e. disjunction of existential formulas, with finitely many parameters in A.

Theorem 2.3 (Ash-Nerode) For a relation R on a computable structure A, under some effectiveness conditions^{2}, R is intrinsically c.e. on A iff it is formally c.e. on A.

In [4], [8], it is shown that the syntactical condition by itself, with no added effectiveness, is necessary and sufficient for a relation to be relatively intrinsically c.e. on A.

Theorem 2.4 (Ash-Knight-Manasse-Slaman, Chisholm) For a relation R on a structure A, R is relatively intrinsically c.e. on A iff it is formally c.e. on A.

2It is enough to suppose that the existential diagram of (A, R) is computable.

It would be pleasing if the intrinsically c.e. and relatively c.e. relations coincided. Then we could drop the effectiveness conditions from Theorem 2.3. However, Goncharov [12] and Manasse [26] gave examples of relations R on computable structures A such that R is intrinsically c.e. but not formally c.e., so by Theorem 2.4, R is not relatively intrinsically c.e. on A.

Harizanov [15] considered the degree spectrum of R on A, where this is the set of Turing degrees of images of R in computable copies of A. The following is just one of the results.

Theorem 2.5 (Harizanov) Let R be a relation on a structure A, and suppose R is intrinsically c.e., while ¬R is not. Then, under some extra effectiveness conditions^{3}, for any c.e. degree d, there is a computable copy of A in which the image of R has degree d.

Example: Let A be an algebraically closed field of infinite transcendence degree—the characteristic may be either 0 or p. Let R be the set of algebraic elements. Then R is defined by a c.e. disjunction of polynomial equations, with no parameters, so it is (relatively) intrinsically c.e. There is a copy of A satisfying the effectiveness conditions of Theorem 2.5. Applying the theorem, we can produce computable copies of A in which the set of algebraic elements has any desired c.e. degree.

There are simple examples in which the spectrum consists of a single c.e. degree.

Example: If A is the standard model of arithmetic, and R is a c.e. set, then in all computable B ≅ A, the image of R is always c.e., with the same Turing degree as R.

There are now many deep and interesting results, due to Harizanov [15], Khoussainov and Shore [22], Hirschfeldt, Khoussainov, Shore, Slinko [18], and others, illustrating further possible spectra for intrinsically c.e. relations.

Barker [6] lifted the Ash-Nerode Theorem to arbitrary levels in the hyperarithmetical hierarchy. Here is the natural extension of the syntactical condition formally c.e.

Definition 2.6 A relation R on a structure A is formally Σ_{α}^{0} if it is definable by a computable Σ_{α} formula, with finitely many parameters.

Theorem 2.7 (Barker) For a structure A and relation R, under some effectiveness conditions, R is intrinsically Σ_{α}^{0} iff it is formally Σ_{α}^{0} on A.

Theorem 2.4 generalizes as follows [4], [8].

3Again, it is enough to suppose that the existential diagram of (A, R) is computable.

Theorem 2.8 (Ash-Knight-Manasse-Slaman, Chisholm) For a relation R on a computable structure A, R is relatively intrinsically Σ_{α}^{0} on A iff it is formally Σ_{α}^{0} on A.

It is natural to consider spectra. In [2], there is one possible generalization of Harizanov’s result (Theorem 2.5). It involves degrees that are coarser than Turing degrees. As in [3], the symbol Δ_{α}^{0} is used to denote a complete Δ_{α}^{0} set. (There is such a set naturally associated with each notation for α, but by a result of Spector [35], the degree depends only on the ordinal and not on the notation.)

Definition 2.9

1. A ≤_{Δ_{α}^{0}} B if A ≤_{T} B ⊕ Δ_{α}^{0},

2. A ≡_{Δ_{α}^{0}} B if A ≤_{Δ_{α}^{0}} B and B ≤_{Δ_{α}^{0}} A,

3. the equivalence classes under ≡_{Δ_{α}^{0}} are α-degrees.

Note that ≤_{Δ_{1}^{0}}, ≡_{Δ_{1}^{0}} are the same as ≤_{T}, ≡_{T}.

Theorem 2.10 (Ash-Knight) Let A be a computable structure, and let R be a relation that is not intrinsically Δ_{α}^{0} on A. Then, under some extra effectiveness conditions, for any Σ_{α}^{0} set C, there is an isomorphism F from A onto a computable copy with F (R) ≡_{Δ_{α}^{0}} C.

The proof of Theorem 2.10 is a natural lifting of the proof of Theorem 2.5. It is not possible to substitute Turing degrees for the coarser α-degrees. In [1], there are examples of structures A and relations R, satisfying a great deal of effectiveness, in which certain Σ_{α}^{0} Turing degrees, in particular, minimal degrees, are impossible for the image of R.

3 Intrinsically Δ_{1}^{1} and intrinsically Π_{1}^{1} relations

Soskov gave results characterizing the intrinsically Δ_{1}^{1} relations and the relatively intrinsically Π_{1}^{1} relations. In this section, we first rework Soskov’s results, and then give our characterization of intrinsically Π_{1}^{1} relations.

3.1 Intrinsically Δ_{1}^{1} relations

In [34], Soskov proved the following result—his terminology was different from ours.

Theorem 3.1 (Soskov) Suppose A is computable, and R is a Δ_{1}^{1} relation that is invariant under automorphisms of A. Then R is definable in A by a computable infinitary formula, with no parameters.

Proof: For simplicity, we suppose R is unary. The main step is the following.

Claim: There is a computable ordinal α such that for all a, b, if a ∈ R, and b satisfies the computable Π_{α} formulas true of a, then b ∈ R.

Proof of Claim: The structure (A, R) is hyperarithmetical. If there is no ordinal α as in the claim, then using Theorem 1.4, we get a ∈ R and b ∉ R satisfying the same computable infinitary formulas. By Corollary 1.5, some automorphism of A takes a to b, a contradiction. This proves the claim.

Now, letting α be as in the claim, we easily obtain the conclusion of Theorem 3.1. For each a, let ψ_{a}(x) be the conjunction of all computable Π_{α} formulas true of a. Then R is defined by the disjunction of the formulas ψ_{a}(x), for a ∈ R. This is equivalent to a computable infinitary formula.

Remarks:

1. There are no extra effectiveness conditions in Theorem 3.1. It is enough for A to be hyperarithmetical.

2. Suppose R is invariant in A, so it is definable in some way. If there is some computable copy in which the image of R is hyperarithmetical, then in all computable copies, the image of R is hyperarithmetical.

Corollary 3.2 For a computable structure A, and a relation R on A, the following are equivalent:

1. R is intrinsically Δ_{1}^{1} on A,

2. R is relatively intrinsically Δ_{1}^{1} on A,

3. R is definable in A by a computable infinitary formula, with finitely many parameters.

Proof: Clearly, 3 ⇒ 2 ⇒ 1. To see that 1 ⇒ 3, first note that R has only countably many images under automorphisms of A. This implies that for some tuple \overline{c}, R is invariant under automorphisms of (A, \overline{c}). Then by Theorem 3.1, R is definable by a computable infinitary formula, with parameters \overline{c}.

3.2 Intrinsically Π_{1}^{1} relations

The appropriate syntactical condition is in the following definition.

Definition 3.3 A relation R on A is formally Π_{1}^{1} on A if it is defined in A by a Π_{1}^{1} disjunction of computable infinitary formulas, with finitely many parameters.

In [33], Soskov proved a result that may be restated as follows.

Theorem 3.4 (Soskov) For a computable (or hyperarithmetical) structure A and relation R on A, the following are equivalent:

1. R is relatively intrinsically Π_{1}^{1} on A,

2. R is formally Π_{1}^{1} on A.

Sketch of proof: Clearly, 2 ⇒ 1. To show that 1 ⇒ 2, we build a generic copy B. The universe of B is a fixed computable set B of constants, and the forcing conditions are (as in the proofs of Theorems 2.4 and 2.8) finite partial 1 − 1 functions from B to A. For simplicity, we suppose that R is unary. Let R^{B} be the image of R in B.

There is more than one way to assign indices to Π_{1}^{1} sets. We consider subtrees of ω^{<ω}. A path in a tree T is a function f ∈ ω^{ω} such that for all n, f ↾ n ∈ T. We can express the fact that T has no path using a notion of rank. A node with no successors gets rank 0, and a node with successors gets rank α > 0 if all of the successors have ranks and α is the least ordinal greater than these ranks. We assign rank α to the tree if that is the rank of the top node ∅. A node extends to a path just in case it is unranked. A tree has no path just in case it has rank. For a computable (or hyperarithmetical) tree that has rank, the rank must be a computable ordinal. A set S is Π_{1}^{1} (relative to X) iff there is a family of trees (T_{n})_{n∈ω}, uniformly computable (relative to X), such that n ∈ S iff T_{n} has no path. For more on Π_{1}^{1} sets and paths through trees, see [29].

As indices for a set S that is Π_{1}^{1} (relative to X), we use indices for the sequences of trees (T_{n})_{n∈ω} described above. In particular, e is a Π_{1}^{1} index for R^{B} relative to B if for each b, φ_{e}(b) is an index for a tree T_{b} ⊆ ω^{<ω}, computable in B, such that b ∈ R^{B} iff T_{b} has no path.

Our forcing language includes computable infinitary sentences describing (B, R^{B}), plus a sentence ψ saying that e is a Π_{1}^{1} index for R^{B}. We describe this sentence, which is not computable infinitary, and we say how the sentence is forced. For each b and each computable ordinal α (actually, for each notation), we have a computable infinitary sentence ρ_{α,b} saying that T_{b} has rank α. Now, the sentence ψ says

⋀_{b} ⋀ [ b ∈ R^{B} ↔ ⋁_{α<ω_{1}^{CK}} ⋁ ρ_{α,b}] .

We define forcing such that p ∥− ψ iff for all a,

a ∈ R ⇔ ⋁_{α<ω_{1}^{CK}} ⋁ ⋁_{b} ⋁ (∃q ⊇ p) [ q(b) = a & q ∥− ρ_{α,b}] .

As usual, statements in the forcing language are true of our generic copy B just in case they are forced. For any computable infinitary sentence φ and any tuple \overline{b} from the universe of B, we can find a computable infinitary formula force_{\overline{b},φ}(\overline{x}), in the language of A, such that A ⊧ force_{\overline{b},φ}(\overline{a}) just in case the condition p taking \overline{b} to \overline{a} forces φ. Recall the sentences ψ and ρ_{α,b} above.

Suppose p ∥− ψ, where p maps \overline{d} to \overline{c}. We get a formally Π_{1}^{1} definition of R, with parameters \overline{c}, as follows. For each pair (α, b), we have a computable infinitary formula ρ_{(α,b)}^{∗}(\overline{c}, x) saying

(∃q ⊇ p) [q(b) = x & q ∥− ρ_{α,b}] .

The disjunction of the formulas ρ_{(α,b)}^{∗}(\overline{c}, x) is the desired formally Π_{1}^{1} definition of R.

We may extract more information from the proof of Theorem 3.4.

Theorem 3.5 Suppose A is a hyperarithmetical structure, and R is an infinite, coinfinite relation on A. If X is computable in the image of R in all copies B such that o(hyp(B)) = ω_{1}^{CK}, then X is computable.

The proof involves combining steps of the forcing construction with steps from Ressayre’s construction of a hyperarithmetically saturated structure [28]. We do not give the details.

The next result is the analogue of Theorem 3.1.

Theorem 3.6 Suppose A is a computable structure, and let R be a relation on A that is Π_{1}^{1} and invariant under automorphisms of A. Then R is formally Π_{1}^{1}. Moreover, there is a definition with no parameters.

Again, for simplicity, we suppose that R is unary. To prove Theorem 3.6, we use the following.

Lemma 3.7 For each a ∈ R, we can find a Δ_{1}^{1} index for a set D(a), invariant under automorphisms of A, such that a ∈ D(a) ⊆ R.

Proof of Lemma 3.7: For each a ∈ R, the orbit O_{1}(a) is a Σ_{1}^{1} subset of R, with index computed from a. By Kleene’s Separation Theorem, there is a Δ_{1}^{1} set D_{1}(a) containing all of O_{1}(a) and none of ¬R, again with index computed from a. Let O_{2}(a) be the union of the orbits of elements of D_{1}(a). Then O_{2}(a) is a Σ_{1}^{1} subset of R. There is a Δ_{1}^{1} set D_{2}(a) containing all of O_{2}(a) and none of ¬R, again with index computed from a. We continue in this way, forming D_{n}(a), for all n ∈ ω. Now, D(a) = ∪_{n}D_{n}(a) is invariant under automorphisms, with a ∈ D(a) ⊆ R. Moreover, D(a) is Δ_{1}^{1}, with index computed from a. This proves the lemma.

Using Lemma 3.7, we complete the proof of Theorem 3.6 as follows. We have a Π_{1}^{1} set of computable infinitary formulas ψ(x) such that

A ⊧ ψ(x) → ⋁_{c∈D(a)} ⋁ x = c

for some a ∈ R. Among the formulas ψ(x) are definitions of the sets D(a). The disjunction defines R.

Here is the analogue of Corollary 3.2.

Corollary 3.8 For a computable structure A and relation R, the following are equivalent:

1. R is intrinsically Π_{1}^{1} on A,

2. R is relatively intrinsically Π_{1}^{1} on A,

3. R is formally Π_{1}^{1} on A.

Sketch of Proof: Clearly, 3 ⇒ 2 ⇒ 1. The nontrivial implication 1 ⇒ 3 follows from Theorem 3.6 in the same way that the nontrivial implication in Corollary 3.2 follows from Theorem 3.1.

A relation is properly Π_{1}^{1} if it is Π_{1}^{1} and not Σ_{1}^{1}. We have seen that if a relation R on a computable structure A is invariant and Π_{1}^{1}, then it is intrinsically Π_{1}^{1}. Moreover, if there is some computable copy of A in which the image of R is Δ_{1}^{1}, then it is intrinsically Δ_{1}^{1}. This shows the following.

Corollary 3.9 If a relation R on a computable structure A is invariant and properly Π_{1}^{1}, then the image of R in any computable copy is also properly Π_{1}^{1}.

The next result produces computable copies of a given structure A with the same intrinsically Π_{1}^{1} relation, but with no hyperarithmetical isomorphism. Again, for B ≅ A, we write R^{B} for the image of R in B.

Theorem 3.10 Let A be a computable structure, with an invariant Π_{1}^{1} unary relation R. Suppose that for any invariant Δ_{1}^{1} relation R′ ⊆ R and any Δ_{1}^{1} set Γ_{0} of computable infinitary formulas, there is a computable structure, not isomorphic to A, but with the same universe A, such that the identity function on R′ preserves satisfaction of all formulas in Γ_{0}. Then the identity function on R extends to an isomorphism from A onto a computable copy B, where A and B are not hyperarithmetically isomorphic.

Proof: Since R is Π_{1}^{1} and invariant, there is a Π_{1}^{1} definition, with no parameters— say P is the Π_{1}^{1} set of disjuncts. We use the fact that O is m-complete Π_{1}^{1} (see [29]). Let f be a computable function witnessing that P ≤_{m} O. For each a ∈ O, let P_{a} be the set of all n such that f(n) <_{O} a. We can pass effectively from a ∈ O to a computable infinitary formula ψ_{a}(x) equivalent to the disjunction of the formulas in P_{a}.

We describe B by a Π_{1}^{1} set Γ of computable infinitary sentences, in a language with added constants for the elements of A.

1. We include a sentence saying that B is a computable structure with universe A.

2. To guarantee that B ≅ A, we include all computable infinitary sentences true in A (in the language without the constants from A).

3. To guarantee that R^{B} = R^{A}, we include, for each a ∈ A, sentences ψ_{a}(c) if A ⊧ ψ_{a}(c), and ¬ψ_{a}(c) if A ⊧ ¬ψ_{a}(c).

4. To guarantee that there is an isomorphism that acts as the identity on R, we include φ(\overline{c}), for each tuple \overline{c} in R and each computable infinitary formula φ(\overline{x}) such that A ⊧ φ(\overline{c}).

Remarks: Given the sentences of 4, we could omit the sentences of 2, and we could reduce 3 to just the sentences of the form ¬ψ_{a}(c).

The hypotheses yield a model for any Δ_{1}^{1} subset of Γ. Then, by Barwise-Kreisel Compactness, Γ has a model. We have a computable structure B that is isomorphic to A, such that for all a ∈ O, ψ_{a}^{B} = ψ_{a}^{A}, and the identity function on R preserves satisfaction of all computable infinitary formulas. For each a ∈ O, if we expand A and B by constants for all elements satisfying ψ_{a}, the resulting structures are hyperarithmetical, and since they satisfy the same computable infinitary sentences, they are isomorphic.

We must show that there is an isomorphism from A onto B that acts as the identity on all of R. Let A^{∗} be the structure (A, A, B), with separate relations for the two structures. Then A^{∗} is computable. We form a Π_{1}^{1} set Λ of computable infinitary sentences, in a language with a new binary relation symbol F, in addition to the symbols of the language of A^{∗}. We include a sentence saying that F is an isomorphism from A onto B, and sentences for all a ∈ O saying that F acts as the identity on the set of elements satisfying ψ_{a}(x). It follows from the previous paragraph that for any Δ_{1}^{1} set Λ′ ⊆ Λ, there is an expansion of A^{∗} satisfying Λ′. Then by Theorem 1.4, there is an expansion of A^{∗} satisfying all of Λ.

Soskov showed that the notions “intrinsically Δ_{1}^{1}” and “relatively intrinsically Δ_{1}^{1}” are equivalent. We have seen that “intrinsically Π_{1}^{1}” and “relatively intrinsically Π_{1}^{1}” are also equivalent. We mentioned a result of Goncharov and Manasse, showing that the notions “intrinsically c.e.” and “relatively intrinsically c.e.” are not equivalent. It is natural to ask at which levels the notions differ.

Conjecture: For each computable ordinal α, there exist A and R such that R is intrinsically Σ_{α}^{0} and not relatively intrinsically Σ_{α}^{0} on A.

In [14] the conjecture is proved for all computable successor ordinals, but for limit ordinals, the method of [14] gives no information.

4 Examples

Here are some examples of computable structures with intrinsically Π_{1}^{1} relations.

1. A Harrison ordering is a computable ordering of type ω_{1}^{CK}(1 + η). Recall that η is the order type of the rationals, and for orderings A and B, A · B is the result of replacing each element of B by a copy of A. Harrison [17] showed the existence of such orderings (see also [31] and [3]). In fact, he showed that for any computable tree T ⊆ ω^{<ω}, if T has paths but no hyperarithmetical paths, then the Kleene-Brouwer ordering on T is a computable ordering of type ω_{1}^{CK}(1+η)+α, for some computable ordinal α. Let A be a Harrison ordering, and let R be the initial segment of type ω_{1}^{CK}. This set is intrinsically Π_{1}^{1}, since it is defined by the disjunction of computable infinitary formulas saying that the interval to the left of x has order type β, for computable ordinals β.

2. A Harrison Boolean algebra is a computable Boolean algebra of type I(ω_{1}^{CK}(1 + η)). Recall that for an ordering C, the interval algebra I(C) is the algebra generated, under finite union, by the half-open intervals [a, b), (−∞, b), [a, ∞), with endpoints in C. Let A be a Harrison Boolean algebra, and let R be the set of superatomic elements—those contained in one of the Frechet ideals. This is intrinsically Π_{1}^{1}, since it is defined by the disjunction of computable infinitary formulas saying that x is a finite join of α-atoms, for computable ordinals α.

3. Recall that a countable Abelian p-group G is determined up to isomorphism by its Ulm sequence (u_{α}(G))_{α<λ(G)}, and the dimension of the divisible part (see [21]). A Harrison p-group is a computable Abelian p-group G such that λ(G) = ω_{1}^{CK}, u_{G}(α) = ∞, for all α < ω_{1}^{CK}, and the divisible part D has infinite dimension. A Harrison group is a Harrison p-group for some p. Let A be a Harrison group, and let R be the set of elements that have computable ordinal height—the complement of the divisible part. Then R is intrinsically Π_{1}^{1} on A, since it is defined by the disjunction of computable infinitary formulas saying that x has height α, for computable ordinals α.

The Scott Isomorphism Theorem [32] says that for any countable structure A (for a countable language), there is an L_{ω_{1}ω} sentence σ such that the countable models of σ are exactly the copies of A. In the proof, Scott assigned an ordinal to the structure. There is more than one definition of “Scott rank”. The one used by Sacks [30] involves a sequence of expansions of A. Let A_{0} = A, let A_{α+1} be the result of adding to A_{α} predicates for the types realized in A_{α}, and for limit α, let A_{α} be the limit of the expansions A_{β}, for β < α. For some countable ordinal α, A_{α} is atomic. The least such α is the rank. For a hyperarithmetical structure A, the maximum possible rank is ω_{1}^{CK} + 1.

Another possible rank, for a hyperarithmetical structure A, is the least ordinal α such that for each tuple \overline{a} in A, there is some β < α such that the set of all computable Π_{γ} formulas true of \overline{a}, for γ < β, defines the orbit of \overline{a} under automorphisms. These definitions are not equivalent, but they agree to the extent that if the one rank is a computable ordinal, or ω_{1}^{CK}, or ω_{1}^{CK} + 1, then so is the other.

A hyperarithmetical structure A has rank ω_{1}^{CK} + 1 just in case there is a tuple \overline{a} in A whose orbit under automorphisms is not defined by any computable infinitary formula. In the three examples of intrinsically Π_{1}^{1} relations described above, the structures have Scott rank ω_{1}^{CK} + 1. Below, we describe a general class of examples arising in computable structures of this rank.

Proposition 4.1 Let A be a computable structure of Scott rank ω_{1}^{CK} + 1. Let \overline{a} be a tuple in A whose orbit is not defined by any computable infinitary formula, and let R be the complementary relation. Then R is intrinsically Π_{1}^{1}, and not Δ_{1}^{1}.

Proof: We define R by the disjunction of ¬γ(\overline{x}), where γ(\overline{x}) is a computable infinitary formula true of \overline{a}.

The structures in Examples 1, 2, and 3 above all have Scott rank ω_{1}^{CK} + 1, but the intrinsically Π_{1}^{1} relations that we described above are not complements of single orbits. We can apply Proposition 4.1 to obtain further intrinsically Π_{1}^{1} relations on these same structures. In particular, in the Harrison ordering, if a is an element outside the well-ordered initial segment, then the orbit of a is not defined by any computable infinitary formula. Say a is first in its copy of ω_{1}^{CK}. Then the orbit of a consists of the elements that are first in their copy of ω_{1}^{CK}, but not first over-all. By Proposition 4.1, the complement of this orbit is intrinsically Π_{1}^{1}. It is not Δ_{1}^{1}.

In the next section, we show that for Examples 1, 2, and 3, the degree spectrum of R is the set of Turing degrees of Π_{1}^{1} paths through O.

5 Connections with paths through O

By a path through O we mean a subset of O that is linearly ordered under <_{O} and includes a notation for each computable ordinal.

1. Let P be the set of Turing degrees of Π_{1}^{1} paths through O.

2. Let N be the set of computable trees T ⊆ ω^{<ω} such that T has a path, but no hyperarithmetical path.

3. Let L be the set of Turing degrees of left-most paths of trees in N.

4. Let L̂ be the set of Turing degrees of left-most paths of computable trees T ⊆ ω^{<ω} in which there is a path, and the left-most one is not hyperarithmetical.

5. Let WH be the set of Turing degrees of maximal well-ordered initial segments of Harrison orderings.

6. Let W be the set of Turing degrees of maximal well-ordered initial segments I of computable orderings, where the order type of I is not a computable ordinal.

7. Let SH be the set of Turing degrees of superatomic parts of Harrison Boolean algebras.

8. Let DH_{p} be the set of Turing degrees of divisible parts of Harrison pgroups. (The divisible part of a Harrison p-group has the same degree as its complement, which, as we have seen, is intrinsically Π_{1}^{1}.)

In this section, we show that P = L = L̂ = WH = W = SH = DH_{p}.

The next result characterizes those orderings that can appear as the maximal well-ordered initial segments of Harrison orderings.

Theorem 5.1 For an ordering (R, <) of type ω_{1}^{CK}, the following are equivalent:

1. (R, <) is Π_{1}^{1}, and for b ∈ R, the restriction of the ordering to pred(b) is computable uniformly in b.

2. (R, <) is the maximal well-ordered initial segment in a Harrison ordering.

3. (R, <) is the maximal well-ordered initial segment in a computable ordering that has initial segments of type α, for all computable ordinals α.

4. (R, <) is the maximal well-ordered initial segment in a computable ordering that has initial segments of type α, for all computable ordinals α, and has no infinite hyperarithmetical decreasing sequence.

Sketch of proof: Clearly, 2 ⇒ 3, 4 ⇒ 3, and 3 ⇒ 1. To show that 1 ⇒ 2, we use the Barwise-Kreisel Compactness Theorem. We describe a Π_{1}^{1} set Γ of computable infinitary sentences, in a language with an infinite computable set of constants B (= ω) and a binary relation symbol <. First, we include sentences saying that the universe is equal to B, and < is a computable linear ordering of B. Next, we include the Π_{1}^{1} set Γ_{0} consisting of all computable infinitary sentences true in some known Harrison ordering. Finally, we include the Π_{1}^{1} set Γ_{1} of sentences

(∀x) [ x < b ↔ ⋁_{c∈pred(b)} ⋁ x = c]

for b ∈ R.

For any Δ_{1}^{1} set Γ′ ⊆ Γ, there is a model. We may suppose that the constants mentioned in Γ′ ∩Γ_{1} are in pred(b). Then Γ′ has a model such that pred(b) is an initial segment, and the remaining constants from B form a terminal segment of order type ω^{α}, where α is chosen sufficiently large that Γ′ ∩ Γ_{0} is satisfied. It is clear that a model of Γ yields a Harrison ordering B with R^{B} = R.

The fact that 1 ⇒ 4 is proved in much the same way, with Γ_{0} replaced by the set of sentences saying that (B, <) has no hyperarithmetical decreasing sequence.

It follows from Theorem 5.1 that WH = W (the sets whose degrees we are taking are the same). The next result says that W ⊆ P.

Proposition 5.2 Let A be a computable linear ordering, and let (L, <) be the maximal well-ordered initial segment. If L is not hyperarithmetical, then it has order type ω_{1}^{CK}, and deg(L) ∈ P.

Proof: Clearly, L cannot have order type > ω_{1}^{CK}. If A has an initial segment of type α, where α is a computable ordinal, then there is a computable infinitary formula φ_{α}(x) defining the initial segment, and the set of elements satisfying φ_{α}(x) is hyperarithmetical. Therefore, L cannot have order type < ω_{1}^{CK}. It follows that L must have order type exactly ω_{1}^{CK}.

We must show that L has degree in P. We form another computable ordering A^{∗}, of type ω×A, by replacing each element a of A by a copy of ω, with elements ⟨a, n⟩, for n ∈ ω—A^{∗} is the lexicographic ordering on A × ω. So, for example, if a_{0} is the least element of A, then ⟨a_{0}, 0⟩ is the least element of A^{∗}. Let L^{∗} be the maximal well-ordered initial segment of A^{∗}. In passing from A to A^{∗}, what we have gained is that, given ⟨a, n⟩ ∈ L^{∗}, we can effectively determine whether it is the first element (⟨a_{0}, 0⟩), or a successor (of the form ⟨a, n⟩, for n > 0), or a limit (of the form ⟨a, 0⟩, for a ≠ a_{0}), and we can effectively find the successor of ⟨a, n⟩ (namely, ⟨a, n + 1⟩).

Claim: There is a total computable function f that maps L^{∗} isomorphically onto an initial segment of O. Moreover, if x is an element of the domain of f of the form ⟨a, 0⟩, then x < f(x).

Proof of Claim: We want a computable function f such that

1. f(⟨a_{0}, 0⟩) = 1,

2. f(⟨a, n + 1⟩) = 2^{f(⟨a,n⟩)}, for a ∈ A,

3. f(⟨a, 0⟩) = 3 · 5^{e}, for a >_{A} a_{0}, where e > ⟨a, 0⟩ is an index for a <_{O}- ascending sequence, cofinal in V_{a} = {f(x) : x <_{A^{∗}} ⟨a, 0⟩}; e.g., for the function g such that g(n) is the first element y that we come to, in the standard enumeration of the c.e. set V_{a}, such that g(m) <_{O} y for all m < n, and c <_{O} a for all c in the stage n approximation of V_{a},

4. f(x) = 0 in all other cases.

To obtain the desired f, we apply the Recursion Theorem, as follows. We have a total computable function σ that takes each e to an index for a partial computable function k such that

1’. k(⟨a_{0}, 0⟩) = 1,

2’. if φ_{e}(⟨a, n⟩) = d, then k(⟨a, n + 1⟩) = 2^{d},

3’. if a ∈ A, and a ≠ a_{0}, then k(⟨a, 0⟩) = 3 · 5^{e′}, where e′ is the index for the function g that is calculated by the procedure described above, in terms of the set V_{a} = {φ_{e}(x) : x <_{A^{∗}} ⟨a, 0⟩}, over which we have no

control,

4’. if x is not of the form ⟨a, n⟩ for a ∈ A, then k(x) = 0.

We let f = φ_{e}, where φ_{e} = φ_{σ(e)}. To see that f is total, note that every number x can be expressed in the form ⟨a, n⟩. If a ∉ A, then f(x) is defined, by 4. Suppose a ∈ A. If n = 0, then f(x) is defined by 1 if a = a_{0}, and by 3 if a ≠ a_{0}. Finally, to show that f(⟨a, n⟩) is defined for n > 0, we proceed by induction on ω, using 2. Now, we see by induction on < that f maps initial segments of L^{∗} onto initial segments of O (under <_{O}). Moreover, by 3, if x has the form ⟨a, 0⟩, then f(x) > x. This proves the claim.

Let f be as in the claim. Now, f[L^{∗}] is a Π_{1}^{1} but not hyperarithmetical subset of O, so it is unbounded. Then f[L^{∗}] = P is a path through O. Thus, the order type of L^{∗} is ω_{1}^{CK}, and so is that of L. Clearly, L and L^{∗} have the same Turing degree. Thus, we only have to show that L^{∗} ≡_{T} P. The fact that L^{∗} ≤_{T} P is immediate, since the domain of f is computable and x ∈ L^{∗} iff f(x) ∈ P.

For the other direction, to decide whether x ∈ P, using L^{∗}, we first see if x = 1. If so, then x ∈ P. If not, then we see if x is a power of 2. If x = 2^{y}, then we apply the same procedure to y, keeping in mind that x ∈ P iff y ∈ P. If not, then we determine for which numbers z < x, in the usual ordering of ω, z has the form ⟨a, 0⟩ < x and z ∈ L^{∗}. For each such z, we ask if f(z) = x. If, for some z, the answer is “yes”, then x ∈ P. Otherwise, x ∉ P, as by our construction, f(⟨b, 0⟩) > ⟨b, 0⟩, for all b >_{A} a_{0} and x can only be in P if it is the image of a limit point ⟨b, 0⟩ in L^{∗}. Eventually, this process terminates, as y < x.

The next result says that P ⊆ WH.

Proposition 5.3 If A is a Π_{1}^{1} path through O, then there is a Harrison ordering B with maximal well-ordered initial segment R such that R ≡_{T} A.

Proof: Jockusch [19] showed that for any Π_{1}^{1} path A through O, there is another Π_{1}^{1} path C, of the same Turing degree, such that C is regular, where this means that for c ∈ C, pred(c) is computable, uniformly in c. Then by Theorem 5.1, there is a Harrison ordering B such that the maximal well-ordered initial segment is C, ordered by <_{O}.

Now, we consider the sets of degrees of certain paths through computable trees. Clearly, L ⊆ L̂. The next result says that L̂ ⊆ P.

Corollary 5.4 Suppose T is a computable tree, and let g be the left-most path in T. If g is not hyperarithmetical, then deg(g) ∈ P.

Proof: We apply Proposition 5.2 to the Kleene-Brouwer ordering on T, and note that the well-ordered initial segment has the same degree as g, since it consists of just the nodes in T to the left of g.

The next result says that P ⊆ SH.

Theorem 5.5 Let A be a Π_{1}^{1} path through O. Then there is a Harrison Boolean algebra B with superatomic part R such that R ≡_{T} A.

Sketch of proof: We may suppose that A is regular. Note that A ≡_{T} A × ω. We produce a Harrison ordering A^{∗}, extending A (with <_{O}), a Harrison Boolean algebra B, with superatomic part R, and a pair of 1 − 1 computable functions F and G, such that F is defined on A^{∗} × ω, with

(a, n) ∈ A × ω ⇔ F (a, n) ∈ R ,

and G is defined on B, with

b ∈ R ⇔ G(b) ∈ A × ω .

Assume for the moment that we have A^{∗}, B, F, and G, as described. Then A × ω ≤_{1} R^{B} via F, while R^{B} ≤_{1} A × ω via G. It follows that R^{B} ≡_{T} A.

The objects A^{∗}, B, F, and G will form a model of a Π_{1}^{1} set Γ of computable infinitary sentences consisting of the following:

1. sentences guaranteeing that A^{∗} is a computable linear ordering, with universe ω, such that A, ordered by <_{O}, is an initial segment,

2. sentences guaranteeing that B = (B, ∨, ∧, 0, 1) is a Harrison Boolean algebra,

3. sentences guaranteeing that F is a computable 1 − 1 function mapping A^{∗} × ω into B, such that for a ∈ A, the set of elements F (a, n) is a basis for the |a|-atoms of B,

4. sentences guarateeing that G is a computable 1 − 1 function with domain B such that for each a ∈ A, G maps the set R_{a} of elements of “rank” |a| onto the set A_{a} of pairs (a, n). (An element is in R_{a} if it differs from a finite join of elements of B_{a} by a finite join of elements of B_{d} for d <_{0} a.)

If A^{∗}, B, F, and G satisfy all of Γ, then B is a Harrison Boolean algebra, and the functions F and G have the properties we want. By the Barwise-Kreisel Compactness Theorem, Γ has a model if every Δ_{1}^{1} subset has a model. We just need to prove the following lemma.

Lemma 5.6 Let a ∈ A, where |a| = α. Then there exist a computable Boolean algebra B of type I(ω^{α+1}) and computable 1−1 functions F and G such that for each b ≤_{O} a with |b| = β, F takes {b} × ω onto a computable set B_{b} generating the β-atoms of B, and G maps B_{b} onto the set R_{b} of elements of B of rank β.

Proof of Lemma: Since A is regular, {b ∈ O : b ≤_{O} a} is computable. Let F (b, n) = (b, n), for b <_{O} a. For any infinite computable set C, we have a canonical partition into infinitely many infinite computable sets C_{n}—the k^{th} element of C_{n} is the (n, k)^{th} element of C. Using the canonical partitions, we determine, for b <_{O} c, the relations x ≤ y, for x ∈ B_{b} and y ∈ B_{c}. As a first step, we consider b = 1 and c = a. For x ∈ B_{1} and y ∈ B_{a}, we let x ≤ y if, y is the n^{th} element of B_{a}, and x is in the n^{th} class in the canonical partition of B_{1}.

At each succeeding step, we consider the next element d of pred(a), in the ordering <_{ω}. If d lies between b and c, in the ordering <_{O}, where b and c have been considered previously, then we take the canonical partition of B_{d}, and put the elements of the n^{th} class of B_{d} below the n^{th} element of B_{c}. At this point, corresponding to each z ∈ B_{c}, we have a class C in B_{b} and a class C′ in B_{d}. We take the canonical partition of C′ and put the elements of the n^{th} class of C′ below the n^{th} element of C.

The union B of the sets B_{b}, for b <_{O} a, is computable, with infinite complement. We can form a computable Boolean algebra generated by the elements of B, with universe ω. Moreover, we can do this so that for all b ∈ pred(a), the set R_{b} of elements of rank |b| is computable, uniformly in b. The names for the elements tell us how they are constructed from elements of B_{c} for c ≤_{O} b. We have a computable 1 − 1 function G that maps R_{b} onto B_{b}, for all b ∈ pred(a).

The next result says that P ⊆ DH_{p}.

Proposition 5.7 If A is a Π_{1}^{1} path through O, then for each prime p, there is a Harrison p-group G, with height-possessing part R such that R ≡_{T} A.

We may suppose that A is regular. We use the following lemma.

Lemma 5.8 For any a ∈ A, there exist a computable reduced Abelian p-group G, and computable 1−1 functions F and H such that G has length |a|, with Ulm invariants all infinite, F has domain pred(a) × ω, where F (b, n) is an element of A of height |b|, H is defined on the elements of G, aside from the identity, and H maps the elements of height |b| onto the pairs of the form (b, n).

Proof of Lemma: First, let T_{a} be the computable tree consisting of ∅ and any nonempty sequences

σ = ⟨b_{1}, n_{1}⟩, …, ⟨b_{k}, n_{k}⟩ ,

where n_{i} ∈ ω, and b_{i} ∈ pred(a), with b_{1} >_{O} … >_{O} b_{k}. Next, let G be the computable Abelian p-group generated by the nodes of T_{a}, under the relations ∅ = 0, and pσ = τ, where σ is a successor of τ. Now, we define F, letting F (b, n) = ⟨b, n⟩. For b ∈ pred(a), F (b, n) is a group element of order p and height |b|. For any σ ∈ T_{a}, apart from ∅, the last term of σ has the form ⟨b, n⟩, where |b| is the height of σ in G. For an arbitrary nonzero element of G, say g = n_{1}σ_{1} + … + n_{k}σ_{k}, where σ_{1}, …, σ_{k} ∈ T_{a}, the σ_{i} are incomparable, and n_{i} < p, the height of g is the minimum of the heights of the σ_{i}. Thus, we can pass effectively from g to the notation b <_{O} a for its height. From this, we get a computable function H on the nonzero elements of G, such that if g is the n^{th} element of height |b|, then H(g) = (b, n).

From the lemma, using Barwise-Kreisel Compactness, we get a Harrison pgroup G and computable 1 − 1 functions F and H with the following properties:

1. F is defined on (b, n) for all b in some computable end extension A′ of A and all n ∈ ω.

2. For b ∈ A, F (b, n) has height |b|, and for b′ ∈ A′, if b′ ≠ b, then F (b′, n) does not have height |b|.

3. H is defined on all nonzero elements of G.

4. For b ∈ A, H maps the elements of height |b| onto the pairs of the form (b, n).

Let R be the set of height-possessing elements of G. To determine whether x ∈ R, using A, we first check that x is a nonzero element of G, and then see if the first component of H(x) is in A. To determine whether x ∈ A, using R, we first check that x ∈ A′, and then see if F (x, 0) ∈ R.

The next result says that WH ⊆ L.

Proposition 5.9 Let (H, <) be a Harrison ordering, and let R be the maximal well-ordered initial segment. Then there is a tree T with no hyperarithmetical path, such that if f is its left-most path, then f ≡_{T} R.

Proof: By Theorem 5.1, we may suppose that H has no infinite hyperarithmetical decreasing sequence. Consider then the tree T of decreasing sequences in H; i.e.,

σ ∈ T ⇔ (∀n < lh(σ)) [ σ(n − 1) <_{H} σ(n) ] .

By our assumption, T has no hyperarithmetical path, so it is in N. If f is the left-most path of T, then f has degree in L.

Claim: f ≡_{T} R.

Proof of Claim: To see that f ≤_{T} R, note that given f ↾ n, f(n) is the least k such that k <_{H} f(n − 1) and k ∉ R. To prove that R ≤_{T} f, we show that n ∉ R ⇔ (∃k ≤ n+1) [f(k) ≤_{H} n]. The implication from right to left is trivial. For the other direction, we note that f is an increasing function, because any value for f(n) could have been used as f(k), for any k < n (and we could then continue on with the values of f(n + i)) except that f must be left-most. Thus, f(n + 1) > n. Let k ≤ n be least such that f(k + 1) > n. As n ∉ R, the only possible reason not to choose n as f(k + 1) is that f(k) ≤_{H} n, as required.

The next result says that SH ⊆ L̂.

Proposition 5.10 Let B be a Harrison Boolean algebra, and let S be the superatomic part. Then there is a computable tree T whose left-most path f is not hyperarithmetical, such that S ≡_{T} f.

Without loss of generality, we may suppose that B has universe ω. We have the usual order relation on B given by x ≤_{B} y ⇔ (x ∧ y = x). The crucial property we need is the following.

Lemma 5.11 b ∉ S iff there is a dense set (dense in the ordering ≤_{B}) below b.

Proof of Lemma 5.11: First, suppose that b = b_{0} ∉ S. Then b is a nonzero element of B/S = B′, which is atomless, and so we can split b_{0} in B/S to get b_{1} with 0 <_{B′} b_{1} <_{B′} b_{0}. Indeed, given any d <_{B′} c ≤_{B′} b_{0}, we can split c − d in B′. From this, it follows that we can build a dense set in B′ below b_{0}. For the other direction, suppose {b_{i} : i > 0} is a dense set in <_{B} below b_{0}. Note that by induction, every b_{i} is a nonzero element of every Cantor-Bendixson derivative of B, so all of them are in the complement of S.

For the proof of Proposition 5.10, we begin our analysis of S with a computable ordering <_{Q} of ω that is dense, with right endpoint but no left endpoint, in which 0 is the right endpoint. We now define a computable tree T all of whose paths are associated with dense sets below infinitely many elements of B, and whose left-most path, f, has the same degree as S. Let T consist of the finite sequences σ with the following two properties:

1. (∀ ⟨n, m⟩, ⟨n, m′⟩ < lh(σ) ) [ σ(⟨n, m⟩) <_{B} σ(⟨n, m′⟩) ↔ m <_{Q} m′]

2. (∀n < m) [ m < lh(σ) → σ(⟨n, 0⟩) < σ(⟨m, 0⟩) ].

It is clear that for every infinite path f in T and every n, {f(⟨n, m⟩) : m > 0} is a dense set in <_{B} below f(⟨n, 0⟩). Let f be the left-most path in T.

Claim: f ≡_{T} S.

Note that from the claim, it follows that f is not hyperarithmetical, and deg(S) ∈ L̂, as required.

Proof of Claim: First, we argue that f ≤_{T} S. Suppose we have f ↾ s and s = ⟨n, m⟩. If m = 0, then f(s) is the least k such that

(∀l) [ ⟨l, 0⟩ < s → f(⟨l, 0⟩) < k] & k ∉ S .

If m > 0, suppose that e and i are the immediate predecessor and successor, respectively, of m in <_{Q}↾ (m + 1) × (m + 1). Now, f(s) is the least k such that

f(⟨n, e⟩) <_{B} f(⟨n, i⟩) and k − f(⟨a, e⟩), f(⟨a, i⟩ − k ∉ S .

Now, we argue that S ≤_{T} f. We claim that n ∈ S if and only if

(∀m ≤ n) [n ≠ f(⟨m, 0⟩] .

The point here is that at every ⟨m, 0⟩ for m ≤ n, f has as its value the least (in the ordering of ω) k ∉ S not yet chosen as one of these values.

The next result says that DH_{p} ⊆ L̂.

Proposition 5.12 Let G be a Harrison p-group, and let D be its divisible part. Then there is a computable tree T with left-most path f such that f is not hyperarithmetical, and f ≡_{T} D.

The proof is similar to that for Proposition 5.10. Again, we suppose that G has universe ω. We have

b ∈ D ⇔ (∃(b_{i})_{i∈ω})[b_{0} = b & (∀i) (b_{i} = p · b_{i+1})] .

We now define the appropriate tree. Let T consist of the finite sequences σ such that

1. (∀⟨n, m⟩) [ σ(⟨n, m⟩) = p · σ(⟨n, m + 1⟩) ] and

2. (∀n < m) [ m < lh(σ) → σ(⟨n, 0⟩) < σ(⟨m, 0⟩) ].

The argument is now much like the one for Boolean algebras. Let f be the left-most path in T. Given f ↾ s and s = ⟨n, m⟩, if m = 0, then f(s) is the least k such that

(∀l) [ ⟨l, 0⟩ < s → f(⟨l, 0⟩) < k] & k ∈ D .

If m > 0, then f(s) is the least k ∈ D such that f(s) = p · k. Again, for the other direction, n ∉ D iff (∀m ≤ n) [ n ≠ f(⟨m, 0⟩) ]. Thus, f ≅_{T} D, so f is not hyperarithmetical, and its Turing degree is in L̂, as required.

Theorem 5.13 P = L = L̂ = WH = SH = DH_{p}.

Proof: We have all of the pieces. Clearly, L ⊆ L̂, and by Corollary 5.4, L̂ ⊆ P. By Proposition 5.3, P ⊆ WH. By Theorem 5.5, P ⊆ SH, and by Proposition 5.7, P ⊆ DH_{p}. By Proposition 5.9, WH ⊆ L. Finally, by Propositions 5.10 and 5.12, SH, DH_{p} ⊆ L̂.

In view of the results in this section, it is natural to ask whether for all computable structures A of rank ω_{1}^{CK} + 1, and all tuples \overline{a} witnessing the rank, if R is the complement of the orbit of \overline{a}, the degree spectrum of R must be P. In fact, this is not true.

Example: Let C be an arbitrary Π_{1}^{1} set. Let (A_{n})_{n∈ω} be a uniformly computable sequence of linear orderings such that A_{n} has computable order type if n ∈ C, and type ω_{1}^{CK}(1 + η) if n ∉ C. Let A consist of an equivalence relation partitioning the universe into infinitely many equivalence classes, corresponding to the universes of the orderings A_{n}, and a binary relation that is the union of the orderings on the structures A_{n}. In A, suppose that we can effectively determine the orderings A_{n} and their first elements. (Of course, there are computable copies of A in which we cannot do this.) Let a be the first element in some equivalence classes on which the ordering has type ω_{1}^{CK}(1 + η), and let R be the complement of the orbit of a. For the given copy A, R ≡_{T} C. We can take C to be properly Π_{1}^{1}, but not of degree in P. In the next section we will show that there are such sets. In particular, we may take C to be properly Π_{1}^{1} of minimal degree, and P contains no minimal degree.

6 Paths through O

We have seen that for some intrinsically Π_{1}^{1} relations (the maximal well-ordered initial segments in Harrison orderings, the superatomic parts of Harrison Boolean algebras, and the height-possessing parts of Harrison groups), the degree spectrum is equal to the set P of degrees of Π_{1}^{1} paths through O. The results on these intrinsically Π_{1}^{1} relations gain meaning from results on P. Older results are found in papers of Parikh [27], Jockusch [19], and Friedman [11]. Friedman showed that there is a Π_{1}^{1} path Turing equivalent to O. We show that there are many further possibilities.

To obtain results about P, we convert questions about Π_{1}^{1} paths through O to questions about left-most paths through trees. A κ-tree T is a subset of κ^{<ω} that is closed under initial segments. We will be interested in the cases where κ = 2 and κ = ω. If κ = 2, we speak of binary branching trees. If κ = ω, we speak of ω branching trees, or simply trees.

For a tree T ⊆ ω^{<ω}, we are interested in the set

[T] = {f ∈ ω^{ω} : (∀x) f ↾ x ∈ T }

of all paths through T. Note that if T is computable, then [T] is a Π_{1}^{0} class of functions f : ω → ω; i.e., there is a computable predicate R such that [T] = {f ∈ ω^{ω} : (∀x) R(f ↾ x)}. Conversely, for every Π_{1}^{0} class, there is a computable tree whose paths are precisely the members of this class. The functions in the Π_{1}^{0} class defined by (∀x) R(f ↾ x) are precisely the paths through the tree T = {σ : (∀x ≤ lh(σ)) R(f ↾ x)}.

An important tool in our analysis will be the ability to convert a Δ_{2}^{0} tree to a computable tree with paths of the same Turing degrees. One conversion is well known. If T is a Δ_{2}^{0} tree, then [T] is a Π_{2}^{0} class of functions in ω^{ω}; i.e., there is a computable predicate R such that

[T] = {f ∈ ω^{ω} : (∀x) (∃y) R(f ↾ x, f ↾ y)} .

Let g be the least Skolem function, so for each x, g(x) is the least y such that R(f ↾ x, f ↾ y). Then g ≤_{T} f. For f, g ∈ ω^{ω}, let ⟨f, g⟩ be the function on ω such that

⟨f, g⟩(2n) = f(n) and ⟨f, g⟩(2n + 1) = g(n) .

For σ, τ ∈ ω^{<ω}, where lh(σ) = lh(τ), we define ⟨σ_{,}τ⟩ in a similar way. We have a computable tree T̂ whose paths are the functions ⟨f, g⟩ such that f ∈ [T] and g is the least Skolem function, as above. There is a 1 − 1 degree-preserving correspondence between [T] and [T̂].

By another definition, common in computability theory, a binary tree is a function F : 2^{<ω} → 2^{<ω} that preserves both order (⊆) and nonorder (⊈) (see, for example, [25]). Trees of this kind correspond to binary trees of the kind above with a special feature—they are “perfect”. The obvious analog for an ω-tree is a function F : ω^{<ω} → ω^{<ω} that preserves both order and nonorder.

So, for κ ∈ {2, ω}, we refer to a function F : κ^{<ω} → κ^{<ω} that preserves both ⊆ and ⊈ as an f-κ-tree—the “f” stands for “function”. The set of paths through the function tree F is

[F] = {f ∈ κ^{ω} : (∃g ∈ κ^{ω}) [f = ∪_{n∈ω}F (g ↾ n)]} .

We would like to know that X-computable trees described in the different ways (κ-trees, or f-κ-trees) give rise to the same sets of paths, or at least the same sets of Turing degrees of paths. In the case where κ = 2, there is nothing to worry about, at least in one direction. For each X-computable f-binary tree F, there is an X-computable binary tree T_{F}, uniformly computable in F, such that F and T_{F} have the same paths. We let

T_{F} = {σ : (∃τ) [σ ⊆ F (τ)]} .

The relation in the other direction is more complicated since, for example,

[F] is always a nonempty perfect set, while T may have isolated paths, and terminal nodes. However, these are the only restrictions. If every node in T splits, i.e., for all σ ∈ T,

(∃τ_{0}, τ_{1} ∈ T) (∃k < lh(τ_{0}), lh(τ_{1})) [ σ ⊆ τ_{0}, τ_{1} & τ_{0}(k) ≠ τ_{1}(k) ],

then there is an f-tree F, computable in T, with the same paths as T. We can define F by recursion. We let F (∅) = ∅, and given F (σ) = ρ ∈ T, we find the shortest τ ⊇ ρ such that τˆ 0, τˆ 1 ∈ T and set F (σˆ i) = τˆ i.

For ω-trees, even the first direction is unclear, in general. The problem is that [F] need not be a closed set, so it need not be the set of paths on a tree. A condition on the function F sufficient to eliminate this problem is that all the branches at each node are already distinguished at some fixed finite length; i.e.,

(∀σ) (∃t) (∀m ≠ n) [ F (σˆ m) ↾ t ≠ F (σˆ n) ↾ t] .

Another problem is making T_{F} computable in F. For binary trees, the quantification over τ is essentially bounded by the length of σ, and so there is no difficulty. For ω-trees we add another restriction. We require that F preserve lexicographic order (<_{L}) as well, i.e.

(∀σ) (∃t) (∀m < n) [F (σˆ m) ↾ t <_{L} F (σˆ n) ↾ t] .

For binary trees, this is no real restriction on the paths, since we can always switch the values 0 and 1. In this paper, we consider only such f-trees.

For an X-computable f-tree F of the kind we are considering, T_{F} is always an X-computable tree with the same paths as F. For κ = ω, we argue (briefly) that T_{F} is computable uniformly in F. Given σ, we can determine whether it is in T_{F}, using oracle F. We begin with ∅ and check whether F (∅) ⊇ σ or F (∅) ⊆ σ. Inductively, we may assume that F (ρ) ⊆ σ. Then we compute F (ρˆ i), for i = 0, 1, …, until we find i such that one of the following holds:

(i) F (ρˆ i) ⊇ σ, (ii) F (ρˆ i) ⊆ σ, or

(iii) σ is to the left of F (ρˆ i).

In case (i), we conclude that σ ∈ T_{F}, and in case (iii), we conclude that σ ∉ T_{F}. In case (ii), we continue on to the successors of ρˆ i. This process must terminate in at most lh(σ) steps.

Recall that N is the set of computable trees that have a path, but not one that is hyperarithmetical, L̂ is the set of Turing degrees of left-most paths in these trees, and P is the set of degrees of Π_{1}^{1} paths through O. In the previous section, we showed that P = L̂.

Proposition 6.1 If c ∈ P, and d is the Turing degree of the left-most path in a computable tree, then c ∨ d ∈ P. Hence, P is closed under join, and also under join with any hyperarithmetical degree.

Proof: Given c ∈ P, choose T_{0} ∈ N such that the left-most path in T_{0} has degree c. Let T_{1} be another computable tree (in N or not), in which the left-most path has degree d. Form the sum tree

T = T_{0} ⊕ T_{1} = {⟨σ_{0}, σ_{1}⟩ : σ_{i} ∈ T_{i} & lh(σ_{0}) = lh(σ_{1})} .

It is clear that T ∈ N, and the left-most path in T is ⟨f_{0}, f_{1}⟩, where f_{i} is the left-most path in T_{i}. By Theorem 5.13, deg(⟨f_{0}, f_{1}⟩) ∈ P, and it is immediate that deg(⟨f_{0}, f_{1}⟩) = c ∨ d, as required.

Parikh [27] and Friedman [11] provide some restrictions on the degrees in P by showing that a hyperarithmetical degree which is weak truth table reducible (wtt-reducible) to all x ∈ P must be computable. This fact can be used to show that there is a properly Π_{1}^{1} degree not in P. Standard initial segment constructions produce sets X such that any set Turing reducible to X is also truth table reducible (tt-reducible) to X, and it is possible to make X also properly Π_{1}^{1}. However, there are much more severe restrictions on the degrees in P.

We say that a function h dominates f if f(n) ≤ h(n) for all but finitely many n, and h majorizes f if f(n) ≤ h(n) for all n.

Proposition 6.2 If f is the left-most path in a computable tree T, and f is not hyperarithmetical (e.g., f ∈ P), then no hyperarithmetical function h dominates f.

Proof: Suppose h is a hyperarithmetical function dominating f. By a finite change, we may assume that h majorizes f. Consider the h-computable tree

S = {σ : σ ∈ T & (∀n < lh(σ)) [σ(n) ≤ h(n)]} .

Since h majorizes f, f is the left-most path in S, as well as in T. Now, S is computable in h and h-computably bounded. By relativizing the fact that the left-most path in a computable and computably bounded tree is Δ_{2}^{0}, we conclude that f is Δ_{2}^{0} relative to h. Hence f is hyperarithmetical, which contradicts the assumption.

A degree c is array non-computable (or anc) iff for each h ≤_{wtt} ∅′, there is a function f of degree at most c such that h does not dominate f. A function f is 1-generic if each computable Σ_{1} statement about f is decided by some finite initial segment. Equivalently, f is 1-generic iff for every c.e. set W_{e} of finite sequences, f satisfies (∃σ ⊆ f) [σ ∈ W_{e} ∨ (∀τ ⊇ σ) τ ∉ W_{e}]. The degree c is 1-generic if it contains a 1-generic function.

Corollary 6.3 Let c ∈ P.

1. c is anc, so it is not minimal.

2. There is a 1-generic degree ≤ c.

3. Any computable lattice with 0, 1 can be embedded in D(≤ c), preserving 0, 1.

4. c is the supremum of two 1-generic anc degrees that form a minimal pair.

5. For every b > c, there exists d < b such that c ∨ d = b.

Proof: The statements now all follow by results of Downey, Jockusch, and Stob [9].

Of course, there are many properly Π_{1}^{1} degrees that are not anc degrees— even minimal ones. To see this, we use 1-trees from Lachlan [24]. Take a Δ_{3}^{0} function f : ω → 3 such that D = {n : f(n) = 2} is infinite, and every function gotten by replacing each of the values 2 by either 0 or 1 (independently) gives a function of minimal degree. Suppose C is properly Π_{1}^{1}. If D is listed in increasing order as d_{0} < d_{1} < d_{2} < …, and g is the function that agrees with f on \overline{D} and has value C(i) on d_{i}, then g has the desired degree. Many other examples of properly Π_{1}^{1} degrees that are not in P can be constructed in the same way.

We wish to provide examples of the types of degrees that do occur in P, and to analyze the internal structure of P. We continue to use L̂. We begin with a relatively simple construction that provides a solution to a question raised in Friedman [11] and Jockusch [19], by showing that there are degrees in L̂, and, hence, in P, that do not compute ∅′. (At the time this was asked, it was also a question whether every element of P had the same degree as O.) In fact, we build a Δ_{2}^{0} tree T in which each paths is 1-generic, but none is hyperarithmetical. It follows that there is a computable tree T̂ with the same properties (the paths have the same degrees). The left-most path in T̂ will be our desired element of L̂. The key idea is to construct an f-tree F in which all paths are 1-generic, and then code a tree S ∈ N into a subtree of F.

Definition 6.4 If S is a tree, and F is an f-tree, then the S-subtree of F is the tree S(F) = {σ ∈ ω^{<ω} : (∃τ) [ σ ⊆ F (τ) & τ ∈ S]}.

For example, if S is ω^{<ω}, then S(F) = T_{F}.

Remark: If S is an X-computable tree, and F is an X-computable f-tree, then S(F) is also an X-computable tree, and [S(F)] ⊆ [F] (justifying the term subtree). Each path g ∈ [S] corresponds to a path ∪_{n}F (g ↾ n) in [S(F)], and vice versa. Moreover, if f ∈ [S(F)], we can form g ∈ ω^{ω} such that f = ∪_{n}F (g ↾ n). Then g is a path in S that is computable in f and X. The fact that g is a path in S is clear from the definition of S(F). To compute g(n), assume we have g ↾ n = τ, where F (τ) = f ↾ m. There is a unique i such that F (τ ˆ i) is an initial segment of f, and this is g(n).

We can now prove the following theorem.

Theorem 6.5 There is a 1-generic degree (and, hence, one not above 0′) in P.

Proof: First, we define, by recursion, a Δ_{2}^{0} f-tree F, all of whose paths are 1-generic. Let F (∅) = ∅. Suppose we have defined F (σ), where lh(σ) = n. If there is some τ ⊇ F (σ)ˆ i such that φ_{i}^{τ} (i) ↓, then let F (σˆ i) be the first one found in some standard computable search. If not, let F (σˆ i) = F (σ)ˆ i. Next, let S be any tree in N. Consider the Δ_{2}^{0} tree S(F). If f is a path in S(F), then f is 1-generic, since it is a path in [F]. Moreover, f ⊕ ∅′ computes a path in S, by the remark above, and so cannot be hyperarithmetical. Thus, every path in the computable tree T_{S(F)} has 1-generic Turing degree, and none are hyperarithmetical. The left-most path in T_{S(F)} is then our desired element of L̂, and of P.

This construction has many possible variations, incorporating coding of Δ_{2}^{0} sets, avoiding upper cones, and relativization to any Π_{1}^{0} singleton. Using these ideas, it is possible to produce, for example, incomparable degrees in P. More complicated results, such as the existence of minimal pairs, require interactions between sets, and normally involve a construction that is carried out in an interleaving fashion. We can produce a minimal pair by constructing a Δ_{2}^{0} binary tree F such that any two paths on it form a minimal pair. It is not clear how to construct such a tree that is ω-branching. To show that there is a minimal pair in P, we use a more careful analysis of the degree-preserving translation of Π_{2}^{0} classes into Π_{1}^{0} classes in the case where the first class is the set of paths on a Δ_{2}^{0} tree.

Proposition 6.6 If T is a Δ_{2}^{0} tree, then there is a computable tree T̂ such that there is a 1−1 degree-preserving correspondence between [T] and [T̂], which also preserves lexicographic order. In particular, the left-most paths in T and T̂ have the same degree.

Proof: As remarked on p. 69 in [20], in terms of Π_{1}^{0} classes, for every Δ_{2}^{0} tree T, there is a computable predicate R such that the Δ_{2}^{0} tree

T′ = {σ : (∃y) R(σ, y)}

has the same paths as T. We convert T to a computable tree by using least Skolem functions again. Let

T̂ = {⟨σ, τ⟩ : lh(σ) = lh(τ) &
(∀n ≤ lh(σ)) [ R(σ ↾ n, τ(n)) & (∀m < τ(n)) ¬R(σ ↾ n, m) ]}.

It is clear that if ⟨f, g⟩ ∈ [T̂], then f ∈ [T] and for all n, g(n) is the least y such that R(f ↾ n, y). Conversely, if f ∈ [T], and for all n, g(n) is the least y such that R(f ↾ n, y), then g ≤_{T} f (and so ⟨f, g⟩ ≡_{T} f) and ⟨f, g⟩ ∈ [T̂]. Finally, if f_{1}, f_{2} ∈ [T], where f_{1} <_{L} f_{2}, and g_{1}, g_{2} are the corresponding least Skolem functions, then ⟨f_{1}, g_{1}⟩ <_{L} ⟨f_{2}, g_{2}⟩. That is, if they first differ at an even number, then they are ordered as are f_{1}, f_{2}, while if they first differ at an odd number, then there is at most one value for g that can lie on the tree T̂ at all.

We can now construct a pair of f-trees F_{i} such that the set of degrees of corresponding paths have some property (e.g., they form a minimal pair), then take some single S, and apply this proposition to the pair S(F_{i}) = T_{i} to show that the left-most paths in T_{i} have these properties as well. We provide a sample result.

Theorem 6.7 There are Turing degrees c, d ∈ P that form a minimal pair; i.e., c ∧ d = 0.

Proof: We define two f-trees F_{0}, F_{1}, both Δ_{2}^{0}, such that for any f ∈ ω^{ω}, the Turing degrees of the two paths ∪_{n}F_{i}(f ↾ n) form a minimal pair. We proceed by induction on lh(σ), beginning with F_{i}(∅) = i. Suppose we have defined F_{i}(σ) for σ of length e, and we wish to define F_{i}(σˆ n). We ask if there exist τ_{i} ⊇ F_{i}(σ)ˆ n, i = 0, 1, and x such that φ_{e}^{τ_{0}}(x) ≠ φ_{e}^{τ_{1}}(x). If so, we choose the first such pair τ_{i} in some standard search, and we let F_{i}(σˆ n) = τ_{i}. If there do not exist such τ_{i} and x, then we let F_{i}(σˆ n) = F_{i}(σ)ˆ n. The standard argument used in the construction of a minimal pair shows that for every f ∈ ω^{ω}, the degrees of ∪_{n}F_{i}(f ↾ n), for i = 0, 1, form a minimal pair.

Now, let S be any tree in N, and consider S(F_{i}) = T_{i}. Every path on T_{i} is of the form ∪_{n}F_{i}(f ↾ n), for some f ∈ S, and this correspondence preserves lexicographic order; i.e., if f_{1} <_{L} f_{2} are in [S], then

∪_{n}F_{i}(f_{1} ↾ n) <_{L} ∪_{n}F_{i}(f_{2} ↾ n) ,

by our requirements on f-trees preserving lexicographic order. Thus, if f is the left-most path in S, then for i = 0, 1, f_{i} = ∪_{n}F_{i}(f ↾ n) is the left-most path in T_{i}, and f_{0}, f_{1} form a minimal pair. The corresponding paths f̂_{i} in T̂_{i} have the same degrees, and so also form a minimal pair. Since there is no hyperarithmetical path in S, it follows that there is no hyperarithmetical path in S(F_{i}), or in T̂_{i}. Thus, the degrees of the paths f̂_{i} form a minimal pair in P.

We can generalize the construction above to build infinitely many mutually generic degrees in P.

Theorem 6.8 There are functions f_{i}, for i ∈ ω, with degrees in P which are mutually 1-generic. In fact, we can arrange that ⊕_{i}f_{i} is 1-generic, and the degrees of ⊕_{i}f_{i} and all f_{i} are in P. As a further refinement, we may take the degree of ⊕_{i}f_{i} to be computable in any degree in P that is above 0′.

Proof: We first build uniformly Δ_{2}^{0} f-trees F_{i} such that for all f ∈ ω^{ω}, ⊕_{i}∪_{n}F_{i}(f ↾ n) is 1-generic. We define F_{i}(σ), for σ ∈ ω^{<ω}, by induction on lh(σ), beginning with F_{i}(∅) = ∅. Suppose we have F_{i}(σ), for i ∈ ω, where lh(σ) = e. We wish to define F_{i}(σˆ n). We ask if there are τ_{i} ⊇ F_{i}(σ)ˆ n such that τ = ⊕_{i}τ_{i} forces the e^{th} computable Σ_{1} statement about G = ⊕_{i}G_{i}—a sample statement would be φ_{k}^{τ}(k) ↓. This question can be answered using the Δ_{2}^{0} oracle, since without loss of generality, we may suppose that all but finitely many of the τ_{i} are F_{i}(σ)ˆ n. If so, then we choose the first sequence (τ_{i})_{i∈ω} witnessing this fact, and let F_{i}(σˆ n) = τ_{i}. If not, then we let F_{i}(σˆ n) = F_{i}(σ)ˆ n.

Suppose c ∈ P, and let S ∈ N be such that the left-most path f in S has degree c. Consider the Δ_{2}^{0} trees T_{i} = S(F_{i}), and the left-most paths f_{i} in these trees. By construction, ⊕_{i}f_{i} is 1-generic. By the remark before Theorem 6.5, if c ≥ 0′, then the f_{i} are uniformly computable in c. In any case, for each i, f_{i} has the same degree as the left-most path in T̂_{i}, so the degrees are all in P, as required.

Finally, we consider the sum tree ⊕_{i}T_{i}. Let us say what this is. First, for σ ∈ ω^{<ω}, let σ_{i} = (σ⟨i, n⟩)_{⟨i,n⟩<lh(σ)}. Then

⊕_{i}T_{i} = {σ ∈ ω^{<ω} : (∀i) [⟨i, 0⟩ < lh(σ) → σ_{i} ∈ T_{i}]} .

Then T = ⊕_{i}T_{i} is in N, and the left-most path through T, call it ⊕_{i}f_{i}, has degree in P. By the uniformity of the reductions, if ∅′ ≤_{T} X, then ⊕_{i}f_{i} ≤_{T} X.

Corollary 6.9 Every countable distributive lattice can be embedded in P, and in P(≤ c), so long as 0′ ≤ c ∈ P. It follows that every countable upper semilattice can be embedded in P.

By the use of lattice tables, one can embed every computable lattice in P—not just the distributive ones.

In Theorem 6.8, if we consider finite sums, and give up the full genericity of ⊕_{i}f_{i}, then we can take the f_{i} so that the Turing degrees are independent and pairwise minimal. In addition, we can give ⊕_{i}f_{i} degree c, for any desired c ∈ P such that c ≥ 0′. Thus, for example, for any such degree c, we can embed any finite Boolean algebra in P so that the top is c and the bottom is 0.

We will now give a new solution to Problem 71 on Friedman’s list [10]^{4}.

Theorem 6.10 There exists c ∈ P such that 0 is the only hyperarithmetical degree ≤ c.

Proof: First, we build a set of sequences that satisfies the definition of a Δ_{2}^{0} f-tree F except that the domain consists of pairs ⟨σ, τ⟩, of the same length, with σ ∈ 2^{<ω} and τ ∈ ω^{<ω}—the range will be contained in ω^{<ω}. We begin with F (⟨∅, ∅⟩) = ∅. Suppose F is defined for ⟨σ, τ⟩ with lh(σ) = lh(τ) = e. We find the first pair σ_{0}, σ_{1} ⊇ F (⟨σ, τ⟩) and the first x_{σ,τ} (in some standard order) such that σ_{0} <_{L} σ_{1} and φ_{e}^{σ_{0}}(x_{σ,τ}) ↓≠ φ_{e}^{σ_{1}}(x_{σ,τ}) ↓, and we let F (⟨σˆ i, τ ˆ n⟩) = σ_{i} ˆ n. If there do not exist such σ_{0}, σ_{1} and x_{σ,τ}, then we let F (⟨σˆ i, τ ˆ n⟩) = σˆ iˆ n.

Consider the corresponding Δ_{2}^{0} tree T_{F} with the same paths as F. Let S ∈ N, where each path starts with 1 and has degree above all the hyperarithmetical degrees, as in Friedman [11]. We take a subtree Ŝ of T_{F} in which each path codes a path through S, and we diagonalize against every set that is computable in the coded path but is not itself computable. We let Ŝ be the downward closure of the set of nodes F (⟨σ, τ⟩) such that τ ∈ S and

(∀e < lh(σ)) ¬[ φ_{e}^{F (⟨σ,τ⟩)}(x_{σ↾x,τ↾x}) ↓= φ_{e}^{τ}(x_{σ↾x,τ↾x}) ↓] .

It is clear that S is a Δ_{2}^{0} tree with no hyperarithmetical path (as before, for any path f in S, f ⊕ ∅′ computes a path through Ŝ). Thus, the leftmost path f in S has degree in P. Let g be the path in Ŝ corresponding to f. Now, suppose some hyperarithmetical set is computable in f. It is then computable in g, by our choice of S. By Posner’s trick, we may suppose that there exists an e such that φ_{e}^{f} = φ_{e}^{g}. Let σ and τ have length e, let i ∈ {0, 1}, and let n ∈ ω be such that F (⟨σˆ i, τˆ n⟩) ⊆ f. If there were σ_{0}, σ_{1} and x_{σ,τ} as described above, then let σ̂ ⊇ σˆ i and τ̂ ⊇ τˆ n be such that F (⟨σ̂, τ̂⟩) ⊆ f and φτ̂ ; e(x_{σ,τ}) ↓. It is clear from the definition of S that φ_{e}^{F (⟨σ ˆ i,τ ˆ n⟩)}(x_{σ↾x,τ↾x}) ↓ and so as F (⟨σˆ i, τ ˆ n⟩) ⊆ f and τ̂ ⊆ g, we have contradicted our assumption that φ_{e}^{f} = φ_{e}^{g}. On the other hand, if there do not exist σ_{0}, σ_{1} and x_{σ,τ} as described above, then, since F (⟨σ, τ⟩) ⊆ f, φ_{e}^{f} is computable.

If, instead of standard Turing reducibility, one is interested in the stronger reducibilities given by allowing some added fixed hyperarithmetical set, then results corresponding to most of the ones above can be derived by relativization. One such set of relativizations gives information about the α-degrees, introduced in Section 2 (see the paragraph before Theorem 2.10). Again, we let Δ_{α}^{0} be a complete Δ_{α}^{0} set, and we use the notation also for its Turing degree.

4Based on a completely different and more complex method, Steel [36] provided a relativized solution to Friedman’s problem. Harrington [16] also outlined, using a very different method, how a solution to Friedman’s problem can be obtained. Steel’s method [36] involves a forcing technique for ω branching trees whose paths are not easily definable from one another, even when the defining formulas allow a parameter for the tree itself. Steel’s method often produces only relativized results. After Steel completed his work, Harrington [16] found a powerful method for obtaining the unrelativized versions of similar results, using iterated priority arguments. Both Steel’s and Harrington’s techniques are quite different from, and more complicated than, ours.

If c ∈ P, then by Corollary 6.3, c is anc relative to Δ_{α}^{0}. Relativizing the proofs about anc sets, we obtain a set that is 1-generic relative to Δ_{α}^{0}, of degree below c ∨ Δ_{α}^{0}. Then we can embed every countable partial ordering in the αdegrees below c ≡_{Δ_{α}^{0}} c ∨ Δ_{α}^{0}. For the arguments involving constructing various computable trees and considering the properties of their left-most paths, we relativize the entire construction to Δ_{α}^{0} to get Δ_{α}^{0} trees T_{i} whose paths have the desired properties.

For Theorem 6.8, we get Δ_{α}^{0} trees T_{i} with left-most paths f_{i} such that ⊕_{i}f_{i} is 1-generic over Δ_{α}^{0}. Let h_{α} be the characteristic function of Δ_{α}^{0} (our complete Δ_{α}^{0} set), and let R_{i} be a computable tree in which h_{α} is the only path. Let the tree T̂_{i} be

{⟨σ, τ⟩ : lh(σ) = lh(τ) & σ ∈ S & (∀n < lh(σ)) R_{i}(σ ↾ n, τ ↾ n)} .

It is clear that if ⟨h, g⟩ ∈ [T̂_{i}], then h = h_{α}. Moreover, g ∈ [T_{i}] and ⟨h, f_{i}⟩ is the left-most path in T̂_{i}. Thus, the degree of f_{i} ⊕ h_{α} is in P. Since the f_{i} ⊕ h are Turing independent, the f_{i} themselves are independent with respect to ≤_{Δ_{α}^{0}}. Similarly, the relativization of Theorem 6.10 yields some c ∈ P such that for any hyperarithmetical d, if d ≤ c ∨ Δ_{α}^{0}, then d ≤ Δ_{α}^{0}; i.e., if a hyperarithmetical set X is Δ_{α}^{0}-reducible to some set in c, then X has α-degree 0.

We close this section with an application of these ideas to a problem about trees of minimal degrees. Before thinking of Theorem 5.13 and realizing how to prove Proposition 6.1, we tried to construct minimal degrees in P along the lines of the constructions above. The natural lemma to try for was the existence of a Δ_{2}^{0} f-tree F each of whose paths has minimal degree (or is hyperarithmetical), as then the left-most path in S(F) would represent the desired minimal degree in P. Indeed, it has often seemed that constructing an f-tree each of whose paths has minimal degree would be a useful first step in many arguments about minimal degrees.

More generally, it would have been pleasing to find a notion of forcing with f-trees which would produce minimal degrees; i.e., constructing for each e and each f-tree (condition) F, an f-subtree (refinement) all of whose paths g are either computable or computable in φ_{e}^{g}. If we had such a notion, then using it in an iterated fashion along all paths would produce an f-tree each of whose paths has minimal degree. Our observations above show that there is no such tree computable in ∅′, and much more.

Proposition 6.11 There is no hyperarithmetical f-tree F each of whose paths is hyperarithmetical or else has minimal (or even array computable) degree. Indeed, this remains true even if we omit the restrictions that F preserves lexicographic order and that (∀σ) (∃t) (∀m ≠ n) [ F (σˆ m) ↾ t ≠ F (σˆ n) ↾ t], so long as [F] is required to be a closed set.

Proof: Suppose we are given a hyperarithmetical order and nonorder preserving F̂ : ω^{<ω} → ω^{<ω} such that [F̂] is a closed set all of whose elements are either hyperarithmetical or array computable. We construct a hyperarithmetical f-tree F with the same properties. We proceed by recursion, starting by letting F (∅) = F̂(∅). Suppose F (σ) = F̂(τ). Let F̂(τ) have length m. If there are infinitely many different values for F̂(τˆ n)(m), then we choose a sequence n_{i} such that

i < j → F̂(τˆ n_{i})(m) < F̂(τˆ n_{j})(m) ,

and we let F (σˆ i) = F̂(τˆ n_{i}). If not, then we let m_{0} be the value of F̂(τˆ n)(m) for all but finitely many n, and let m_{0} be larger than all the exceptions.

We now ask if there are infinitely many different values for F̂(τˆ n)(m + 1). If so, we choose n_{i} > m_{0} such that

i < j → F̂(τˆ n_{i})(m + 1) < F̂(τˆ n_{j})(m + 1) ,

and let F (σˆ i) = F̂(τˆ n_{i}). If not, we let m_{1} be the value of F̂(τˆ n)(m + 1) taken on for almost all n. Continuing in this way, either we define F (σˆ i) so that F preserves lexicographic order and all F (σˆ i) differ at some one number in the common domain, as required, or else we build a function g(k) = m_{k} such that g is a limit point of F̂(τˆ n) but g is not in [F̂], for a contradiction. Now, F is clearly hyperarithmetical, as F̂ was, and F is an f-tree in our restricted sense. Thus, we may suppose we have an f-tree F satisfying our restrictions, and the hypotheses of the proposition. Moreover, we may assume that we also have a hyperarithmetical function k which, for each σ, supplies a t such that

(∀s < t) [F (σˆ s) = F (σˆ t) & (∀m < n) (F (σˆ m)(t) < F (σˆ n)(t))] .

We again take S to be a computable tree with no hyperarithmetical paths, and we consider S(F) and its left-most path f, which corresponds to the leftmost path g in S. As before, f is not hyperarithmetical. We claim that there is no hyperarithmetical h that dominates f, and so f is anc, for the desired contradiction. Suppose h dominates f, so, without loss of generality, it is increasing and majorizes f. We shall define a hyperarithmetical function ĥ that dominates g, contradicting Proposition 6.2. We begin with ĥ(0) = h ∘ k(∅). Note that, by our choice of k, and the corresponding restrictions on F, g(0) ≤ f ∘ k(∅) < h ∘ k(∅) = ĥ(0), as desired. In general, we let

ĥ(n) = max{h ∘ k(σ) : lh(σ) = n & (∀m ≤ n)[σ(m) < ĥ(m)]}.

Clearly, ĥ is hyperarithmetical. Suppose that g(m) < ĥ(m) for each m < n and g ↾ n = τ, so F (τ) ⊆ f. As at 0, g(n) ≤ f ∘ k(τ) and so g(n) < h ∘ k(τ), and τ is one of the σ over which we take the maximum in the definition of ĥ. Thus, g(n) < ĥ(n), as required.

Thus, it seems that there is no way to force with conditions consisting of hyperarithmetical f-trees bounded in the hyperarithmetical hierarchy and produce a minimal degree.

References

[1] Ash, C. J., and J. F. Knight, “Possible degrees in recursive copies”, Annals of Pure and Applied Logic, vol. 75(1995), pp. 215–221.

[2] Ash, C. J., and J. F. Knight, “Possible degrees in recursive copies II”, Annals of Pure and Applied Logic, vol. 87(1997), pp. 151–165.

[3] Ash, C. J., and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Elsevier, 2000.

[4] Ash, C., J. Knight, M. Mannasse, and T. Slaman, “Generic copies of countable structures”, Annals of Pure and Applied Logic, vol. 42(1989), pp. 195– 205.

[5] Ash, C. J., and A. Nerode, “Intrinsically recursive relations”, in Aspects of Effective Algebra, ed. by J. N. Crossley, Upside Down A Book Co., Steel’s Creek, Australia, 1979, pp. 26–41.

[6] Barker, E., “Intrinsically Σ_{α}^{0} relations”, Annals of Pure and Applied Logic, vol. 39(1988), pp. 105–130.

[7] Barwise, J., “Infinitary logic and admissible sets”, J. Symb. Logic, vol. 34(1969), pp. 226–252.

[8] Chisholm, J., “Effective model theory vs. recursive model theory”, J. Symb. Logic, vol. 55(1990), pp. 1168–1191.

[9] Downey, R., C. G. Jockusch, Jr., and M. Stob, “Array nonrecursive degrees and genericity”, in Computability, Enumerability, Unsolvability: London Math. Soc. Lecture Notes Series 224, Cambridge Univ. Press, 1996, pp. 93–104.

[10] Friedman, H., “One hundred and two problems in mathematical logic”, J. Symb. Logic vol. 40(1975), pp. 113–129. .

[11] Friedman, H., “Recursiveness in Π_{1}^{1} paths through O”, Proc. of the Amer. Math. Soc., vol. 54(1976), pp 311–315.

[12] Goncharov, S. S., “The quantity of nonautoequivalent constructivizations”, Algebra and Logic, vol. 16(1977) (English translation), pp. 169–185.

[13] Goncharov, S. S., and J. F. Knight, “Computable structure and nonstructure theorems”, Algebra and Logic, vol. 41(2002), (English translation), pp. 351–373.

[14] Goncharov, S. S., V. S. Harizanov, J. F. Knight, C. McCoy, R. G. Miller, and R. Solomon, “Enumerations in computable structure theory”, submitted to Annals of Pure and Applied Logic.

[15] Harizanov, V. S., “Some effects of Ash-Nerode and other decidability conditions on degree spectra”, Annals of Pure and Applied Logic, vol. 55(1991), pp. 51–65.

[16] Harrington, L., “McLaughlin’s conjecture,” handwritten notes, 1976.

[17] Harrison, J., “Recursive pseudo-well-orderings”, Trans. of the Amer. Math. Soc., vol. 131(1968), pp. 526–543.

[18] Hirschfeldt, D. R., B. Khoussainov, R. A. Shore, A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures”, Annals of Pure and Applied Logic, vol. 115(2002), pp. 71–113.

[19] Jockusch, C. G. Jr., “Recursiveness of initial segments of Kleene’s O”, Fund. Math., vol. 87(1975), pp. 161–167.

[20] Jockusch, C. G. Jr., and T. G. McLaughlin, “Countable retracing functions and Π_{2}^{0} predicates”, Pacific J. Math., vol. 30(1969), pp. 67–93.

[21] Kaplansky, I., Infinite Abelian Groups, University of Michigan Press, 1954.

[22] Khousainov, B. and R. A. Shore, Computable isomorphisms, degree spectra of relations and Scott families, Annals of Pure and Applied Logic vol. 93 (1998), pp. 153–193.

[23] Kreisel, G., “Set theoretic problems suggested by the notion of potential totality”, in Infinitistic Methods (Proc. of Symp. on Found. of Math., Warsaw, 1959), Pergamon, 1961, pp. 103–140.

[24] Lachlan, A. H., “Solution to a problem of Spector”, Canad. J. Math. vol. 23(1971), pp. 247–256.

[25] Lerman, M. Degrees of Unsolvability, Springer-Verlag, Berlin, 1983.

[26] Manasse, M. S., Techniques and Counterexamples in Almost Categorical Recursive Model Theory, Ph.D. thesis, University of Wisconsin-Madison, 1982.

[27] Parikh, R., “A note on paths through O”, Proc. of the Amer. Math. Soc., vol. 39(1973), pp. 178–180.

[28] Ressayre, J. P., “Models with compactness properties relative to an admissible language”, Annals of Math. Logic, vol. 11(1977), pp. 31–55.

[29] Rogers, H., Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.

[30] Sacks, G. E., “On the number of countable models”, in Southeast Asian Conference on Logic (Singapore, 1981), ed. by C. T. Chong and M. J. Wicks, pp. 185–195, North-Holland, 1983.

[31] Sacks, G. E., Higher Recursion Theory, Springer-Verlag, 1990.

[32] Scott, D., “Logic with denumerably long formulas and finite strings of quantifiers”, in Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), ed. by J. Addison, L. Henkin, and A. Tarski, North-Holland, 1965, pp. 329–341.

[33] Soskov, I. N., “Intrinsically Π_{1}^{1} relations”, Math. Logic Quarterly, vol. 42(1996), pp. 109–126.

[34] Soskov, I. N., “Intrinsically hyperarithmetical sets”, Math. Logic Quarterly, vol. 42(1996), pp. 469–480.

[35] Spector, C. “Recursive well-orderings”, J. Symb. Logic, vol. 20(1955), pp. 151–163.

[36] Steel, J. R., “Forcing with tagged trees”, Ann. Math. Logic, vol. 15(1978), pp. 55–74.