Analytical hierarchy
From Free net encyclopedia
In mathematical logic and descriptive set theory, the analytical hierarchy is a second-order analogue of the arithmetical hierarchy; it thus continues the classification of sets and properties by their complexity to levels higher than can be defined using first-order logic.
The standard notation <math>\Sigma^1_0 = \Pi^1_0 = \Delta^1_0</math> indicates the class of first-order formulas which can be written without real parameters (or equivalently, without parameters at all). Note that the Greek letters here should be read as lightface symbols; the corresponding boldface symbols indicate the class of first-order formulas which can be written with real parameters; see projective hierarchy for more details.
A <math>\Sigma^1_1</math> formula is a formula of the form <math>\exists X \phi</math>,
where X is now a predicate on the naturals and <math>\phi \in \Pi^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 an arithmetic set of reals, and R is an arithmetic relation.
A <math>\Sigma^1_1</math> set can be seen as a lightface or recursive analog of an analytic set, since it is an arithmetic projection of an arithmetic relation, just as an analytic set is an arbitrary projection of a Borel relation.
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 <math>\Sigma^1_1</math> set.
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 \Pi^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>\Pi^1_n</math>, and R is again an arithmetic relation.
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 set is called <math>\Delta^1_n</math> if it is both <math>\Sigma^1_n</math> and <math>\Pi^1_n</math>. A <math>\Delta^1_1</math> set is said to be hyperarithmetic, and is the lightface analog of a Borel set.
(Note that it rarely makes sense to speak of a <math>\Delta^1_n</math> formula; the first quantifier of a formula is either existential or universal.)
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 analytical.