2
$\begingroup$

According to what I know, a formula is $\Sigma^0_n$ if it begins with existential quantifier and alternates $n-1$ times. However, how do we know which quantifier comes first? For example, for $\Sigma^0_7$, we can have $\forall n_1 \exists n_2 \forall n_3 \exists n_4 \forall n_5 \exists n_6$ and reorder it to $\exists n_2 \forall n_1 \exists n_4 \forall n_3 \exists n_6 \forall n_5$. So, what I am mistaken?

$\endgroup$
2
$\begingroup$

The sentence $\forall x_1\exists x_2 \varphi(x_1,x_2)$ is in general not equivalent to $\exists x_2\forall x_1 \varphi(x_1,x_2)$. So one cannot reorder in the way that you describe.

Example: Let $\varphi(x_1,x_2)$ be the formula $x_1 \lt x_2$. Then $\forall x_1\exists x_2 \varphi(x_1,x_2)$ is true in the reals, but $\exists x_2\forall x_1 \varphi(x_1,x_2)$ is not.

$\endgroup$
  • $\begingroup$ The first one would be.. for any $x_1$ there exists $x_2$ that satisfies the predicate. And the second one would be there exists $x_2$ that for any $x_1$ the predicate would be satisfied. It seems to me that those two are virtually equivalent $\endgroup$ – user1894 May 31 '12 at 3:13
  • 1
    $\begingroup$ All people have/had a mother, but there is no person that is everybody's mother. $\endgroup$ – anon May 31 '12 at 3:17
  • $\begingroup$ I added an example. There are many, I can think of very few instances where meaning does not change. $\endgroup$ – André Nicolas May 31 '12 at 3:17
  • $\begingroup$ Right, thank you very much everyone. $\endgroup$ – user1894 May 31 '12 at 3:20

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.