Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
Also, if you quote from somewhere you should include the reference to wherever you quoted from. –  Asaf Karagila May 13 '12 at 15:21

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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