# Thread: Order of Quantifiers changes meaning?

1. ## Order of Quantifiers changes meaning?

I was told that the order of the quantifiers will change the meaning of a statement. But why is it that sometimes these statements seem like the same even after I changed their quantifiers' order? Am I reading the statements correctly?

For example, this one...
$\forall a \exists f\; Q(a, f)$
For any airlines a, there exists a flight f.
So, all airlines have this one particular flight f.

$\exists f \forall a \; Q(a, f)$
There is a flight f that exists on all airlines in a.
So, there is one particular flight that all airlines in a have it.
In other words, all airlines have this one particular flight f. Which, is the same thing as the previous statement, isn't it?

Do the 2 statements mean the same thing?

2. The order definitely does matter ... however like many things in set theory or logic it depends on the context

The first main important thing to say is that the order can go EITHER
way. The order you use depends on what you want to say. Consider these
two sample statements, which should be considered to be about
integers:

(1) $\forall$ m $\exists$ k $\mid$ k>m which in plain English means: For any integer, there
is another integer greater than it.

(2) $\exists$ k $\forall$ m $\mid$ k>m which in plain English means: There is some integer
that is greater than every integer.

The only difference is the order of the quantifiers, but the meaning
is MUCH changed.

3. I think sometimes it is easier to understand in the context of integers because I could imagine the numbers being larger or smaller? But if we say that we apply this in other context such as the one above(the flights and airlines) given in my notes, am I still reading the statements correctly?

Maybe I should have also stated that [LaTeX ERROR: Compile failed] is defined as where "Flight f is in airline a".

I am thinking if there is a standard way of reading the statements so that I will always get the correct meaning of what the logic intends to tell be it in any type of context(integers, situation, etc). Otherwise, I find myself always generating different kind of meanings for different sentences of different contexts.

4. Ah yes ... if that's what you'd like .. the general rule of thumb is left to right following your first post and mine below it ... it'd be read as follows ...

For all airlines there exists some flight such that flight f is in airline a
for all m there exists some k such that k is greater than m

and

there exists some flight for all airlines such that flight f is in airline a
there exists some k for all m such that k is greater than m

it's about how things are restricted and when .. imagine a bottle neck ... the second statement bottlenecks you really fast and opens up ... while the first statement narrows as you progress through. When I first learned quantifiers I learned them in the context of true and false ...

Definition. Universal quantifier, $\forall x \in X) P(x)$ Let $P(x)$ be a formula in one variable with universe U. Let $X \subseteq U$. Let Q be the statement
( $\forall x \in X$ ) $P(x)$
Then Q is true if for every $a \in X$, $P(a)$ is true. Otherwise Q is false.

Definition. Existential quantifier, ( $\exists x \in X$) $P(x)$ Let $P(x)$ be a formula in one variable with universe U. Let $X \subseteq U$, $X \neq \emptyset$ . Let Q be the statement
( $\exists x \in X$) $P(x)$
Then Q is true if there is some $a \in X$ for which P(a) is true. Otherwise Q is false. [/tex]

This might help you a bit to see them ... I can add some more stuff if you'd like

5. For any airlines a, there exists a flight f.
So, all airlines have this one particular flight f.
No, the first sentence says that each airline $a$ may have its own flight $f$; it does not have to be the same for every airline. In contrast, "There is a flight $f$ that exists on every airline $a$" says that there is a single flight $f$ that works for every airline $a$.

The idea is that is choosing a witness for an existential quantifier, one is allowed to take into account all objects introduced by the preceding universal quantifiers. So, in $\forall m\,\exists k\,k>m$, one can take m into account while choosing k. For instance, one can take k = m + 1. In contrast, in $\exists k\,\forall m\,k>m$, there has to be a single k that is greater than all possible m, which is impossible.

6. Thanks imind and emakarov. I am starting to see some light now. I think you made a good point that one can take m into account while choosing k. Thanks a lot!!