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.
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.
The first definition of the hyperarithmetic sets uses the analytical hierarchy.
A set of natural numbers is classified at level
of this hierarchy if it is definable by a formula of second-order arithmetic with only existential set quantifiers and no other set quantifiers.
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 second, equivalent, definition shows that the hyperarithmetical sets can be defined using infinitely iterated Turing jumps.
A system of ordinal notations is required in order to define the hyperarithmetic hierarchy.
The following inductive definition is typical; it uses a pairing function
This may also be defined by taking effective joins at all levels instead of only notations for limit ordinals.
The set of all natural numbers that are ordinal notations is denoted
Ordinal notations are used to define iterated Turing jumps.
The sets of natural numbers used to define the hierarchy are
[2] Suppose that δ has notation e. These sets were first defined by Davis (1950) and Mostowski (1951).
depends on having a fixed notation for δ, and each infinite ordinal has many notations, a theorem of Clifford Spector shows that the Turing degree of
[2] 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
be the map from a member of Kleene's O to the ordinal it represents.
[4] A third characterization of the hyperarithmetical sets, due to Kleene, uses higher-type computable functionals.
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
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
, and so is not high in the hyperarithmetical hierarchy, although it is not arithmetically definable by Tarski's indefinability theorem.
The fundamental results of hyperarithmetic theory show that the three definitions above define the same collection of sets of natural numbers.
set of natural numbers is many-one reducible to it.
subset T of Baire space consisting only of characteristic functions of well orderings, there is an
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
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
Hyperarithmetical theory is the special case in which α is