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?
Arithmetic hierarchy alternating between series of existential and universal quantifiers
2
$\begingroup$
logic
1 Answers
2
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.
-
0The 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 – 2012-05-31
-
1All people have/had a mother, but there is no person that is *everybody's* mother. – 2012-05-31
-
0I added an example. There are many, I can think of very few instances where meaning does not change. – 2012-05-31
-
0Right, thank you very much everyone. – 2012-05-31