I am reading nested quantifiers. I am confused in between two cases,
1. Existential Quantifier before Universal Quantifier
2. Universal Quantifier before Existential Quantifier
I would be very thankful if someone highlights the difference between them and also give an example.
Thanks in advance.
On
To elaborate on my comment, imagine that a teacher assigns a set of questions $Q$ for homework to a class (set) $S$ of students. Contrast the following two scenarios.
Scenario 1. Suppose that there is no student who can solve all the questions on her own, but still each of the questions has been solved by at least one student. In this case, if I have a doubt in any given question, I can ask around and I will find someone who can help me. Of course, the same person might not be able to help me with all the questions.
We can say this in symbols using:
$\forall q \in Q \ \exists s \in S \ : \ $s$ \text{ can solve } q$.
Scenario 2. Imagine that there is a particularly bright student in class who can solve all the questions. In this case, if I cannot solve any question, I simply need to ask that particular student and she can definitely help. My job of finding help with questions is therefore even easier.
We can formally write as:
$\exists s \in S \ \forall q \in Q : \ $s$ \text{ can solve } q$.
Do you see the difference between the two statements now?
On
Here's a simple example that I keep in mind when teaching the distinction to students; consider these two statements:
The first statement is true (over the reals, say) but the second is false.
On
Another way to think about this comes as to see what quantifiers look in the context of classical propositional logic which has truth set {0, 1}. Since we only have two truth values here, if I say "for all p, p" I've basically said "p is false, and p is true." So, we can interpret, at least here, "for all" as meaning a conjunction "^". So, for any such formula p, $\forall p $(p) means (0^1), and $\forall p$ ((p v q) ^ q) means
(((0 v q) ^q)^((1 v q)^q)).
"There exists" means "for at least one", which we can interpret as meaning a disjunction "v" in this context. So, $\exists p$ means (0 v 1), and $\exists p$ ((p v q) ^ q) means (((0 v q) ^q)v((1 v q)^q)).
Now let us see how the quantifiers behave when we switch them.
$\forall q $ $\exists p$ ((pvq)^q) becomes
$\forall q $ (((0 v q) ^q)v((1 v q)^q))) which becomes
((((0 v 0) ^0)v((1 v 0)^0))^(((0 v 1)^1)v((1 v 1)^1)))
On the other hand
$\exists p$ $\forall q$ ((p v q)^q) becomes
$\exists p$ (((p v 0)^0)^((p v 1)^1)) which becomes
((((0 v 0)^0)^((0 v 1)^1))v(((1 v 0)^0)^((1 v 1)^1)))
If you think of "for all" as indicating a conjunction for 2-element sets as the above suggests one might do, then for sets with more than 3 elements, and sets with an infinity of elements, then "for all" will indicate an extended conjunction, and similarly you'll have "there exists" as an extended disjunction. What do you do with 1-element sets though under this interpretation? Simple, all quantifiers effectively become meaningless, and the distinction between the universal and existential quantifiers breaks down. So, you just write the element of the set in any formula and you can forget about quantifiers here.
On
When a statement contains more than one quantifier, think about the quantifiers one at a time, in order.
Existential Quantifier before Universal Quantifier
Consider the statement $\exists x \forall y L(x,y)$, where the universe of discourse is the set of all people and $L(x,y)$ means "$x$ likes $y$". This statement says that there is some person $x$ such that $\forall y L(x,y)$ is true. Statement $\forall y L(x,y)$ means that for every person $y$, $x$ likes $y$, or in other words $x$ likes every person, or just $x$ likes everyone. The original statement $\exists x \forall y L(x,y)$ now can be written as "there is some person $x$ that likes everyone". In other words, there is someone who likes everyone.
Universal Quantifier before Existential Quantifier
On the other hand, statement $\forall x \exists y L(x,y)$ means that for every person $x$, the statement $\exists y L(x,y)$ is true. The $\exists y L(x,y)$ means that there is some person that $x$ likes, or, in other words, that $x$ likes someone. The orginal statement now can be written as "for every person $x$, there is some person that $x$ likes". In other words, everyone likes someone.
These statements don't mean the same thing. It might be the case that everyone likes someone, but it is unlikely that there is someone who likes everyone.
On
Say $M$ is the set of men, $W$ is the set of women, and we will write $w\prec m$ if woman $w$ is the mother of man $m$.
Then this says that every man $m$ has a mother:
$$\forall m\in M: \exists w\in W: w\prec m $$
This says there is a woman $w$ who is every man's mother:
$$\exists w\in W: \forall m\in M: w\prec m $$
The first one is true, but the second is false.
There is a nice way to think about quantifiers in terms of games, and then the order of the quantifiers corresponds to the order in which the players move in the game. If $f(p, q)$ is some statement, then
$$\forall p \exists q : f(p, q)$$
says that there are two players, $P$ and $Q$, playing a game. Player $P$ moves first and makes some move $p$. Player $Q$'s goal is to find a corresponding move $q$ which "beats" $p$ in the sense that $f(p, q)$ is true. The statement above is true if $Q$ has a winning strategy; otherwise, it's false. However,
$$\exists q \forall p : f(p, q)$$
says that player $Q$ moves first. So instead of finding a move $q = q(p)$ for each possible move $p$ that player $P$ can make, $Q$ must now make a single move that beats all possible moves by player $P$. Again, the statement above is true if $Q$ has a winning strategy; otherwise, it's false.
But now it should be obvious that the second game is much harder for $Q$ than the first! (To further augment this game-theoretic intuition, it might help to think of $P$ as a "devil" who is trying to thwart the "hero" $Q$. Note the similarity of the $\forall$ symbol to devil horns.)