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.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 –  user1894 May 31 '12 at 3:13
1  
All people have/had a mother, but there is no person that is everybody's mother. –  anon May 31 '12 at 3:17
    
I added an example. There are many, I can think of very few instances where meaning does not change. –  André Nicolas May 31 '12 at 3:17
    
Right, thank you very much everyone. –  user1894 May 31 '12 at 3:20

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.