On the theory of the Delta 0,2 degrees.

摘要

From a recursion-theoretic point of view, $D02$ sets are the most concrete non-recursive sets, with the r.e. sets holding a distinguished place as the most concrete of all. By the work of [Epstein, Haas and Kramer, 1981; Ershov,1968a; Ershov, 1968b; Ershov,1970] and others, the $D02$ degrees can, roughly speaking, be stratified into the Ershov difference hierarchy, with the r.e. degrees at the bottom just above the recursive degree. Much of this thesis explores questions about the relationships and interactions between arbitrary $D02$ degrees and $D02$ degrees that sit in some initial segment of this hierarchy:; We begin by looking at how natural structures composed of r.e. degrees sit inside of natural structures composed of general $D02$ degrees. First we show that if l is a low₂, r.e. degree, then the partial order of r.e. degrees below l is a Σ₁ elementary substructure of the partial order of $D02$ degrees below l, where both structures are ordered by ≤_T.; Next, we consider the existence of $D02$ reals that are simultaneously 1-generic or 1-random over many $D02$ degrees. We show that for any r.e. set V and any collection of sets uniformly recursive in V, that V bounds a real that is 1-generic over every member of the collection that is strictly below V.; Definition 1. Let x be a Turing degree and let $W$ and $V$ be sets of Turing degrees such that for all $w\in W$ and all $v\in V$, x ∨ v ≥_T w → v ≥_T w. Then we say that x is join independent for $V$ over $W$. We extend this definition to the case when X is a real and $W$ and $V$ are sets of reals in the obvious way.; An easy corollary of our construction of 1-generics is that if R is a univalent, recursively related system of notations for α, then there is a $D02$ degree that is join independent for the R, α-r.e. degrees over the n-REA degrees.; Finally, we prove that for all reals A and B, A′ ≤_1T B′ if and only if A ≤ _T B, where X ≤_{n T} Y means that X is computable from Y via an algorithm that makes at most n oracle queries to Y on each input. This gives a partial answer to the following question, originally asked by Gasarch [1998], by showing that if X $\ngeqq$_T 0′, then X ′ $\ngeqq$_1T 0″. (Abstract shortened by UMI.)