From TheBestLinks.com
In mathematical logic and descriptive set theory, the analytical hierarchy is a second-order analogue of the arithmetical hierarchy.
The standard notation <math>\Sigma^1_0 = \Pi^1_0 = \Delta^1_0<math>
indicates on the one hand the class of formulas that can be expressed as formulas of arbitrary finite length of alternating universal and existential quantifiers for individuals over predicates linked by sentential connectives; and on the other the class of Borel sets.
A <math>\Sigma^1_1<math> formula is a formula of the form <math>\exists X \phi<math>,
where X is now a predicate and <math>\phi \in \Sigma^1_0<math>,
while a <math>\Sigma^1_1<math> set is a set of the form
- <math>\{x : (\exists y \in S)\ R(x,y) \}<math>,
where S is Borel and R is a relation.
A <math>\Sigma^1_1<math> set is said to be analytic, and can thus be seen as a projection of a Borel set.
A <math>\Pi^1_1<math> formula is the negation of a <math>\Sigma^1_1<math> formula,
while a <math>\Pi^1_1<math> set is the complement of a Borel set.
A <math>\Pi^1_1<math> set is said to be co-analytic.
Generalizing this construction, a <math>\Sigma^1_{n+1}<math> formula is a formula of the form <math>\exists X \phi<math>
where X is a predicate and <math>\phi \in \Sigma^1_n;<math>
and a <math>\Sigma^1_{n+1}<math> set is a set of the form
- <math>\{x : (\exists y \in S)\ R(x,y) \},<math>
where S is <math>\Sigma^1_n<math>.
A <math>\Pi^1_n<math> formula is the negation of a <math>\Sigma^1_n<math> formula,
and a <math>\Pi^1_n<math> set is the complement of a <math>\Sigma^1_n<math> set.
A formula or set is called <math>\Delta^1_n<math> if it is both <math>\Sigma^1_n<math> and <math>\Pi^1_n<math>.
We have the strict containments
- <math>\Pi^1_n \subset \Sigma^1_{n+1};<math>
- <math>\Pi^1_n \subset \Pi^1_{n+1};<math>
- <math>\Sigma^1_n \subset \Pi^1_{n+1};<math>
- <math>\Sigma^1_n \subset \Sigma^1_{n+1}.<math>
A set that is in <math>\Sigma^1_n<math> for some n is said to be projective.
External links:
See http://planetmath.org/encyclopedia/AnalyticHierarchy.html at PlanetMath.
Related links
Top visited
0 of
0 links
[no links posted yet]
>> place link >>
Discussion
Last posted
0 of
0 messages
[no messages posted yet]
>> post message >>
Watch
You can
add this article to your own "watchlist" and receive e-mail notification about all changes in this page.
