analytic hierarchy

The first level can be called $\Delta^{1}_{0}$, $\Delta^{1}_{1}$, $\Sigma^{1}_{0}$, or $\Pi^{1}_{0}$, and consists of the arithmetical formulas or relations.

A formula $\phi$ is $\Sigma^{1}_{n}$ if there is some arithmetical formula $\psi$ such that:

 $\phi(\vec{k})=\exists X_{1}\forall X_{2}\cdots QX_{n}\psi(\vec{k},\vec{X}_{n})$
 $\text{ where }Q\text{ is either }\forall\text{ or }\exists\text{, whichever % maintains the pattern of alternating quantifiers, and each }X_{i}\text{ is a % set variable (that is, second order)}$

Similarly, a formula $\phi$ is $\Pi^{1}_{n}$ if there is some arithmetical formula $\psi$ such that:

 $\phi(\vec{k})=\forall X_{1}\exists X_{2}\cdots QX_{n}\psi(\vec{k},\vec{X}_{n})$
 $\text{ where }Q\text{ is either }\forall\text{ or }\exists\text{, whichever % maintains the pattern of alternating quantifiers, and each }X_{i}\text{ is a % set variable (that is, second order)}$
Title analytic hierarchy AnalyticHierarchy 2013-03-22 12:56:48 2013-03-22 12:56:48 Henry (455) Henry (455) 4 Henry (455) Definition msc 03B15 analytical hierarchy ArithmeticalHierarchy