2
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.