Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 4.2.3 When Does Quantifier Order Matter?

Does it matter in what order we write the quantifiers?

• If they are the same, often it doesn’t matter.

If we write, for example, ∀x (∀y ((Friends(x, y) → Friends(y, x))), we’re saying that for every combination of values of x and y, the statement holds. Order doesn’t matter. To understand why it doesn’t matter, recall that:

• ∀ can be thought of as a large conjunction (expressions anded together). Order doesn’t matter in conjunctions since and is both associative and commutative.

• ∃ can be thought of as a large disjunction (expressions ored together). Again, order doesn’t matter because or is both associative and commutative.

But, to see why we can’t say that it never matters, consider this claim (similar to the bus boarding claim that we just considered):

[1] \(\forall \)x (\(\forall \)y (FinishWork(y)) \(\rightarrow \) Invited(x))

Notice that the scope of y ends before the \(\rightarrow \) . We are saying that, for any x, if everyone finishes their work, then x will be invited to the event. In other words, if everyone finishes, everyone is invited. If we try to swap the quantifiers, we must also adjust the parentheses to make sure that every variable is bound by the appropriate quantifier. Doing that, we get:

[2] \(\forall \) y (\(\forall \)x (FinishWork(y) \(\rightarrow \) Invited(x)))

Now we have that, for any y, if y finishes the work, everyone will be invited. In other words, if even one person finishes, everyone will be invited. Very different.

• If they are different, it usually does matter.

Suppose, on the other hand, that we are writing expressions over the domain of people. Then we might write:

[2] \(\forall \)x (\(\exists \)y (Father-Of(y, x)))

In other words, every person has a father. Notice that \(\exists \)y (Father-of(y, x) occurs within the scope of \(\forall \)x. So, for any particular x, we know that there’s someone who is x’s father. Definitely not necessarily the same father for every x. Suppose, on the other hand, that we’d written:

[3] \(\exists \)y (\(\forall \)x (Father-Of(y, x)))

This says something quite different. It says that there is someone (y) who is the father of everyone (all possible values of x, including himself). This is patently false.

Of course, it’s not that the other order is necessarily false. It’s just that it produces a different statement, whose truth value may be different. There are cases where the two orders happen to produce statements with the same truth value.

Define: Hates(x, y): True if x hates y.

These two statements have the same truth value (in the real world):

[5] \(\exists \)y (\(\forall \)x (Hates(x, y)))

[6] \(\forall \)x (\(\exists \)y (Hates(x, y)))

Since everyone hates Flu, both [5] and [6] are true.

Big Idea

Be careful when mixing quantifiers. Order often matters. The only way to be sure that two different expressions are logically equivalent is to use sound identities and inference rules to prove that they are. In the next chapter, we’ll see how to do that.