Relativized Hyperarithmeticity and Hyperdegrees
The definition of can be relativized to a set X of natural numbers: in the definition of an ordinal notation, the clause for limit ordinals is changed so that the computable enumeration of a sequence of ordinal notations is allowed to use X as an oracle. The set of numbers that are ordinal notations relative to X is denoted . The supremum of ordinals represented in is denoted ; this is a countable ordinal no smaller than .
The definition of can also be relativized to an arbitrary set of natural numbers. The only change in the definition is that is defined to be X rather than the empty set, so that is the Turing jump of X, and so on. Rather than terminating at the hierarchy relative to X runs through all ordinals less than .
The relativized hyperarithmetical hierarchy is used to define hyperarithmetical reducibility. Given sets X and Y, we say if and only if there is a such that X is Turing reducible to . If and then the notation is used to indicate X and Y are hyperarithmetically equivalent. This is a coarser equivalence relation than Turing equivalence; for example, every set of natural numbers is hyperarithmetically equivalent to its Turing jump but not Turing equivalent to its Turing jump. The equivalence classes of hyperarithmetical equivalence are known as hyperdegrees.
The function that takes a set X to is known as the hyperjump by analogy with the Turing jump. Many properties of the hyperjump and hyperdegrees have been established. In particular, it is known that Post's problem for hyperdegrees has a positive answer: for every set X of natural numbers there is a set Y of natural numbers such that .
Read more about this topic: Hyperarithmetical Theory