Dealing with multiple quantifiers
Letβs jump a step up in complexity. So far, we considered quantified sentences in which only a single quantifier occurred. But of course, our language has more elaborate formulas in which several quantifiers can occur in various places. This introduces a lot of complexity, and the need to be very careful when calculating with these.
There is a prototypical example here that logicians love talking about; the example of a two-place predicate
, glossed as the relation βlovesβ for simplicity.
More precisely, let
be the domain of the structure
, and let
. So
is the set of all pairs of people
,
, such that
loves
. Of course, this is a made up example, so letβs specify that
In other words, Jackie loves Kim, Kim loves Jackie, Tamie loves Jackie, but Jackie does not love Tamia, and Kim and Tamia do not love each other. This can also be represented with the following graph:
Given our language, we can then express simple things like:
And as it turns out, all of these mean completely different things! In order to see this, however, we need to see how to go on calculating, once we passed one quantifier, and moved to another.
Existential-existential
In the simplest case, we have
. This may be read as βThere is an
and a
such that
loves
β, or in other words, there is at least one pair of people such that one loves the other.
As usual, the question is whether
is true in
or not. That is, is it the case that
? By the above, we know that this should come out true, but how?
The reasoning is a simple generalization of the previous one. Previously, for atomic formulas with a unary predicate, we had:
iff there is an
-variant assignment
such that
.
We can generalize this to any formula
of
so that it says:
iff there is an
-variant assignment
such that
.
Note that
here may be any formula whatsoever, including one that already has quantifiers in it. This allows us to calculate our way through multiple quantifiers in a formula.
As we discussed before, semantic rules for formulas are always formulated in parallel to the syntactic rules. Since we have a syntactic rule that says for any formula
, you can put
(
) in front to get a quantified formula
(
), we needed a semantic rule in just those terms. The above is exactly that, in terms of the existential quantifier. Thus, once more, our semantic calculations will stepwise follow the steps of the syntactic breakdown of any formula.
Letβs return to our sentence
. As mentioned, this should come out true. Letβs see how this comes about using our definitions. First, take any
whatsoever, since this is a sentence. Then, letβs see when it is the case that
. Well, by the above, we have that:
iff there is an
-variant assignment
such that
.
Note that we got rid of the first quantifier. However, we are now working with a hypothesis, choosing a value for
that we think will make the resulting formula
satisfied under
(and not
anymore). Since we see the definition of
as regards
, we know that Jackie and Kim is a good pair to choose, since by
, they love each other (and specifically, Jackie loves Kim). So letβs choose the
-variant assignment
. Then, we need to plug these new values into the definition to calculate again. In particular:
iff there is a
-variant (!) assignment
such that
.
Again, the hypothesis is that if
evaluates to Jackie, then we should find a value for
such that
becomes satisfied in
. Of course, this happens precisely when
evaluates to Kim. So we take the
-variant assignment of
(and not
!) that still assigns Jackie to
, but now also explicitly assigns Kim to
. We can represent this as
. This is the assignment that is just like
except
is assigned Jackie, and
is assigned Kim. Thus, we have that:
Since there are no more quantifiers to deal with, and there were no connectives to begin with, this is where we bottom out. Thus, it is shown that
.
Here are the steps again, in succession:
Again, as you can see, we are working parallel to the syntactic analysis of the formula, namely, taking off a quantifier at each turn until we get to the atomic formula. And semantically, what we are trying to make sure at each turn is to have the final (now open) formula satisfied under the new assignment we constructed.
Thinking in terms of mathematics, you may think of this as finding a solution to the final expression
by finding an appropriate value for
, and for
, that makes
come out correct. And thinking intuitively, we just found two people in the domain of the structure such that one loves the other, and derived that the sentence βThere are two people such that one loves the otherβ is therefore true relative to the structure.
Existential-universal
When it comes to the use of the universal quantifier, things get more interesting. In the case of the existential quantifier, we only had to look at single solutions. But when it comes to the universal quantifier, we have to check whether everything is a solution. Again, we can generalize the previous definition for the universal to cover every formula as such:
iff for every
-variant assignment
,
.
As you can see, this says that
is satisfied in
relative to
iff every
-variant assignment
satisfies
in
. This gets more complicated when we examine how this relates to the other quantifiers in a certain formula. Of course, in general, the calculation steps are always given by the definitions, but carrying them out correctly is crucial.
Letβs take the next formula, then,
. Using our usual gloss, this means that there is someone in our domain such that they love everyone. Thus, if we are trying to figure out whether this is true or false, we need to consider every person, and see whether any of them is such that they love everyone. As it turns out, this is false. In fact, you have to be careful here, since loving everyone would mean that they love themselves too! By that fact alone, there is no one in the domain that loves everyone. Why is this case?
Well, again, we add an arbitrary assignment
to start with, and get to the instance of the
-definition:
iff there is an
-variant assignment
such that
.
Thus, we need to find a value for
that would make the open formula
satisfied in the structure
, which in turn would mean the open formula
satisfied for every value of
in turn. Since this is a finite structure, this can be checked mechanically, by taking each value one by one.
In particular, any possible solution would need to assign a value to
to start. Plugging these into our
-definition, we have that:
-
iff for every
-variant assignment
,
;
-
iff for every
-variant assignment
,
;
-
iff for every
-variant assignment
,
.
The next question is if we can make the right hand side of any of these true. And the answer, again, is no. To each of these, there is a counterexample. In particular, each counterexample shows that for every choice of
, we can find a value for
such that
does not love
, thereby making sure that there is no one that loves everyone.
In particular, we have that:
-
;
-
;
-
.
In other words, Jackie dos not love Jackie, Kim does not love Kim, Tamia does not love Tamia, and therefore, there is no one that loves everyone. So we can conclude that:
Before moving forward, we should note that the above way of checking the truth of a quantified sentence is not always possible, since some structures are infinite. For example, if
, where
, then it is true that
. That is, there is a particular natural number that is less than or equal to every other natural number. That number is
. The problem is that the relevant instance of this is:
iff for every
-variant assignment
,
The above is clearly true, since
is less than or equal to every number (including itself!). But you cannot mechanically check this for every number one by one, since there are infinitely many of them! Thankfully, mathematicians have ways of proving facts about infinitely many things that do not require an infinite amount of time to carry out. We shall not go into this, and freely refer to facts like
is less than or equal to every other number.
Universal-existential
Now letβs consider the formula
. Does this mean the same thing as
? In fact, it does not! Note that one says that there is an
which is in the relation
for every
, and the other one says every
is in the relation
with some
. These two are not, in general, equivalent. For example, if we read
as βlovesβ,
says, as we have just seen, that there is someone who loves everyone. On the other hand, if we take
, this says that everyone loves someone. In fact, if we check the second sentence, unlike the first, it will come out true in
!
Here, we start with the
-definition, since the first quantifier is a universal. Thus:
iff for every
-variant assignment
,
.
Again, we need to continue with the right hand side. In particular, we need to check whether for every choice of value for
, there is a choice of
for which
is satisfiable in
.
We only have three people in our domain, so checking for every value of
is not a huge pain. In particular, we need to check each of:
-
iff there is a
-variant assignment
such that
;
-
iff there is a
-variant assignment
such that
;
-
iff there is a
-variant assignment
such that
.
Notice that unlike before, we want each of the right hand sides to hold, since we need to consider every possible value for
in the domain. On the other hand, for each of the three, we only need to find a single value for
for which
is satisfied. This can be done easily:
-
;
-
;
-
.
Thus, for every choice of
, there is a choice for
such that
is satisfied in
. So as expected:
Universal-universal
If we take our calculations stepwise, it is the formula
that will take the most amount of time, since we need to check
in
for every pair of values
and
. Since we have three people in our domain, this will mean checking
for 9 pairs of values (an exponential growth!). For what the sentence
says relative to
is that everyone loves everyone. This means that for each person, we have to check that personβs relation to every other person.
Of course, as you may see, this sentence is false in
. In fact, for every person, there are two people whom they do not love. Kim does not love Tamia, Jackie does not love Tamia, and Tamia does not love Kim, and nobody loves themselves. Any one of these is sufficient to conclude that not everyone loves everyone. But if we want to check it directly, we need to consider all 9
-variant-of-the-
-variant-of-
. We can represent all these assignments in three subsequent graphs for each choice of
, to make it more vivid. Thus:
Choosing Jackie for the value of
Choosing Kim for the value of
Choosing Tamia for the value of
Again, as mentioned above, relative to any of the 9 leaves in the above trees,
should come out satisfied in
. So there are 6 assignments, 2 for each tree, that entail individually that