Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Categories: Mathematical logic | Set theory

Analytical hierarchy

In mathematical logic and descriptive set theory, the analytical hierarchy is a second-order analogue of the arithmetical hierarchy.

The standard notation $\Sigma^1_0 = \Pi^1_0 = \Delta^1_0$ 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 $\Sigma^1_1$ formula is a formula of the form $\exists X \phi$ , where X is now a predicate and $\phi \in \Sigma^1_0$ ,
while a $\Sigma^1_1$ set is a set of the form

$\{x : (\exists y \in S)\ R(x,y) \}$ ,

where S is Borel and R is a relation. A $\Sigma^1_1$ set is said to be analytic, and can thus be seen as a projection of a Borel set.

A $\Pi^1_1$ formula is the negation of a $\Sigma^1_1$ formula,
while a $\Pi^1_1$ set is the complement of a Borel set. A $\Pi^1_1$ set is said to be co-analytic.

Generalizing this construction, a $\Sigma^1_{n+1}$ formula is a formula of the form $\exists X \phi$ where X is a predicate and $\phi \in \Sigma^1_n;$
and a $\Sigma^1_{n+1}$ set is a set of the form

$\{x : (\exists y \in S)\ R(x,y) \},$

where S is $\Sigma^1_n$ .

A $\Pi^1_n$ formula is the negation of a $\Sigma^1_n$ formula,
and a $\Pi^1_n$ set is the complement of a $\Sigma^1_n$ set.

A formula or set is called $\Delta^1_n$ if it is both $\Sigma^1_n$ and $\Pi^1_n$ .

We have the 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 projective. We may for example define the set of "first projective" subsets of Rⁿ to be the set of all subsets which are projections of Borel subsets of R^{n + 1}; it will be the set of $\Sigma^1_1$ subsets. Then we may define "second projective" sets as projections of first projective sets or complements thereof, producing the set of a $\Sigma^1_2$ sets, and so on. A set is projective, then, if it belongs to some level of this hierarchy.

External link

PlanetMath page

Categories: Mathematical logic | Set theory

Science Fair Project Encyclopedia Contents Page

10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects