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.

If you have a formula with existential quantifiers, it is important in which order they appear.

Just to make an easy example:

$\forall$ man $\exists$ woman: the woman is the true love of the man

which is obviously a different statement than

$\exists$ woman $\forall$ man: the women is the true love of the man

The first one means that there a many women - eventually for every man another woman. The second statement means there is one women that is loved by all men. Good for the woman, eventually bad for the men.

If you have two existential quantifiers or two universal quantifiers, does the order make a difference?

share|improve this question
4  
No, it does not. –  Brian M. Scott Sep 23 '12 at 8:06
1  
$\forall$ man $\exists$ woman: some woman is the true love of the man -- I think it should be in this way. –  nikita2 Sep 23 '12 at 8:10
1  
Although, $\forall x \forall (y<x) : (y<x^2)$ certainly is dependent on order, since the other way round makes no sense! (even though it can be written as $\forall x \forall y : (y<x) \to (y<x^2)$ which is the same as $\forall y \forall x : (y<x) \to (y<x^2)$) –  NeuroFuzzy Sep 23 '12 at 9:07
add comment

3 Answers

up vote 7 down vote accepted

Any number of successive quantifiers of the same kind can be replaced by a single quantifier by combining the quantified variables into a tuple; e.g. $\forall x\forall y$ is equivalent to $\forall(x,y)$. The order in the tuple is irrelevant, and thus so is the order of the quantifiers.

share|improve this answer
    
The question asks about ∀+∃ whereas you answer, accept and upvote mostly the answer to the different, ∀+∀ question. What is even more surprising is that the duplicate question has the same attitude, math.stackexchange.com/questions/491783/…! –  Val Jan 9 at 23:32
add comment

The fact that you can't swap $\forall$ and $\exists$ is a point on which teachers insist a lot even if it is not always true. But it is true if the two things are linked.

Let $u=\left(u_n\right)_{n\in \mathbb{N}} \in \mathbb{R}^\mathbb{N}$

If you say $\forall n \in \mathbb{N}, \exists n_0 \in \mathbb{N}^*, u_n > 0, u_{n_0} = 2$ or $\exists n_0 \in \mathbb{N}^*, \forall n \in \mathbb{N}, u_n > 0, u_{n_0} = 2$ you're saying the exact same thing because the two variables aren't linked. This doesn't happen often but sometimes it does.

You can swap $\forall$ and $\exists$ if they aren't linked by some relation.

If you say $\forall a \in \mathbb{R}, \forall b \in [-|a|,+|a|], |b| \le |a|$, you obviously can't swap them.

If you have two $\forall$ or two $\exists$, you can swap them if the first one isn't used in the definition of the other one.

Here's a real example where you can swap things around:

$$f : \left[a, b\right] \to \mathbb{R} \\ x \mapsto f(x)$$

$f \in C^0$

$f$ is differentiable on $\left]a, x_0\right[ \cup \left]x_0, b\right[$ for a given $x_0$

Prove that "$f'$ has a finite limit at $x_0$"$\implies$ "$f$ is differentiable at $x_0$ and $f'(x_0) = \lim_{x\to x_0}f(x) = f'(x_0)$

If you do this exercise, at some point, you should have two "definitions of the limit" withing the same expression with 2 couples of independent variables that'll you'll move around to get what you want.

share|improve this answer
add comment

Yes, it matters. The statements are classified differently in the arithmetical hierarchy.

share|improve this answer
4  
You've misunderstood the question, I think. The OP understands that a universal and an existential cannot be switched, but asks whether two universals or two existentials can be switched. –  Alex Kruckman Sep 23 '12 at 9:17
add comment

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.