Analytical hierarchy
|
|
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. We may for example define the set of "first projective" subsets of Rn to be the set of all subsets which are projections of Borel subsets of Rn + 1 ; it will be the set of <math>\Sigma^1_1<math> subsets. Then we may define "second projective" sets as projections of first projective sets or complements thereof, producing the set of a<math>\Sigma^1_2<math>sets, and so on. A set is projective, then, if it belongs to some level of this hierarchy.
External link
- PlanetMath page (http://planetmath.org/encyclopedia/AnalyticHierarchy.html)