# Arithmetic hierarchy definition

From Wikipedia, Arithmetic hierarchy:

The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted $\Sigma^0_n$ and $\Pi^0_n$ for natural numbers ''n'' (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters. If a formula $\phi$ is logically equivalent to a formula with only bounded quantifiers then $\phi$ is assigned the classifications $\Sigma^0_0$ and $\Pi^0_0$. The classifications $\Sigma^0_n$ and $\Pi^0_n$ are defined inductively for every natural number ''n'' using the following rules: *If $\phi$ is logically equivalent to a formula of the form $\exists n_1 \exists n_2\cdots \exists n_k \psi$, where $\psi$ is $\Pi^0_n$, then $\phi$ is assigned the classification $\Sigma^0_{n+1}$. *If $\phi$ is logically equivalent to a formula of the form $\forall n_1 \forall n_2\cdots \forall n_k \psi$, where $\psi$ is $\Sigma^0_n$, then $\phi$ is assigned the classification $\Pi^0_{n+1}$. Also, a $\Sigma^0_n$ formula is equivalent to a formula that begins with some existential quantifiers and alternates $n-1$ times between series of existential and universal quantifiers; while a $\Pi^0_n$ formula is equivalent to a formula that begins with some universal quantifiers and alternates similarly.

The first question is: what does "set parameters" mean? I heard of function and predicate parameter, but not set parameter.

The second question is:

*If $\phi$ is logically equivalent to a formula of the form $\exists n_1 \exists n_2\cdots \exists n_k \psi$, where $\psi$ is $\Pi^0_n$, then $\phi$ is assigned the classification $\Sigma^0_{n+1}$. *If $\phi$ is logically equivalent to a formula of the form $\forall n_1 \forall n_2\cdots \forall n_k \psi$, where $\psi$ is $\Sigma^0_n$, then $\phi$ is assigned the classification $\Pi^0_{n+1}$.

The question is how can $\phi$ be transformed into a form that has existential or universal quantifier? I am getting much confusion at here. How can we double, triple etc. quantifier assignments?

• It is a "second-order" parameter. If you think about it in terms of computability this means that you have an oracle. – Asaf Karagila May 13 '12 at 15:21
• Also, if you quote from somewhere you should include the reference to wherever you quoted from. – Asaf Karagila May 13 '12 at 15:21
• @AsafKaragila Can you point to a reference that defines or explains the correspondence between second order parameters as an oracle? – Łukasz Lew Jan 2 at 0:11
• @ŁukaszLew: It's a function, which is a second-order object. – Asaf Karagila Jan 2 at 0:27

The following formula has a set parameter $X$: $(\forall n) [ n \in X]$. It is much more common in mathematical settings to use set parameters instead of "predicate parameters" like in $(\forall n)[X(n)]$.
The method to put a formula into prenex normal form is described at the Wikipedia article. If you start with the formula $(\forall n)[(\forall m) [m \in X] \to n \in X]$ then a prenex normal form is $(\forall n)(\exists m)[m \not \in X \lor n \in X]$, so the original formula is equivalent to a $\Pi^0_2$ formula.