Confused between Nested Quantifiers

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.)


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?