Analytical hierarchy

Definition

Work in the language of second-order arithmetic, which has number variables and set variables. It is interpreted in the standard model, where set variables range over all subsets of $\N$. A formula is arithmetical if it has no quantifiers over sets; it may have free set variables. The classes of formulas $\Sigma^1_n$ and $\Pi^1_n$ are defined by induction on $n$.

1. $\Sigma^1_0 = \Pi^1_0$ is the class of arithmetical formulas.
2. A formula is $\Sigma^1_{n+1}$ if it has the form $\exists X_1 \cdots \exists X_k \, \psi$ with $\psi$ in $\Pi^1_n$.
3. A formula is $\Pi^1_{n+1}$ if it has the form $\forall X_1 \cdots \forall X_k \, \psi$ with $\psi$ in $\Sigma^1_n$.

A set $A \subseteq \N$ is $\Sigma^1_n$, or $\Pi^1_n$, if a formula of that class defines it in the standard model. The formula must have one free number variable and no other free variables. A set is $\Delta^1_n$ if it is both $\Sigma^1_n$ and $\Pi^1_n$, and analytical if it is $\Sigma^1_n$ for some $n$.