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 $L$, glossed as the relation ‘loves’ for simplicity.

More precisely, let $\mathbf{D}=\{Jackie, Kim, Tamia\}$ be the domain of the structure $\mathbf{S}$, and let $I(L)=\{\langle\mathbf{c}, \mathbf{d}\rangle \mid \mathbf{c}\text{ loves }\mathbf{d}\}$. So $I(L)$ is the set of all pairs of people $\mathbf{c}$, $\mathbf{d}$, such that $\mathbf{c}$ loves $\mathbf{d}$. Of course, this is a made up example, so let’s specify that $$I(L)=\{\langle\text{Jackie}, \text{Kim}\rangle, \langle\text{Kim}, \text{Jackie}\rangle, \langle\text{Tamia}, \text{Jackie}\rangle\}.$$ 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:

1. $\exists x \exists y L(x, y)$

2. $\exists x \forall y L(x, y)$

3. $\forall x \exists yL(x,y)$

4. $\forall x \forall y L(x, y)$

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 $\exists x \exists y L(x,y)$. This may be read as “There is an $x$ and a $y$ such that $x$ loves $y$”, or in other words, there is at least one pair of people such that one loves the other.

As usual, the question is whether $\exists x \exists y L(x, y)$ is true in $\mathbf{S}$ or not. That is, is it the case that $\mathbf{S} \models \exists x \exists y L(x, y)$? 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:

$\mathbf{S} \models \exists x P(x)[\mathbf{a}]$ iff there is an $x$-variant assignment $\mathbf{a}'$ such that $\mathbf{S} \models P(x)[\mathbf{a}']$.

We can generalize this to any formula $Y$ of $\mathcal{L}_1$ so that it says:

$\mathbf{S} \models \exists x Y[\mathbf{a}]$ iff there is an $x$-variant assignment $\mathbf{a}'$ such that $\mathbf{S} \models Y[\mathbf{a}']$.

Note that $Y$ 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 $Y$, you can put $\exists x$ ($\forall x$) in front to get a quantified formula $\exists x Y$ ($\forall x Y$), 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 $\exists x \exists y L(x, y)$. As mentioned, this should come out true. Let’s see how this comes about using our definitions. First, take any $\mathbf{a}$ whatsoever, since this is a sentence. Then, let’s see when it is the case that $\mathbf{S} \models \exists x \exists y L(x, y)[\mathbf{a}]$. Well, by the above, we have that:

$\mathbf{S} \models \exists x \exists y L(x,y)[\mathbf{a}]$ iff there is an $x$-variant assignment $\mathbf{a}'$ such that $\mathbf{S} \models \exists y L(x,y)[\mathbf{a}']$.

Note that we got rid of the first quantifier. However, we are now working with a hypothesis, choosing a value for $x$ that we think will make the resulting formula $\exists yL(x,y)$ satisfied under $\mathbf{a}'$ (and not $\mathbf{a}$ anymore). Since we see the definition of $I$ as regards $L$, we know that Jackie and Kim is a good pair to choose, since by $I(L)$, they love each other (and specifically, Jackie loves Kim). So let’s choose the $x$-variant assignment $\mathbf{a}^x_\text{Jackie}$. Then, we need to plug these new values into the definition to calculate again. In particular:

$\mathbf{S} \models \exists y L(x,y)[\mathbf{a}^x_\text{Jackie}]$ iff there is a $y$-variant (!) assignment $(\mathbf{a}^x_\text{Jackie})'$ such that $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Jackie})']$.

Again, the hypothesis is that if $x$ evaluates to Jackie, then we should find a value for $y$ such that $L(x, y)$ becomes satisfied in $\mathbf{S}$. Of course, this happens precisely when $y$ evaluates to Kim. So we take the $y$-variant assignment of $\mathbf{a}^x_\text{Jackie}$ (and not $\mathbf{a}$!) that still assigns Jackie to $x$, but now also explicitly assigns Kim to $y$. We can represent this as $(\mathbf{a}^x_\text{Jackie})^y_\text{Kim}$. This is the assignment that is just like $\mathbf{a}$ except $x$ is assigned Jackie, and $y$ is assigned Kim. Thus, we have that: $$\mathbf{S}\models L(x, y)[(\mathbf{a}^x_\text{Jackie})^y_\text{Kim}].$$

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 $\mathbf{S} \models \exists x \exists y L(x, y)[\mathbf{a}]$.

Here are the steps again, in succession: $$\begin{aligned} \mathbf{S} \models & \exists x \exists y L(x, y)[\mathbf{a}]\\ \mathbf{S} \models & \exists y L(x,y)[\mathbf{a}^x_\text{Jackie}]\\ \mathbf{S}\models & L(x, y)[(\mathbf{a}^x_\text{Jackie})^y_\text{Kim}]. \end{aligned}$$ 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 $L(x, y)$ by finding an appropriate value for $x$, and for $y$, that makes $L(x, y)$ 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:

$\mathbf{S} \models \forall x Y[\mathbf{a}]$ iff for every $x$-variant assignment $\mathbf{a}'$, $\mathbf{S} \models Y[\mathbf{a}']$.

As you can see, this says that $\forall x Y$ is satisfied in $\mathbf{S}$ relative to $\mathbf{a}$ iff every $x$-variant assignment $\mathbf{a}'$ satisfies $Y$ in $\mathbf{S}$. 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, $\exists x \forall y L(x, y)$. 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 $\mathbf{a}$ to start with, and get to the instance of the $\exists$-definition:

$\mathbf{S} \models \exists x \forall y L(x,y)[\mathbf{a}]$ iff there is an $x$-variant assignment $\mathbf{a}'$ such that $\mathbf{S} \models \forall y L(x,y)[\mathbf{a}']$.

Thus, we need to find a value for $x$ that would make the open formula $\forall y L(x, y)$ satisfied in the structure $\mathbf{S}$, which in turn would mean the open formula $L(x, y)$ satisfied for every value of $y$ 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 $x$ to start. Plugging these into our $\forall$-definition, we have that:

1. $\mathbf{S} \models \forall y L(x,y)[\mathbf{a}^x_\text{Jackie}]$ iff for every $y$-variant assignment $(\mathbf{a}^x_\text{Jackie})'$, $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Jackie})']$;

2. $\mathbf{S} \models \forall y L(x,y)[\mathbf{a}^x_\text{Kim}]$ iff for every $y$-variant assignment $(\mathbf{a}^x_\text{Kim})'$, $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Kim})']$;

3. $\mathbf{S} \models \forall y L(x,y)[\mathbf{a}^x_\text{Tamia}]$ iff for every $y$-variant assignment $(\mathbf{a}^x_\text{Tamia})'$, $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Tamia})']$.

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 $x$, we can find a value for $y$ such that $x$ does not love $y$, thereby making sure that there is no one that loves everyone.

In particular, we have that:

1. $\mathbf{S} \not\models L(x,y)[(\mathbf{a}^x_\text{Jackie})^y_\text{Jackie}]$;

2. $\mathbf{S} \not\models L(x,y)[(\mathbf{a}^x_\text{Kim})^y_\text{Kim}]$;

3. $\mathbf{S} \not\models L(x,y)[(\mathbf{a}^x_\text{Tamia})^y_\text{Tamia}]$.

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: $$\mathbf{S} \not\models \exists x \forall y L(x, y).$$

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 $\mathbf{S}'=\langle\mathbb{N}, I\rangle$, where $I(L)=\{\langle j, k\rangle \mid j\leq k\}$, then it is true that $\exists x \forall y L(x, y)$. That is, there is a particular natural number that is less than or equal to every other natural number. That number is $0$. The problem is that the relevant instance of this is:

$\mathbf{S} \models \forall y L(x,y)[\mathbf{a}^x_0]$ iff for every $y$-variant assignment $(\mathbf{a}^x_0)'$, $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_0)']$

The above is clearly true, since $0$ 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 $0$ is less than or equal to every other number.

Universal-existential

Now let’s consider the formula $\forall x \exists y L(x, y)$. Does this mean the same thing as $\exists x \forall y L(x,y)$? In fact, it does not! Note that one says that there is an $x$ which is in the relation $L$ for every $y$, and the other one says every $x$ is in the relation $L$ with some $y$. These two are not, in general, equivalent. For example, if we read $L$ as ‘loves’, $\exists x \forall y L(x,y)$ says, as we have just seen, that there is someone who loves everyone. On the other hand, if we take $\forall x \exists y L(x, y)$, this says that everyone loves someone. In fact, if we check the second sentence, unlike the first, it will come out true in $\mathbf{S}$!

Here, we start with the $\forall$-definition, since the first quantifier is a universal. Thus:

$\mathbf{S} \models \forall x \exists y L(x,y)[\mathbf{a}]$ iff for every $x$-variant assignment $\mathbf{a}'$, $\mathbf{S} \models \exists y L(x,y)[\mathbf{a}']$.

Again, we need to continue with the right hand side. In particular, we need to check whether for every choice of value for $x$, there is a choice of $y$ for which $L(x,y)$ is satisfiable in $\mathbf{S}$.

We only have three people in our domain, so checking for every value of $x$ is not a huge pain. In particular, we need to check each of:

1. $\mathbf{S} \models \exists y L(x,y)[\mathbf{a}^x_\text{Jackie}]$ iff there is a $y$-variant assignment $(\mathbf{a}^x_\text{Jackie})'$ such that $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Jackie})']$;

2. $\mathbf{S} \models \exists y L(x,y)[\mathbf{a}^x_\text{Kim}]$ iff there is a $y$-variant assignment $(\mathbf{a}^x_\text{Kim})'$ such that $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Kim})']$;

3. $\mathbf{S} \models \exists y L(x,y)[\mathbf{a}^x_\text{Tamia}]$ iff there is a $y$-variant assignment $(\mathbf{a}^x_\text{Tamia})'$ such that $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Tamia})']$.

Notice that unlike before, we want each of the right hand sides to hold, since we need to consider every possible value for $x$ in the domain. On the other hand, for each of the three, we only need to find a single value for $y$ for which $L(x, y)$ is satisfied. This can be done easily:

1. $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Jackie})^y_\text{Kim}]$;

2. $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Kim})^y_\text{Jackie}]$;

3. $\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Tamia})^y_\text{Jackie}]$.

Thus, for every choice of $x$, there is a choice for $y$ such that $L(x, y)$ is satisfied in $\mathbf{S}$. So as expected: $$\mathbf{S} \models \forall x \exists y L(x, y).$$

Universal-universal

If we take our calculations stepwise, it is the formula $\forall x \forall y L(x, y)$ that will take the most amount of time, since we need to check $L(x, y)$ in $\mathbf{S}$ for every pair of values $x$ and $y$. Since we have three people in our domain, this will mean checking $L(x, y)$ for 9 pairs of values (an exponential growth!). For what the sentence $\forall x \forall y L(x, y)$ says relative to $\mathbf{S}$ 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 $\mathbf{S}$. 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 $y$-variant-of-the-$x$-variant-of-$\mathbf{a}$. We can represent all these assignments in three subsequent graphs for each choice of $x$, to make it more vivid. Thus:

Again, as mentioned above, relative to any of the 9 leaves in the above trees, $L(x, y)$ should come out satisfied in $\mathcal{L}_1$. So there are 6 assignments, 2 for each tree, that entail individually that $$\mathbf{S}\not\models\forall x \forall y L(x, y).$$