Hyperarithmetical theory


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.

Hyperarithmetical sets

The central focus of hyperarithmetic theory are certain 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 Sigma^1_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 Pi^1_1 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 Delta^1_1 if it is both Sigma^1_1 and Pi^1_1. The hyperarithmetical sets are exactly the Delta^1_1 sets.

Hyperarithmetical sets and iterated Turing jumps: the hyperarithmetical hierarchy

The definition of hyperarithmetical sets as Delta^1_1 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 langle cdot , cdot angle.
* The number 0 is a notation for the ordinal 0.
* If "n" is a notation for an ordinal λ then langle 1, n angle is a notation for λ + 1;
* Suppose that δ is a limit ordinal. A notation for δ is a number of the form langle 2, e angle, where "e" is the index of a total computable function phi_e such that for each "n", phi_e(n) is a notation for an ordinal λn less than δ and δ is the sup of the set { lambda_n mid n in mathbb{N}}.

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 omega^{CK}_1. The set of all natural numbers that are ordinal notations is denoted mathcal{O} and called "Kleene's mathcal{O}".

Ordinal notations are used to define iterated Turing jumps. These are sets of natural numbers denoted 0^{(delta)} for each delta < omega^{CK}_1. Suppose that &delta; has notation "e". The set 0^{(delta)} is defined using "e" as follows.
* If &delta; = 0 then 0^{(delta)}= 0 is the empty set.
* If &delta; = &lambda; + 1 then 0^{(delta)} is the Turing jump of 0^{(lambda)}. The notations 0' and 0" are commonly used for 0^{(1)} and 0^{(2)}, respectively.
* If &delta; is a limit ordinal, let langle lambda_n mid n in mathbb{N} angle be the sequence of ordinals less than &delta; given by the notation "e". The set 0^{(delta)} is given by the rule 0^{(delta)} = { langle n,i angle mid i in 0^{(lambda_n)}}. This is the effective join of the sets 0^{(lambda_n)}.Although the construction of 0^{(delta)} depends on having a fixed notation for &delta;, and each infinite ordinal has many notations, a theorem of Spector shows that the Turing degree of 0^{(delta)} depends only on &delta;, not on the particular notation used, and thus 0^{(delta)} 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 &delta; of the hyperarithmetical hierarchy, for delta < omega^{CK}_1, if "X" is Turing reducible to 0^{(delta)}. There will always be a least such &delta; if there is any; it is this least &delta; 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 {}^2Ecolon mathbb{N}^{mathbb{N o mathbb{N} is defined by the following rules::{}^2E(f) = 1 quad if there is an "i" such that "f"("i") > 0,:{}^2E(f) = 0 quad 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 {}^2E.

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 Godel numbers of formulas of Peano arithmetic that are true in the standard natural numbers mathbb{N}. The set "T" is Turing equivalent to the set 0^{(omega)}, 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 Pi^1_1 complete if it is at level Pi^1_1 of the analytical hierarchy and every Pi^1_1 set of natural numbers is many-one reducible to it. The definition of a Pi^1_1 complete subset of Baire space (mathbb{N}^mathbb{N}) is similar. Several sets associated with hyperarithmetic theory are Pi^1_1 complete:
* Kleene's mathcal{O}, the set of natural numbers that are notations for ordinal numbers
* The set of natural numbers "e" such that the computable function phi_e(x,y) 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 mathbb{N}^mathbb{N} cong mathbb{N}^{mathbb{N} imesmathbb{N).

Results known as Sigma^1_1 bounding follow from these completeness results. For any Sigma^1_1 set "S" of ordinal notations, there is an alpha < omega^{CK}_1 such that every element of "S" is a notation for an ordinal less than alpha. For any subset "T" of Baire space consisting only of characteristic functions of well orderings, there is an alpha < omega^{CK}_1 such that each ordinal represented in "T" is less than alpha.

Relativized hyperarithmeticity and hyperdegrees

The definition of mathcal{O} 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 mathcal{O}^X. The supremum of ordinals represented in mathcal{O}^X is denoted omega^{X}_1; this is a countable ordinal no smaller than omega^{CK}_1.

The definition of 0^{(delta)} can also be relativized to an arbitrary set X of natural numbers. The only change in the definition is that X^{(0)} is defined to be "X" rather than the empty set, so that X^{(1)} = X' is the Turing jump of "X", and so on. Rather than terminating at omega^{CK}_1 the hierarchy relative to "X" runs through all ordinals less than omega^{X}_1.

The relativized hyperarithmetical hierarchy is used to define hyperarithmetical reducibility. Given sets "X" and "Y", we say X leq_{HYP} Y if and only if there is a delta < omega^Y_1 such that "X" is Turing reducible to Y^{(delta)}. If X leq_{HYP} Y and Y leq_{HYP} X then the notation X equiv_{HYP} Y is used to indicate "X" and "Y" are hyperarithmetically equivalent. This is a coarser equivalence relation that 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 mathcal{O}^X 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 X <_{HYP} Y <_{HYP} mathcal{O}^X.

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 omega^{CK}_1.

References

* 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.

External links

* [http://math.uic.edu/~marker/math512/dst.pdf Descriptive set theory] . Notes by David Marker, University of Illinois at Chicago. 2002.
* [http://www.math.uio.no/~dnormann/LogikkII.pdf Mathematical Logic II] . Notes by Dag Normann, The University of Oslo. 2005.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Descriptive set theory — In mathematical logic, descriptive set theory is the study of certain classes of well behaved subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to other… …   Wikipedia

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia

  • Reduction (recursion theory) — In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively… …   Wikipedia

  • Analytical hierarchy — In mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them. The analytical hierarchy of… …   Wikipedia

  • Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… …   Wikipedia

  • Computable function — Total recursive function redirects here. For other uses of the term recursive function , see Recursive function (disambiguation). Computable functions are the basic objects of study in computability theory. Computable functions are the formalized …   Wikipedia

  • Ordinal analysis — In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength. The field was formed when Gerhard Gentzen in 1934 used cut elimination to prove, in modern terms, that… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia