Hyperarithmetical theory

In recursion theory, hyperarithmetic theory is a generalization of Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theory. It is an important tool in effective descriptive set theory.
The central focus of hyperarithmetic theory is the sets of natural numbers known as hyperarithmetic sets. There are three equivalent ways of defining this class of sets; the study of the relationships between these different definitions is one motivation for the study of hyperarithmetical theory.
Hyperarithmetical sets and definability.
The first definition of the hyperarithmetic sets uses the analytical hierarchy. 
A set of natural numbers is classified at level formula_1 of this hierarchy if it is definable by a formula of second-order arithmetic with only existential set quantifiers and no other set quantifiers. A set is classified at level formula_2 of the analytical hierarchy if it is definable by a formula of second-order arithmetic with only universal set quantifiers and no other set quantifiers. A set is formula_3 if it is both formula_1 and formula_2. The hyperarithmetical sets are exactly the formula_3 sets.
Hyperarithmetical sets and iterated Turing jumps: the hyperarithmetical hierarchy.
The definition of hyperarithmetical sets as formula_3 does not directly depend on computability results. A second, equivalent, definition shows that the hyperarithmetical sets can be defined using infinitely iterated Turing jumps. This second definition also shows that the hyperarithmetical sets can be classified into a hierarchy extending the arithmetical hierarchy; the hyperarithmetical sets are exactly the sets that are assigned a rank in this hierarchy.
Each level of the hyperarithmetical hierarchy corresponds to a countable ordinal number (ordinal), but not all countable ordinals correspond to a level of the hierarchy. The ordinals used by the hierarchy are those with an ordinal notation, which is a concrete, effective description of the ordinal.
An ordinal notation is an effective description of a countable ordinal by a natural number. A system of ordinal notations is required in order to define the hyperarithmetic hierarchy. The fundamental property an ordinal notation must have is that it describes the ordinal in terms of small ordinals in an effective way. The following inductive definition is typical; it uses a pairing function formula_8.
There are only countably many ordinal notations, since each notation is a natural number; thus there is a countable ordinal which is the supremum of all ordinals that have a notation. This ordinal is known as the Church-Kleene ordinal and is denoted formula_14. Note that this ordinal is still countable, the symbol being only an analogy with the first uncountable ordinal, formula_15. The set of all natural numbers that are ordinal notations is denoted formula_16 and called "Kleene's formula_16".
Ordinal notations are used to define iterated Turing jumps. These are sets of natural numbers denoted formula_18 for each formula_19. Suppose that δ has notation "e". The set formula_18 is defined using "e" as follows.
Although the construction of formula_18 depends on having a fixed notation for δ, and each infinite ordinal has many notations, a theorem of Spector shows that the Turing degree of formula_18 depends only on δ, not on the particular notation used, and thus formula_18 is well defined up to Turing degree.
The hyperarithmetical hierarchy is defined from these iterated Turing jumps. A set "X" of natural numbers is classified at level δ of the hyperarithmetical hierarchy, for formula_19, if "X" is Turing reducible to formula_18. There will always be a least such δ if there is any; it is this least δ that measures the level of uncomputability of "X".
Hyperarithmetical sets and recursion in higher types.
A third characterization of the hyperarithmetical sets, due to Kleene, uses higher-type computable functionals. The type-2 functional formula_37 is defined by the following rules:
Using a precise definition of computability relative to a type-2 functional, Kleene showed that a set of natural numbers is hyperarithmetical if and only if it is computable relative to formula_40.
Example: the truth set of arithmetic.
Every arithmetical set is hyperarithmetical, but there are many other hyperarithmetical sets. One example of a hyperarithmetical, nonarithmetical set is the set "T" of Gödel numbers of formulas of Peano arithmetic that are true in the standard natural numbers formula_41. The set "T" is Turing equivalent to the set formula_42, and so is not high in the hyperarithmetical hierarchy, although it is not arithmetically definable by Tarski's indefinability theorem.
Fundamental results.
The fundamental results of hyperarithmetic theory show that the three definitions above define the same collection of sets of natural numbers. These equivalences are due to Kleene.
Completeness results are also fundamental to the theory. A set of natural numbers is formula_2 complete if it is at level formula_2 of the analytical hierarchy and every formula_2 set of natural numbers is many-one reducible to it. The definition of a formula_2 complete subset of Baire space (formula_47) is similar. Several sets associated with hyperarithmetic theory are formula_2 complete:
Results known as formula_1 bounding follow from these completeness results. For any formula_1 set "S" of ordinal notations, there is an formula_54 such that every element of "S" is a notation for an ordinal less than formula_55. For any subset "T" of Baire space consisting only of characteristic functions of well orderings, there is an formula_54 such that each ordinal represented in "T" is less than formula_55.
Relativized hyperarithmeticity and hyperdegrees.
The definition of formula_16 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 formula_59. The supremum of ordinals represented in formula_59 is denoted formula_61; this is a countable ordinal no smaller than formula_14.
The definition of formula_18 can also be relativized to an arbitrary set formula_64 of natural numbers. The only change in the definition is that formula_65 is defined to be "X" rather than the empty set, so that formula_66 is the Turing jump of "X", and so on. Rather than terminating at formula_14 the hierarchy relative to "X" runs through all ordinals less than formula_61.
The relativized hyperarithmetical hierarchy is used to define hyperarithmetical reducibility. Given sets "X" and "Y", we say formula_69 if and only if there is a formula_70 such that "X" is Turing reducible to formula_71. If formula_69 and formula_73 then the notation formula_74 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 formula_59 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 formula_76.
Generalizations.
Hyperarithmetical theory is generalized by α-recursion theory, which is the study of definable subsets of admissible ordinals. Hyperarithmetical theory is the special case in which α is formula_14.