Hyperarithmetical theory

(Redirected from Hyperarithmetic hierarchy)

In computability 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.[1]

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

edit

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. A set is classified at level   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   if it is both   and  . The hyperarithmetical sets are exactly the   sets.

Hyperarithmetical sets and iterated Turing jumps: the hyperarithmetical hierarchy

edit

The definition of hyperarithmetical sets as   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 is indexed by 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 smaller ordinals in an effective way. The following inductive definition is typical; it uses a pairing function  .

  • The number 0 is a notation for the ordinal 0.
  • If n is a notation for an ordinal λ then   is a notation for λ + 1;
  • Suppose that δ is a limit ordinal. A notation for δ is a number of the form  , where e is the index of a total computable function   such that for each n,   is a notation for an ordinal λn less than δ and δ is the sup of the set  .

This may also be defined by taking effective joins at all levels instead of only notations for limit ordinals.[2]

There are only countably many ordinal notations, since each notation is a natural number; thus there is a countable ordinal that is the supremum of all ordinals that have a notation. This ordinal is known as the Church–Kleene ordinal and is denoted  . Note that this ordinal is still countable, the symbol being only an analogy with the first uncountable ordinal,  . The set of all natural numbers that are ordinal notations is denoted   and called Kleene's  .

Ordinal notations are used to define iterated Turing jumps. The sets of natural numbers used to define the hierarchy are   for each  .   is sometimes also denoted  ,[3] or   for a notation   for  .[2] Suppose that δ has notation e. These sets were first defined by Davis (1950) and Mostowski (1951).[2] The set   is defined using e as follows.

  • If δ = 0 then   is the empty set.
  • If δ = λ + 1 then   is the Turing jump of  . The sets   and   are   and  , respectively.
  • If δ is a limit ordinal, let   be the sequence of ordinals less than δ given by the notation e. The set   is given by the rule  . This is the effective join of the sets  .

Although the construction of   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   depends only on δ, not on the particular notation used, and thus   is well defined up to Turing degree.[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  , if X is Turing reducible to  . 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 constructibility

edit

Let   denote the  th level of the constructible hierarchy, and let   be the map from a member of Kleene's O to the ordinal it represents. A subset of   is hyperarithmetical if and only if it is a member of  . A subset of   is definable by a   formula if and only if its image under   is  -definable on  , where   is from the Lévy hierarchy of formulae.[4]

Hyperarithmetical sets and recursion in higher types

edit

A third characterization of the hyperarithmetical sets, due to Kleene, uses higher-type computable functionals. The type-2 functional   is defined by the following rules:

  if there is an i such that f(i) > 0,
  if there is no i such that f(i) > 0.

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  .

Example: the truth set of arithmetic

edit

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  . The set T is Turing equivalent to the set  , and so is not high in the hyperarithmetical hierarchy, although it is not arithmetically definable by Tarski's indefinability theorem.

Fundamental results

edit

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   complete if it is at level   of the analytical hierarchy and every   set of natural numbers is many-one reducible to it. The definition of a   complete subset of Baire space ( ) is similar. Several sets associated with hyperarithmetic theory are   complete:

  • Kleene's  , the set of natural numbers that are notations for ordinal numbers
  • The set of natural numbers e such that the computable function   computes the characteristic function of a well ordering of the natural numbers. These are the indices of recursive ordinals.
  • The set of elements of Baire space that are the characteristic functions of a well ordering of the natural numbers (using an effective isomorphism  .

Results known as   bounding follow from these completeness results. For any   set S of ordinal notations, there is an   such that every element of S is a notation for an ordinal less than  . For any   subset T of Baire space consisting only of characteristic functions of well orderings, there is an   such that each ordinal represented in T is less than  .

Relativized hyperarithmeticity and hyperdegrees

edit

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  .

Generalizations

edit

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  .

Relation to other hierarchies

edit
Lightface Boldface
Σ0
0
= Π0
0
= Δ0
0
(sometimes the same as Δ0
1
)
Σ0
0
= Π0
0
= Δ0
0
(if defined)
Δ0
1
= recursive
Δ0
1
= clopen
Σ0
1
= recursively enumerable
Π0
1
= co-recursively enumerable
Σ0
1
= G = open
Π0
1
= F = closed
Δ0
2
Δ0
2
Σ0
2
Π0
2
Σ0
2
= Fσ
Π0
2
= Gδ
Δ0
3
Δ0
3
Σ0
3
Π0
3
Σ0
3
= Gδσ
Π0
3
= Fσδ
Σ0
= Π0
= Δ0
= Σ1
0
= Π1
0
= Δ1
0
= arithmetical
Σ0
= Π0
= Δ0
= Σ1
0
= Π1
0
= Δ1
0
= boldface arithmetical
Δ0
α
recursive)
Δ0
α
countable)
Σ0
α
Π0
α
Σ0
α
Π0
α
Σ0
ωCK
1
= Π0
ωCK
1
= Δ0
ωCK
1
= Δ1
1
= hyperarithmetical
Σ0
ω1
= Π0
ω1
= Δ0
ω1
= Δ1
1
= B = Borel
Σ1
1
= lightface analytic
Π1
1
= lightface coanalytic
Σ1
1
= A = analytic
Π1
1
= CA = coanalytic
Δ1
2
Δ1
2
Σ1
2
Π1
2
Σ1
2
= PCA
Π1
2
= CPCA
Δ1
3
Δ1
3
Σ1
3
Π1
3
Σ1
3
= PCPCA
Π1
3
= CPCPCA
Σ1
= Π1
= Δ1
= Σ2
0
= Π2
0
= Δ2
0
= analytical
Σ1
= Π1
= Δ1
= Σ2
0
= Π2
0
= Δ2
0
= P = projective


References

edit
  • H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
  • G. Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7
  • S. Simpson, 1999. Subsystems of Second Order Arithmetic, Springer-Verlag.
  • C. J. Ash, J. F. Knight, 2000. Computable Structures and the Hyperarithmetical Hierarchy, Elsevier. ISBN 0-444-50072-3

Citations

edit
  1. ^ Computability Theory of Hyperarithmetical Sets
  2. ^ a b c d S. G. Simpson, The Hierarchy Based on the Jump Operator, pp.268--269. The Kleene Symposium (North-Holland, 1980)
  3. ^ C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), ch. 5
  4. ^ D. Natingga, Embedding Theorem for the automorphism group of the α-enumeration degrees (p.27), PhD thesis, University of Leeds, 2019.
edit