"

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

LL

, glossed as the relation β€˜loves’ for simplicity.

More precisely, let

𝐃={Jackie,Kim,Tamia}\mathbf{D}=\{Jackie, Kim, Tamia\}

be the domain of the structure

𝐒\mathbf{S}

, and let

I(L)={⟨𝐜,𝐝⟩∣𝐜loves𝐝}I(L)=\{\langle\mathbf{c}, \mathbf{d}\rangle \mid \mathbf{c}\text{ loves }\mathbf{d}\}

. So

I(L)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)={⟨Jackie,Kim⟩,⟨Kim,Jackie⟩,⟨Tamia,Jackie⟩}.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:

Diagram with three circles labeled Kim, Jackie, and Tamia, connected by directional arrows. Arrows point from Kim to Jackie, Jackie to Kim, and from Tamia to Jackie.

Given our language, we can then express simple things like:

  1. βˆƒxβˆƒyL(x,y)\exists x \exists y L(x, y)
  2. βˆƒxβˆ€yL(x,y)\exists x \forall y L(x, y)
  3. βˆ€xβˆƒyL(x,y)\forall x \exists yL(x,y)
  4. βˆ€xβˆ€yL(x,y)\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

βˆƒxβˆƒyL(x,y)\exists x \exists y L(x,y)

. This may be read as β€œThere is an

xx

and a

yy

such that

xx

loves

yy

”, or in other words, there is at least one pair of people such that one loves the other.

As usual, the question is whether

βˆƒxβˆƒyL(x,y)\exists x \exists y L(x, y)

is true in

𝐒\mathbf{S}

or not. That is, is it the case that

π’βŠ¨βˆƒxβˆƒyL(x,y)\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:

π’βŠ¨βˆƒxP(x)[𝐚]\mathbf{S} \models \exists x P(x)[\mathbf{a}]

iff there is an

xx

-variant assignment

πšβ€²\mathbf{a}’

such that

π’βŠ¨P(x)[πšβ€²]\mathbf{S} \models P(x)[\mathbf{a}’]

.

We can generalize this to any formula

YY

of

β„’1\mathcal{L}_1

so that it says:

π’βŠ¨βˆƒxY[𝐚]\mathbf{S} \models \exists x Y[\mathbf{a}]

iff there is an

xx

-variant assignment

πšβ€²\mathbf{a}’

such that

π’βŠ¨Y[πšβ€²]\mathbf{S} \models Y[\mathbf{a}’]

.

Note that

YY

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

YY

, you can put

βˆƒx\exists x

(

βˆ€x\forall x

) in front to get a quantified formula

βˆƒxY\exists x Y

(

βˆ€xY\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

βˆƒxβˆƒyL(x,y)\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

π’βŠ¨βˆƒxβˆƒyL(x,y)[𝐚]\mathbf{S} \models \exists x \exists y L(x, y)[\mathbf{a}]

. Well, by the above, we have that:

π’βŠ¨βˆƒxβˆƒyL(x,y)[𝐚]\mathbf{S} \models \exists x \exists y L(x,y)[\mathbf{a}]

iff there is an

xx

-variant assignment

πšβ€²\mathbf{a}’

such that

π’βŠ¨βˆƒyL(x,y)[πšβ€²]\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

xx

that we think will make the resulting formula

βˆƒyL(x,y)\exists yL(x,y)

satisfied under

πšβ€²\mathbf{a}’

(and not

𝐚\mathbf{a}

anymore). Since we see the definition of

II

as regards

LL

, we know that Jackie and Kim is a good pair to choose, since by

I(L)I(L)

, they love each other (and specifically, Jackie loves Kim). So let’s choose the

xx

-variant assignment

𝐚Jackiex\mathbf{a}^x_\text{Jackie}

. Then, we need to plug these new values into the definition to calculate again. In particular:

π’βŠ¨βˆƒyL(x,y)[𝐚Jackiex]\mathbf{S} \models \exists y L(x,y)[\mathbf{a}^x_\text{Jackie}]

iff there is a

yy

-variant (!) assignment

(𝐚Jackiex)β€²(\mathbf{a}^x_\text{Jackie})’

such that

π’βŠ¨L(x,y)[(𝐚Jackiex)β€²]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Jackie})’]

.

Again, the hypothesis is that if

xx

evaluates to Jackie, then we should find a value for

yy

such that

L(x,y)L(x, y)

becomes satisfied in

𝐒\mathbf{S}

. Of course, this happens precisely when

yy

evaluates to Kim. So we take the

yy

-variant assignment of

𝐚Jackiex\mathbf{a}^x_\text{Jackie}

(and not

𝐚\mathbf{a}

!) that still assigns Jackie to

xx

, but now also explicitly assigns Kim to

yy

. We can represent this as

(𝐚Jackiex)Kimy(\mathbf{a}^x_\text{Jackie})^y_\text{Kim}

. This is the assignment that is just like

𝐚\mathbf{a}

except

xx

is assigned Jackie, and

yy

is assigned Kim. Thus, we have that:

π’βŠ¨L(x,y)[(𝐚Jackiex)Kimy].\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

π’βŠ¨βˆƒxβˆƒyL(x,y)[𝐚]\mathbf{S} \models \exists x \exists y L(x, y)[\mathbf{a}]

.

Here are the steps again, in succession:

π’βŠ¨βˆƒxβˆƒyL(x,y)[𝐚]π’βŠ¨βˆƒyL(x,y)[𝐚Jackiex]π’βŠ¨L(x,y)[(𝐚Jackiex)Kimy].\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)L(x, y)

by finding an appropriate value for

xx

, and for

yy

, that makes

L(x,y)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:

π’βŠ¨βˆ€xY[𝐚]\mathbf{S} \models \forall x Y[\mathbf{a}]

iff for every

xx

-variant assignment

πšβ€²\mathbf{a}’

,

π’βŠ¨Y[πšβ€²]\mathbf{S} \models Y[\mathbf{a}’]

.

As you can see, this says that

βˆ€xY\forall x Y

is satisfied in

𝐒\mathbf{S}

relative to

𝐚\mathbf{a}

iff every

xx

-variant assignment

πšβ€²\mathbf{a}’

satisfies

YY

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,

βˆƒxβˆ€yL(x,y)\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:

π’βŠ¨βˆƒxβˆ€yL(x,y)[𝐚]\mathbf{S} \models \exists x \forall y L(x,y)[\mathbf{a}]

iff there is an

xx

-variant assignment

πšβ€²\mathbf{a}’

such that

π’βŠ¨βˆ€yL(x,y)[πšβ€²]\mathbf{S} \models \forall y L(x,y)[\mathbf{a}’]

.

Thus, we need to find a value for

xx

that would make the open formula

βˆ€yL(x,y)\forall y L(x, y)

satisfied in the structure

𝐒\mathbf{S}

, which in turn would mean the open formula

L(x,y)L(x, y)

satisfied for every value of

yy

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

xx

to start. Plugging these into our

βˆ€\forall

-definition, we have that:

  1. π’βŠ¨βˆ€yL(x,y)[𝐚Jackiex]\mathbf{S} \models \forall y L(x,y)[\mathbf{a}^x_\text{Jackie}]

    iff for every

    yy

    -variant assignment

    (𝐚Jackiex)β€²(\mathbf{a}^x_\text{Jackie})’

    ,

    π’βŠ¨L(x,y)[(𝐚Jackiex)β€²]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Jackie})’]

    ;

  2. π’βŠ¨βˆ€yL(x,y)[𝐚Kimx]\mathbf{S} \models \forall y L(x,y)[\mathbf{a}^x_\text{Kim}]

    iff for every

    yy

    -variant assignment

    (𝐚Kimx)β€²(\mathbf{a}^x_\text{Kim})’

    ,

    π’βŠ¨L(x,y)[(𝐚Kimx)β€²]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Kim})’]

    ;

  3. π’βŠ¨βˆ€yL(x,y)[𝐚Tamiax]\mathbf{S} \models \forall y L(x,y)[\mathbf{a}^x_\text{Tamia}]

    iff for every

    yy

    -variant assignment

    (𝐚Tamiax)β€²(\mathbf{a}^x_\text{Tamia})’

    ,

    π’βŠ¨L(x,y)[(𝐚Tamiax)β€²]\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

xx

, we can find a value for

yy

such that

xx

does not love

yy

, thereby making sure that there is no one that loves everyone.

In particular, we have that:

  1. π’βŠ¨ΜΈL(x,y)[(𝐚Jackiex)Jackiey]\mathbf{S} \not\models L(x,y)[(\mathbf{a}^x_\text{Jackie})^y_\text{Jackie}]

    ;

  2. π’βŠ¨ΜΈL(x,y)[(𝐚Kimx)Kimy]\mathbf{S} \not\models L(x,y)[(\mathbf{a}^x_\text{Kim})^y_\text{Kim}]

    ;

  3. π’βŠ¨ΜΈL(x,y)[(𝐚Tamiax)Tamiay]\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:

π’βŠ¨ΜΈβˆƒxβˆ€yL(x,y).\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

𝐒′=βŸ¨β„•,I⟩\mathbf{S}’=\langle\mathbb{N}, I\rangle

, where

I(L)={⟨j,k⟩∣j≀k}I(L)=\{\langle j, k\rangle \mid j\leq k\}

, then it is true that

βˆƒxβˆ€yL(x,y)\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

00

. The problem is that the relevant instance of this is:

π’βŠ¨βˆ€yL(x,y)[𝐚0x]\mathbf{S} \models \forall y L(x,y)[\mathbf{a}^x_0]

iff for every

yy

-variant assignment

(𝐚0x)β€²(\mathbf{a}^x_0)’

,

π’βŠ¨L(x,y)[(𝐚0x)β€²]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_0)’]

The above is clearly true, since

00

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

00

is less than or equal to every other number.

Universal-existential

Now let’s consider the formula

βˆ€xβˆƒyL(x,y)\forall x \exists y L(x, y)

. Does this mean the same thing as

βˆƒxβˆ€yL(x,y)\exists x \forall y L(x,y)

? In fact, it does not! Note that one says that there is an

xx

which is in the relation

LL

for every

yy

, and the other one says every

xx

is in the relation

LL

with some

yy

. These two are not, in general, equivalent. For example, if we read

LL

as β€˜loves’,

βˆƒxβˆ€yL(x,y)\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

βˆ€xβˆƒyL(x,y)\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:

π’βŠ¨βˆ€xβˆƒyL(x,y)[𝐚]\mathbf{S} \models \forall x \exists y L(x,y)[\mathbf{a}]

iff for every

xx

-variant assignment

πšβ€²\mathbf{a}’

,

π’βŠ¨βˆƒyL(x,y)[πšβ€²]\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

xx

, there is a choice of

yy

for which

L(x,y)L(x,y)

is satisfiable in

𝐒\mathbf{S}

.

We only have three people in our domain, so checking for every value of

xx

is not a huge pain. In particular, we need to check each of:

  1. π’βŠ¨βˆƒyL(x,y)[𝐚Jackiex]\mathbf{S} \models \exists y L(x,y)[\mathbf{a}^x_\text{Jackie}]

    iff there is a

    yy

    -variant assignment

    (𝐚Jackiex)β€²(\mathbf{a}^x_\text{Jackie})’

    such that

    π’βŠ¨L(x,y)[(𝐚Jackiex)β€²]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Jackie})’]

    ;

  2. π’βŠ¨βˆƒyL(x,y)[𝐚Kimx]\mathbf{S} \models \exists y L(x,y)[\mathbf{a}^x_\text{Kim}]

    iff there is a

    yy

    -variant assignment

    (𝐚Kimx)β€²(\mathbf{a}^x_\text{Kim})’

    such that

    π’βŠ¨L(x,y)[(𝐚Kimx)β€²]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Kim})’]

    ;

  3. π’βŠ¨βˆƒyL(x,y)[𝐚Tamiax]\mathbf{S} \models \exists y L(x,y)[\mathbf{a}^x_\text{Tamia}]

    iff there is a

    yy

    -variant assignment

    (𝐚Tamiax)β€²(\mathbf{a}^x_\text{Tamia})’

    such that

    π’βŠ¨L(x,y)[(𝐚Tamiax)β€²]\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

xx

in the domain. On the other hand, for each of the three, we only need to find a single value for

yy

for which

L(x,y)L(x, y)

is satisfied. This can be done easily:

  1. π’βŠ¨L(x,y)[(𝐚Jackiex)Kimy]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Jackie})^y_\text{Kim}]

    ;

  2. π’βŠ¨L(x,y)[(𝐚Kimx)Jackiey]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Kim})^y_\text{Jackie}]

    ;

  3. π’βŠ¨L(x,y)[(𝐚Tamiax)Jackiey]\mathbf{S} \models L(x,y)[(\mathbf{a}^x_\text{Tamia})^y_\text{Jackie}]

    .

Thus, for every choice of

xx

, there is a choice for

yy

such that

L(x,y)L(x, y)

is satisfied in

𝐒\mathbf{S}

. So as expected:

π’βŠ¨βˆ€xβˆƒyL(x,y).\mathbf{S} \models \forall x \exists y L(x, y).

Universal-universal

If we take our calculations stepwise, it is the formula

βˆ€xβˆ€yL(x,y)\forall x \forall y L(x, y)

that will take the most amount of time, since we need to check

L(x,y)L(x, y)

in

𝐒\mathbf{S}

for every pair of values

xx

and

yy

. Since we have three people in our domain, this will mean checking

L(x,y)L(x, y)

for 9 pairs of values (an exponential growth!). For what the sentence

βˆ€xβˆ€yL(x,y)\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

yy

-variant-of-the-

xx

-variant-of-

𝐚\mathbf{a}

. We can represent all these assignments in three subsequent graphs for each choice of

xx

, to make it more vivid. Thus:

Tree diagram with "a^x_Jackie" at the top with three nodes branching below: (a^x_Jackie)^y_Jackie, (a^x_Jackie)^y_Kim, and (a^x_Jackie)^y_Tamia.

Choosing Jackie for the value of x

Tree diagram with "a^x_Kim" at the top with three nodes branching below: (a^x_Kim)^y_Kim, (a^x_Kim)^y_Jackie, and (a^x_Kim)^y_Tamia.

Choosing Kim for the value of x

Tree diagram with "a^x_Tamia" at the top with three nodes branching below: (a^x_Tamia)^y_Tamia, (a^x_Tamia)^y_Jackie, and (a^x_Tamia)^y_Kim.

Choosing Tamia for the value of x

Again, as mentioned above, relative to any of the 9 leaves in the above trees,

L(x,y)L(x, y)

should come out satisfied in

β„’1\mathcal{L}_1

. So there are 6 assignments, 2 for each tree, that entail individually that

π’βŠ¨ΜΈβˆ€xβˆ€yL(x,y).\mathbf{S}\not\models\forall x \forall y L(x, y).

License

Icon for the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

Learning Logic Backwards Copyright © by Peter Susanszky is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License, except where otherwise noted.