Subsection 4.1.9 Quantifier Scope
Recall that the scope of a quantifier is that part of a logical expression over which the quantifier exerts control. We’ve already said everything we absolutely need to say about this. But, when an expression contains multiple quantifiers, it’s very easy to make mistakes. So let’s talk a bit more about this issue.
First, recall that we use parentheses to provide a clear indication of the scope of every quantifier. Every quantified expression has the form:
∀x ( ) or ∃x ( )
If there are multiple quantifiers, there are multiple sets of parentheses. For example:
∀x (∀y ( ) )
Does it matter what variable names we use? Not if there’s just one quantifier. So:
∀x ( ) is equivalent to ∀y ( )
But if there are multiple quantifiers, we need to be careful. If one quantifier occurs within the scope of another one, we must use a different variable name for each one. If we don’t, we’ll probably get an expression that means something quite different from what we intended. In particular, in determining scope, we start with the innermost quantifier. Then we move outward, looking for variables that are still free and waiting to get bound.
For example, we could say that friendship is symmetric. In other words, for any two people, if x is friends with y, then y is also friends with x:
\(\forall \)x (\(\forall \)y (Friends(x, y) \(\rightarrow \) Friends(y, x)))If we hadn’t used a new variable for the second quantifier, we’d have had:
\(\forall \)x ( \(\forall \)x (Friends(x, x) \(\rightarrow \) Friends(x, x)))But this isn’t what we’re trying to say. The inner quantifier binds all occurrences of x. Friends(x, x) is true whenever someone (x) is friends with him/herself. So we have that, if you’re friends with yourself, you’re friends with yourself. The outer quantifier does nothing since there are no unbound instances of x for it to bind. Furthermore, we now have a relatively useless tautology instead of a possibly useful statement about what it means to be friends.
Exercises Exercises
Exercise Group.
1. Consider: [1] ∀x (∃y (P(x, y)) → Q(x))
1.
What is the scope of the universal quantifier in [1]?
Q(x)
\(\displaystyle (\exists y (P(x, y)) \rightarrow Q(x))\)
\(\displaystyle (\exists y (P(x, y))\)
\(\displaystyle (P(x, y)) \rightarrow Q(x))\)
\(\displaystyle (P(x, y))\)
2.
What is the scope of the existential quantifier in [1]?
Q(x)
\(\displaystyle (\exists y (P(x, y)) \rightarrow Q(x))\)
\(\displaystyle (\exists y (P(x, y))\)
\(\displaystyle (P(x, y)) \rightarrow Q(x))\)
\(\displaystyle (P(x, y))\)