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 formulas

The notation $Sigma^1_0 = Pi^1_0 = Delta^1_0$ indicates the class of formulas in the language of second-order arithmetic with no set quantifiers. This language does not contain set parameters. The Greek letters here are lightface symbols, which indicate this choice of language. Each corresponding boldface symbol denotes the corresponding class of formulas in the extended language with a parameter for each real; see projective hierarchy for details.

A formula in the language of second-order arithmetic is defined to be $Sigma^1_{n+1}$ if it is logically equivalent to a formula of the form $exists X_1cdots exists X_k psi$ where $psi$ is $Pi^1_{n}$ . A formula is defined to be $Pi^1_{n+1}$ if it is logically equivalent to a formula of the form $forall X_1cdots forall X_k psi$ where $psi$ is $Sigma^1_{n}$ . This inductive definition defines the classes $Sigma^1_n$ and $Pi^1_n$ for every natural number $n$ .

Because every formula has a prenex normal form, every formula in the language of second-order arithmetic is $Sigma^1_n$ or $Pi^1_n$ for some $n$ . Because meaningless quantifiers can be added to any formula, once a formula is given the classification $Sigma^1_n$ or $Pi^1_n$ for some $n$ it will be given the classifications $Sigma^1_m$ and $Pi^1_m$ for all $m$ greater than $n$ .

Note that it rarely makes sense to speak of a $Delta^1_n$ "formula"; the first quantifier of a formula is either existential or universal.

The analytical hierarchy of sets of natural numbers

A set of natural numbers is assigned the classification $Sigma^1_n$ if it is definable by a $Sigma^1_n$ formula. The set is assigned the classification $Pi^1_n$ if it is definable by a $Pi^1_n$ formula. If the set is both $Sigma^1_n$ and $Pi^1_n$ then it is given the additional classification $Delta^1_n$ .

The $Delta^1_1$ sets are called hyperarithmetical. An alternate classification of these sets by way of iterated computable functionals is provided by hyperarithmetical theory.

The analytical hierarchy on subsets of Cantor and Baire space

The analytical hierarchy can be defined on any effective Polish space; the definition is particularly simple for Cantor and Baire space because they fit with the language of ordinary second-order arithmetic. Cantor space is the set of all infinite sequences of 0s and 1s; Baire space is the set of all infinite sequences of natural numbers. These are both Polish spaces.

The ordinary axiomatization of second-order arithmetic uses a set-based language in which the set quantifiers can naturally be viewed as quantifying over Cantor space. A subset of Cantor space is assigned the classification $Sigma^1_n$ if it is definable by a $Sigma^1_n$ formula. The set is assigned the classification $Pi^1_n$ if it is definable by a $Pi^1_n$ formula. If the set is both $Sigma^1_n$ and $Pi^1_n$ then it is given the additional classification $Delta^1_n$ .

A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from $omega$ to $omega$ to the characteristic function of its graph. A subset of Baire space is given the classification $Sigma^1_n$ , $Pi^1_n$ , or $Delta^1_n$ if and only if the corresponding subset of Cantor space has the same classification. An equivalent definition of the analytical hierarchy on Baire space is given by defining the analytical hierarchy of formulas using a functional version of second-order arithmetic; then the analytical hierarchy on subsets of Cantor space can be defined from the hierarchy on Baire space. This alternate definition gives exactly the same classifications as the first definition.

Because Cantor space is homeomorphic to any finite Cartesian power of itself, and Baire space is homeomorphic to any finite Cartesian power of itself, the analytical hierarchy applies equally well to finite Cartesian power of one of these spaces.A similar extension is possible for countable powers and to products of powers of Cantor space and powers of Baire space.

Extensions

As is the case with the arithmetical hierarchy, a relativized version of the analytical hierarchy can be defined. The language is extended to add a constant set symbol "A". A formula in the extended language is inductively defined to be $Sigma^{1,A}_n$ or $Pi^{1,A}_n$ using the same inductive definition as above. Given a set $Y$ , a set is defined to be $Sigma^{1,Y}_n$ if it is definable by a $Sigma^{1,A}_n$ formula in which the symbol $A$ is interpreted as $Y$ ; similar definitions for $Pi^{1,Y}_n$ and $Delta^{1,Y}_n$ apply. The sets that are $Sigma^{1,Y}_n$ or $Pi^{1,Y}_n$ , for any parameter "Y", are classified in the projective hierarchy.

Examples

* The set of all natural numbers which are indices of computable ordinals is a $Pi^1_1$ set which is not $Sigma^1_1$ .

* The set of elements of Cantor space which are the characteristic functions of well orderings of $omega$ is a $Pi^1_1$ set which is not $Sigma^1_1$ . In fact, this set is not $Sigma^{1,Y}_1$ for any element $Y$ of Baire space.

* If the axiom of constructibility holds then there is a subset of the product of the Baire space with itself which is $Delta^1_2$ and is the graph of a well ordering of Baire space. If the axiom holds then there is also a $Delta^1_2$ well ordering of Cantor space.

Properties

For each $n$ we have the following strict containments:

: $Pi^1_n subset Sigma^1_{n+1}$ ,: $Pi^1_n subset Pi^1_{n+1}$ ,: $Sigma^1_n subset Pi^1_{n+1}$ ,: $Sigma^1_n subset Sigma^1_{n+1}$ .

A set that is in $Sigma^1_n$ for some "n" is said to be analytical. Care is required to distinguish this usage from the term analytic set which has a different meaning.

External links

* [http://planetmath.org/encyclopedia/AnalyticHierarchy.html PlanetMath page]

References

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

Hierarchy (mathematics) — In mathematics, a hierarchy is a preorder, i.e. an ordered set. The term is used to stress a natural hierarchical relation among the elements. In particular, it is the preferred terminology for posets whose elements are classes of objects of… … Wikipedia
Hierarchy — A hierarchy (Greek: hierarchia (ἱεραρχία), from hierarches, leader of sacred rites ) is an arrangement of items (objects, names, values, categories, etc.) in which the items are represented as being above, below, or at the same level as one… … Wikipedia
Arithmetical hierarchy — In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The… … Wikipedia
Analytic Hierarchy Process — The Analytic Hierarchy Process (AHP) is a structured technique for helping people deal with complex decisions. Rather than prescribing a correct decision, the AHP helps people to determine one. Based on mathematics and human psychology, it was… … Wikipedia
Projective hierarchy — In the mathematical field of descriptive set theory, a subset A of a Polish space X is projective if it is oldsymbol{Sigma}^1 n for some positive integer n. Here A is * oldsymbol{Sigma}^1 1 if A is analytic * oldsymbol{Pi}^1 n if the… … Wikipedia
Borel hierarchy — In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number… … Wikipedia
Wadge hierarchy — In descriptive set theory, Wadge degrees are levels of complexity for sets of reals and more comprehensively, subsets of any given topological space. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge… … Wikipedia
Proceso Analítico Jerárquico — Saltar a navegación, búsqueda Una jerarquía AHP, con prioridades finales. El objetivo de la decisión es seleccionar el líder que mejor se ajusta de un grupo de tres candidatos. Los factores que se deben considerar son edad, experiencia, educación … Wikipedia Español
List of philosophy topics (A-C) — 110th century philosophy 11th century philosophy 12th century philosophy 13th century philosophy 14th century philosophy 15th century philosophy 16th century philosophy 17th century philosophy 18th century philosophy 19th century philosophy220th… … Wikipedia
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… … Wikipedia

Academic Dictionaries and Encyclopedias

Analytical hierarchy

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Analytical hierarchy

Look at other dictionaries:

Share the article and excerpts

Direct link