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?

1 Answers 1

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.

  • 0
    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 equivalent2012-05-31
  • 1
    All people have/had a mother, but there is no person that is *everybody's* mother.2012-05-31
  • 0
    I added an example. There are many, I can think of very few instances where meaning does not change.2012-05-31
  • 0
    Right, thank you very much everyone.2012-05-31