The notions of hyperimmune degrees have applications in computability theory, and in the study of its interaction with algorithmic randomness. There are several ways to define these notions, and lets concentrate on the concept of domination. A function g is dominated by a function f if g(n) ≤ f(n) for almost all n. It is sometimes technically useful to work with the following closely related concept: A function g is majorized by a function f if g(n) ≤ f(n) ∀ n.
A degree a is hyperimmune if there is a function f ≤T a that is not dominated by any computable function (or, equivalently, not majorized by any computable function). Otherwise, a is hyperimmune-free.
While 0 is clearly hyperimmune-free, all other ∆02 degrees are hyperimmune.
If a < b ≤ a′, then b is hyperimmune. In particular, every nonzero degree below 0′, and hence every nonzero degree, is hyperimmune.
We carry out the proof for the case a = 0. The general result follows by a straightforward relativization.
Let B be a set such that φ T φ’. we need to find a function g ≤T B such that is not majorized by any computable function. Since B is ∆02, it has a computable approximation {Bs}s∈N. Define
g(n) = μs ≥ x (Bs ↾ n = B ↾ n)
g(n) is not the stage s by which the approximation to B ↾ n has stabilized, but rather the first stage s at which Bs ↾ n is correct. Clearly, g ≤T B. Hypothesizing that no computable function majorizes g. Suppose h is computable and majorizes g. Hypothesizing on the addendum, B is computable as well. To compute B ↾ m, search for an n > m such that Bt ↾ m = Bn ↾ m ∀ t ∈ [n, h(n)]. Such an n must exist because there is a stage at which the approximation to B ↾ m stabilizes. By the definition of g and the choice of h, we have g(n) ∈ [n, h(n)], so B ↾ m = Bg(n) ↾ m = Bn ↾ m. Thus B is computable, which is a contradiction.
On the other hand, there do exist nonzero hyperimmune-free degrees.
We define a noncomputable set A of hyperimmune-free degree, using a technique known as forcing with computable perfect trees. A function tree is a function T: 2<ω → 2<ω such T(σ0) and T(σ1) are incompatible extensions of T(σ). For a tree T, let [T] be a collection of all X for which there is an infinite sequence β such that T(σ) ≺ X ∀ σ ≺ β. Building a sequence of {Ti}i∈N of computable trees such that [T0] ⊇ [T1] ⊇ [T2] ⊇ [T3]…since each [Ti] is closed, ∩n[Tn] ≠ 0. We will take A to be any element of this intersection.
The name “hyperimmune degree” comes from the notion of a hyperimmune set, which is a strong array that is a computable collection of disjoint finite sets {Fi}i∈N (which means not only that the Fi are uniformly computable, but that the function i ↦ max Fi is computable). A set A is hyperimmune if for all strong arrays {Fi}i∈N, there is an i such that Fi ⊂ Â. A set is hypersimple if its complement is hyperimmune.
AltExploit 