A Open problems

A.1 Hyperarithmetic theory

We first list a question which has remained open for almost 40 years.

Question A.1.1 (Sacks [122]). Does every countable set of hyperdegrees have a minimal upper bound?

The next question concerns a version of the Posner–Robinson Theorem in the hyperarithmetic setting.

Question A.1.2. Let x ∉ HYP and let A ⊆ 2ω be and uncountable. Is there a y ∈ A such that x ⊕ y ≥h ?

A.2 Set-theoretic problems in recursion theory

The most important problem in this area is probably Martin’s Conjecture (6.6.9). We also have the following conjecture.

Conjecture A.2.1. Assume ZF + AD + V = L(ℝ). Then Martin’s Conjecture is true for order-preserving functions.

Question A.2.2 (Sacks [117]). Is every locally countable partial ordering 〈2ω, ≤P〉 embeddable into 〈 , ≤〉?

The following is motivated by Theorem 9.3.8.

Question A.2.3. Is it true, under ZF + DC, that the existence of a cofinal maximal chain of Turing degrees of order type ω1 implies the existence of a well-ordering of the reals?

More mysterious is perhaps the structure of antichains of Turing degrees.

Question A.2.4. Is there a -maximal antichain of Turing degrees?

While a number of examples in recursion theory independent of ZF were presented in Chapter 9, it is not known if there is a “natural” first order sentence φ in the language of partial ordering such that “〈D , ≤〉 φ” is independent of ZF.

Question A.2.5. Is there a natural first order sentence φ in the language of partial ordering such that “〈 , ≤〉 φ” is independent of ZF?

In [128], it is proved that if every set of reals is measurable, then ω1 is inaccessible in L.

Question A.2.6. Identify a set of Turing degrees with the set of reals whose degrees belong to . Is it true that if every set of Turing degrees is measurable, then ω1 is inaccessible in L?

A.3 Higher randomness theory

Question A.3.1. Is every -random real strongly -ML random?

By Corollary 14.3.4, Question A.3.1 can be reduced to the question of the existence of a strongly -ML random x ≥h .

It is not known if there is a nonhyperarithmetic real which is not -random cuppable, though we know that lowness for -randomness coincides with hyperarithmeticity.

In Chapter 14, the study of algorithmic randomness was generalized to the -level. It was also shown that one would not obtain a satisfactory theory by generalizing notions of randomness to the -level under the assumption V = L. Indeed under this assumption, any generalization of randomness notions to the analytical hierarchy beyond would result in a theory that is essentially trivial. The key reason is the existence of a well-ordering of 2ω within L. Hence one requires other set-theoretic axioms for a viable theory of algorithmic randomness at higher levels of the analytical hierarchy. There is a “regularity” phenomenon in descriptive set theory where all and -sets are considered analogs of r. e. sets under PD. We are interested in seeing whether this applies to the theory of higher randomness.

Question A.3.2. Can one extend higher randomness theory to the entire analytical hierarchy under certain large cardinal assumptions?

Kechris, Martin and Solovay [65] extended hyperarithmetic theory to Q-theory under PD. One may then introduce the theory of higher randomness in Q-theory. However, the modern development of descriptive set theory has embarked on a route somewhat different from that taken previously. Before the 1980s, most descriptive set-theoretic results were obtained using ingenious constructions, such as those associated with games and AD. Today, large cardinals and inner model theory feature prominently in the investigation of descriptive set theory. Even results that may appear to be “straightforward generalizations” of their low level counterparts were established this way. As recursion theory is grounded on the precept of effective computability, one is interested in having a ”nice L-like model” to perform recursion-theoretic constructions as those in L. In such a model, the study of higher randomness can be reasonably carried out.