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?
Best Answer
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.