Turing degrees of hyperjumps

Stephen G. Simpson Department of Mathematics

Vanderbilt University http://www.math.psu.edu/simpson

sgslogic@gmail.com

(Joint work with Hayden Jananthan)

Higher Recursion Theory National University of Singapore

May 20–29, 2019 Preamble.

In this talk I discuss some work in progress which involves both hyperdegrees and Turing degrees. This is in collaboration with my current Ph.D. student, Hayden Jananthan, at Vanderbilt University.

I start with Turing degree aspects of the Gandy Basis Theorem. From there I move along to hyperarithmetical analogs of several well-known theorems including the Jockusch-Soare Jump Inversion Theorem, the Posner-Robinson Join Theorem, and the Jockusch-Shore Pseudojump Inversion Theorem.

There are a number of open questions here, and I am hoping that some of you will help us solve them at this workshop.

Part 1: Refinements of the Gandy Basis Theorem

A Σ_{1}^{1} class is a set S ⊆ {0, 1}^{ℕ} of the form S = {X | ∃Y A(X, Y)} where X and Y range over {0, 1}^{ℕ} and A(X, Y) is an arithmetical predicate.

Kleene Basis Theorem (1959). Let S be a nonempty Σ_{1}^{1} class, then we can find X ∈ S such that X ≤_{T} O.

Here ≤_{T} denotes Turing reducibility, i.e., X ≤_{T} Y if and only if X ∈ Δ_{1}^{0,Y} . And O is Kleene’s O. The key property of O is that it is a complete Π_{1}^{1} subset of ℕ.

Gandy Basis Theorem (1960). Let S be a nonempty Σ_{1}^{1} class, then we can find X ∈ S such that X <_{hyp} O.

Here ≤_{hyp} denotes hyperarithmetical reducibility, i.e., X ≤_{hyp} Y if and only if X ∈ Δ_{1}^{1,Y} . And of course X <_{hyp} Y means that X ≤_{hyp} Y and Y ≰_{hyp} X. And X ≡_{hyp} Y means that X ≤_{hyp} Y and Y ≤_{hyp} X. And a hyperdegree is an equivalence class under ≡_{hyp}.

For X ∈ {0, 1}^{ℕ} the hyperjump of X is defined as O^{X} = Kleene’s O relative to X, i.e., a complete Π_{1}^{1,X} subset of ℕ. This is analogous to the Turing jump of X, defined as H^{X} = the Halting Problem relative to X, i.e., a complete Σ_{1}^{0,X} subset of ℕ.

A theorem of Spector 1955 tells us that X <_{hyp} O implies O^{X} ≡_{hyp} O. In other words, in the world of hyperdegrees, every “degree” less than the “jump” of the empty set is “low.” This is in contrast to the world of Turing degrees, where the situation is much more complicated.

Gandy’s proof of the Gandy Basis Theorem also gives X ≤_{T} O. Combining these results of Spector and Gandy, we obtain the following refinement of the Kleene Basis Theorem.

Theorem (Gandy, 1960). Let S be a nonempty Σ_{1}^{1} class, then we can find X ∈ S such that X ≤_{T} O and O^{X} ≡_{hyp} O.

It is appropriate to attribute this theorem to Gandy, and all of the relevant textbooks do so. But now consider the following apparently stronger theorem.

Theorem (folklore, ????). Let S be a nonempty Σ_{1}^{1} class, then we can find X ∈ S such that O^{X} ≡_{T} O.

Theorem (folklore, ????). Let S be a nonempty Σ_{1}^{1} class, then we can find X ∈ S such that O^{X} ≡_{T} O.

This “folklore” theorem was unknown to me until I proved it myself, last September, in some ongoing proof-theoretical work with Gerhard Jäger and Michael Rathjen. But later I discovered that the “folklore” theorem is known to many people. And still later I noticed that the “folklore” theorem appears – without proof or references – as Exercise 2.5.6 in the book Recursion Theory, by Chi Tat Chong and Liang Yu, 2015. Other than this, I know of no printed statement of the “folklore” theorem.

A straightforward way to prove the “folklore” theorem is by means of forcing with nonempty Σ_{1}^{1} classes. This technique was introduced by Harrington in 1976 and is well known in descriptive set theory. My first proof of the “folklore” theorem used Harrington’s technique, but later I devised another proof which is more in the spirit of Gandy and Spector.

We are considering two theorems. Theorem 1 (Gandy, 1960). Let S be a nonempty Σ_{1}^{1} class, then we can find X ∈ S such that X ≤_{T} O and O^{X} ≡_{hyp} O. Theorem 2 (folklore, ????). Let S be a nonempty Σ_{1}^{1} class, then we can find X ∈ S such that O^{X} ≡_{T} O. Comparing these two theorems, it is natural to ask whether the conclusion of Theorem 1 implies the conclusion of Theorem 2. In other words: Question. Do X ≤_{T} O and O^{X} ≡_{hyp} O together imply O^{X} ≡_{T} O? Or more generally: Question. Does O^{X} ≡_{hyp} O ⊕ X imply O^{X} ≡_{T} O ⊕ X? Of course the answer to these questions must be “No.” But does anybody have a counterexample??? Please help us ....

The Gandy Basis Theorem may be viewed as a hyperarithmetical analog of the celebrated Low Basis Theorem.

Low Basis Theorem (Jockusch & Soare, 1971). Let P ⊆ {0, 1}^{ℕ} be a nonempty Π_{1}^{0} class, then we can find X ∈ P such that H^{X} ≡_{T} H.

In the same paper Jockusch and Soare obtained the following generalization, which also includes the Friedberg Jump Theorem.

Theorem (Jockusch & Soare, 1971). Let P ⊆ {0, 1}^{ℕ} be a nonempty Π_{1}^{0} class with no recursive elements. Then for all Y we can find X ∈ P such that H^{X} ≡_{T} H ⊕ X ≡_{T} H ⊕ Y.

We now present the analogous generalization of the Gandy Basis Theorem, and of its “folklore” refinement.

Theorem (Jananthan & Simpson, 2018). Let S be a nonempty Σ_{1}^{1} class with no hyperarithmetical elements. Then for all Y we can find X ∈ S such that O^{X} ≡_{T} O ⊕ X ≡_{T} O ⊕ Y.

The special case where S is omitted is due to MacIntyre, 1977. MacIntyre’s proof used Cohen forcing, while our proof uses Harrington’s technique of forcing with Σ_{1}^{1} classes.

Part 2: Posner-Robinson and Pseudojump Inversion

Another extension of the Friedberg Jump Theorem is due to D. Posner and R. W. Robinson.

Posner-Robinson Theorem, 1981. For all Y and all non-recursive Z ≤_{T} H ⊕ Y, we can find X such that Z ⊕ X ≡_{T} H^{X} ≡_{T} H ⊕ X ≡_{T} H ⊕ Y.

Here is the hyperjump analog of the Posner-Robinson Theorem.

Theorem (Slaman, Woodin, ….) For all Y and all non-hyperarithmetical Z ≤_{T} O ⊕ Y, we can find X such that Z ⊕ X ≡_{T} O^{X} ≡_{T} O ⊕ X ≡_{T} O ⊕ Y.

This result is due to Slaman (unpublished) and Woodin (unpublished). Slaman emailed a sketch of his proof to Jananthan and me, and we have written it up and plan to publish it. The proof uses Kumabe-Slaman forcing over a countable non-well-founded model of ZFC.

Yet another extension of Friedberg’s Jump Inversion Theorem is the Pseudojump Inversion Theorem, due to Jockusch and Shore. A pseudojump operator is an operator of the form U : X ↦ U^{X} ⊕ X where X ranges over {0, 1}^{ℕ} and U^{X} ⊆ ℕ is uniformly Σ_{1}^{0,X}, i.e., uniformly recursively enumerable relative to X.

Pseudojump Inversion Theorem (Jockusch & Shore, 1983). For all Y and all pseudojump operators U, we can find X such that U^{X} ⊕ X ≡_{T} H ⊕ X ≡_{T} H ⊕ Y.

The proof of this theorem follows that of the original Jump Inversion Theorem, due to Friedberg 1957.

Let us define a pseudohyperjump operator to be the obvious hyperarithmetical analog of a pseudojump operator, i.e., an operator of the form V : X ↦ V^{X} ⊕ X where V^{X} ⊆ ℕ is uniformly Π_{1}^{1,X}. It seems natural to hope for a Pseudohyperjump Inversion Theorem where the conclusion would be that V^{X} ⊕ X ≡_{T} O ⊕ X ≡_{T} O ⊕ Y. But so far we have not been able to prove this.

In light of Jockusch-Soare 1971, one might try to choose the X’s (in both Posner-Robinson and Pseudojump Inversion) such that X ∈ P for a given nonempty Π_{1}^{0} class P ⊆ {0, 1}^{ℕ} with no recursive elements.

Jananthan and I have some partial results, as follows.

First, let P ⊆ {0, 1}^{ℕ} be a nonempty Π_{1}^{0} class which is Medvedev complete , e.g., P = {X | X is a completion of PA}. Then P has the following properties:

(1) For all Y and all non-recursive Z ≤_{T} H ⊕ Y, we can find an X ∈ P satisfying the conclusion of the Posner-Robinson Theorem, i.e., Z ⊕ X ≡_{T} H^{X} ≡_{T} H ⊕ X ≡_{T} H ⊕ Y.

(2) For all Y and all pseudojump operators U, we can find an X ∈ P satisfying the conclusion of the Pseudojump Inversion Theorem, i.e., U^{X} ⊕ X ≡_{T} H ⊕ X ≡_{T} H ⊕ Y.

On the other hand, there is a nonempty Π_{1}^{0} class P ⊆ {0, 1}^{ℕ} such that no X ∈ P is recursive but every finite sequence X_{1}, …, X_{n} ∈ P, n ≥ 1, is generalized low , i.e., H^{X_{1}⊕···⊕X_{n}} ≡_{T} H ⊕ X_{1} ⊕ ⋯ ⊕ X_{n}. Such a P cannot have property (1) or property (2).

An open problem is to characterize the Π_{1}^{0} classes P ⊆ {0, 1}^{ℕ} which have properties (1) and/or (2).

Another open problem is to characterize the Σ_{1}^{1} classes S which have the hyperarithmetical analogs of properties (1) and/or (2).

Thank you for your attention!

References.

Clifford Spector, Recursive well-orderings, Journal of Symbolic Logic, 20, 1955, 151–163. Richard M. Friedberg, A criterion for completeness of degrees of unsolvability, Journal of Symbolic Logic, 22, 1957, 159–160. Stephen C. Kleene, Quantification of number-theoretic functions, Compositio Mathematica, 14, 1959, 23–40. Robin O. Gandy, On a problem of Kleene’s, Bulletin of the American Mathematical Society, 66, 1960, 501–502. Carl G. Jockusch, Jr. and Robert I. Soare, Π_{1}^{0} classes and degrees of theories, Transactions of the American Mathematical Society, 173, 1972, 35–56. Leo Harrington, A powerless proof of a theorem of Silver, unpublished manuscript, 1976, 8 pages. John M. MacIntyre, Transfinite extensions of Friedberg’s completeness criterion, Journal of Symbolic Logic, 42, 1977, 1–10. David B. Posner and Robert W. Robinson, Degrees joining to 0′, Journal of Symbolic Logic, 46, 1981, 714–722. Carl G. Jockusch, Jr. and Richard A. Shore, Pseudo-jump operators I: the r.e. case, Transactions of the American Mathematical Society, 275, 1983, 599–609. Chi Tat Chong and Liang Yu, Recursion Theory: Computational Aspects of Definability, De Gruyter, 2015, XIII + 306 pages. Theodore A. Slaman, personal communication, December 2018. Hayden Jananthan and Stephen G. Simpson, in preparation, 2019.