Higher Recursion Theory and Set Theory

The following sections are included:

• Contents
• Foreword
• Preface

Investigations of elementary theories for Rogers semilattices constitute one of the core directions in the theory of numberings. In recent years, the studies of significative differences in isomorphism types of these semilattices, witnessed by their algebraic and first-order properties, flourished (especially, in the area of numberings belonging to the levels of various recursion-theoretic hierarchies). Nevertheless, there are not many known results on the algorithmic complexity of elementary theories for Rogers semilattices.

In this chapter, we investigate initial segments of Rogers semilattices in the analytical hierarchy, and we study decidability for fragments of the corresponding first-order theories. Let n be a non-zero natural number. For an arbitrary non-trivial Rogers semilattice R induced by a ${\text{Σ}}_n^1$-computable family of sets, we obtain the following results. The ∏₄-fragment of the theory Th(R) in the signature of partial orders is hereditarily undecidable. The Σ₁-fragment of Th(R) in the signature of upper semilattices is decidable. Similar results hold for families in the arithmetical hierarchy, starting with the ${\text{Σ}}_4^0$ level.

We investigate what collections of c.e. Turing degrees can be realised as the collection of elements of a separating ${\text{Π}}_1^0$ class of c.e. degree. We show that for every c.e. degree c, the collection {c, 0′} can be thus realized. We also rule out several attempts at constructing separating classes realizing a unique c.e. degree. For example, we show that there is no super-maximal pair: disjoint c.e. sets A and B whose separating class is infinite, but every separator of c.e. degree is a finite variant of either A or $\overline{B}$.

σ-complete uniform ultrafilters where extensively studied in early seventies. Many nice results were obtained, specially by J. Ketonen (see [10]).

Recently, G. Goldberg returned to the subject and proved a remarkable result that under The Ultrapower Axiom the first strongly compact cardinal is a supercompact.

The purpose of this chapter is to provide some concrete examples of σ-complete uniform ultrafilters.

We extend results found by Greenberg, Turetsky and Westrick in [7] and investigate effective properties of bases of uncountable free abelian groups. Assuming V = L, we show that if κ is a regular uncountable cardinal and X is a ${\text{Δ}}_1^1\left(L_{\kappa }\right)$ subset of κ, then there is a κ-computable free abelian group whose bases cannot be effectively computed by X. Unlike in [7], we give a direct construction.

The Posner-Robinson Theorem states that for any reals Z and A such that Z ⊕ 0^′ ≤_T A and 0 <_T Z, there exists B such that A ≡_T B^′ ≡_T B ⊕ Z ≡_T B ⊕ 0^′. Consequently, any nonzero Turing degree deg_T (Z) is a Turing jump relative to some B. Here we prove the hyperarithmetical analog, based on an unpublished proof of Slaman, namely that for any reals Z and A such that Z ⊕ 𝒪 ≤_T A and 0 <_HYP Z, there exists B such that A ≡_T 𝒪^B ≡_T B ⊕ Z ≡_T B ⊕ 𝒪. As an analogous consequence, any nonhyperarithmetical Turing degree deg_T (Z) is a hyperjump relative to some B.

The Friedberg Jump Theorem says that for every real A there is a real B such that A ⊕ 0′ ≡_T B′ ≡_T B ⊕ 0′. A well-known refinement of this says that, given a special ${\text{Π}}_1^0$ class Q, we can choose B to be an element of Q. In this chapter, we consider analogous refinements of two other well-known theorems: the Posner-Robinson Theorem — for all reals A and Z such that 0 <_T Z, there is a real B such that A ⊕ Z ⊕ 0′ ≡_T B′ ≡_T B ⊕ Z ≡_T B ⊕ 0′ — and the Pseudojump Inversion Theorem — for all e ∈ ℕ and all reals A, there is a real B such that A ⊕ 0′ ≡_T B ⊕ J_e (B) ≡_T B ⊕ 0′. We show that in these theorems, B can be found in some special ${\Pi }_1^0$ classes but not in others.

A function F : 2^ω → 2^ω is an E₀-isomorphism if for all x, y ∈ 2^ω, we have xE₀y ↔ f (x)E₀f (y), where xE₀y ↔ (∃a)(∀n ≥ b)x(n) = y(n). If such witnesses a for xE₀y and for f (x)E₀f (y) depend on each other but not on x, y, then F is called bi-uniform. It is shown that a homeomorphism of Cantor space which is a bi-uniform E₀-isomorphism can induce only the trivial automorphism of the truth-table degrees.

This survey is based on notes taken by Luke Serafin, on lectures given by the author on June 4th, 6th, 11th and 13th of 2019, at the Workshop on Set Theory, Recursion Theory and their Interaction, held at the Institute for Mathematical Sciences at the University of Singapore. It covers an introductory portion of the classical theory of Woodin’s AD⁺. There is significant overlap between the material presented here and in the paper [9]. The lectures were based on parts of the author’s book [13].

We show that for any x, 𝒰_h(x) = {y | y ≥_h x} is Borel if and only if x ∈ L. Moreover, the Borel rank of 𝒰_h(x) when it exists is less than (ω₁)^L. We also show using Steel forcing with tagged trees that Borel ranks of these sets range unboundedly below (ω₁)^L.

We develop a new metatheorem for 0^(η -priority constructions for transfinite ordinals η. Our metatheorem simplifies previous metatheorems by Ash, Ash–Knight and the author. A drawback of this simplification is that its applications are more limited: It can only be used when the object being built is an ω-presentation of a structure. However, in practical terms, this is not a huge limitation and the majority of proofs in the literature that use the Ash–Knight metatheorem can be done using our metatheorem.

It is well-known that AD implies that there is no ω₁-sequence of distinct reals. A slightly stronger theorem says that AD implies there is no ω₁ sequence of distinct countable sets of reals. It is known that under I₀(λ) the λ-version of the former statement holds in L(V_λ+1) (see Shi-Trang [1]). In this chapter, we prove the I₀ analogue of the latter: Assume ZFC + I₀(λ), in L(V_λ+1) there is no λ⁺-sequence of distinct subsets of 𝒫 (λ) of size ≤λ. This answers a question of John Steel raised at the Arctic Set Theory Workshop 2019. We also analyze two other proofs of the AD theorem (for countable sets of reals), and discuss the possibility of as well as the obstacles in generalizing these arguments to I₀ context.

Type omitting arguments provide conditions under which one can find a model ℳ of a given theory T which does not have elements ā which satisfy all the formulas $\phi (\overline{x})$ in a given type Γ, i.e. a specified collection of formulas. Such theorems are an important feature of first order logic and have been proven for a few more general logics. Harrington, Shore and Slaman [2017] proved a theorem about ${\text{Σ}}_1^1$ sets which implied such results for omega logic (a classical result) and computable infinitary logic as well as other classical theorems of hyperarithmetic theory. In this chapter, we show that the same theorem implies analogous type omitting theorems for many other logics including a wide range of fragments of second order logic both classical and modal. That is, for the modal logics we are also allowed to use any one of these fragments of second order logic at each world.

Building on the results of [19] and [18], we obtain optimal Suslin representations for mouse pairs. This leads us to an analysis of HOD^M, for any model M of AD_ℝ in which there are Wadge-cofinally many mouse pairs. We show also that if there is a least branch hod pair with a Woodin limit of Woodin cardinals, then there is a model of AD⁺ in which not every set of reals is ordinal definable from a countable sequence of ordinals.

Proof mining is the branch of proof theory concerned with examining actual proofs, as they appear in the mathematical literature, and extracting additional from them. In the most common case, we begin with a suitable non-effective proof and convert this proof, by purely syntactic means, into an effective one. In this chapter, we illustrate the main tool, the functional interpretation, by working through a concrete, fairly simple example before describing the underlying proof-theoretic ideas.

We consider the reverse math strength of the statement CD-M: “Every completely determined Borel set is measurable.” Over WWKL, we obtain the following results analogous to the previously studied category case:

• (1) CD-M lies strictly between ATR₀ and L_{ω1, ω}-CA.
• (2) Whenever M ⊆ 2^ω is the second-order part of an ω-model of CD-M, then for every Z ∈ M, there is a R ∈ M such that R is ${\text{Δ}}_1^1$-random relative to Z.

On the other hand, without WWKL, all sets have measure zero (as measured according to CD-M), and it follows vacuously that ¬WWKL implies CD-M over RCA₀.