Recursion Theory

10 Rigidity and biinterpretability of hyperdegrees

Let 〈h, ≤〉 denote the structure of hyperdegrees under the partial ordering ≤ for hyperarithmetic reducibility. As for the Turing degrees 〈, ≤〉, the hyperdegrees form an upper semilattice under the join operator ∪, where if the hyperdegrees of x and y are respectively a and b, then x ⊕ y has hyperdegree a ∪ b. Note that ∪ may be defined in terms of ≤. A map of or h into itself is an automorphism if ...