On quantifiers and bound variables

We now know how to deal with any formula of $\mathcal{L}_1$ that does not have any quantifiers occurring in it. As we just saw, in such cases, the assignment function does not do much, and you may very well wonder why there is even an assignment function distinct from an interpretation function when they function very much the same.

Well, the reason why we do need a separate variable assignment function over and above the interpretation function for constants and predicates is because sometimes, we want to actually vary the variable assignment, without varying the interpretation of the constants and the predicates. And indeed, using quantifiers and binding variables is a way to systematically incorporate these variations into the meaning of complex expressions.

How to do this was already briefly sketched above. Let’s look at it in the simplest case, now from a more formal point of view. First, take $\exists x P(x)$, where $x$ is a a variable and $P$ is a one-place predicate. You can read this as “There exists an $x$ such that $P(x)$”, or “There is an $x$ such that $x$ is $P$”, or some variation of the above. At any rate, what this formula (and indeed, sentence) says is that there is a way of assigning a value to the variable $x$ (there is an assignment) such that $P(x)$ is satisfied under that assignment. In other words, it says that there is a member of the domain that is in the interpretation of $P$. Or in yet other words, the interpretation of $P$ is non-empty. Put as before, it might also be taken to say that $P(x)$ has a solution.

Suppose $\mathbf{S}=\langle\mathbf{D}, I\rangle$ is a structure with (non-empty) domain $\mathbf{D}$ being the set of all living things on the planet (at this moment), and $I(P)$ is a subset of the domain consisting of all pandas. Then, we can ask: is the sentence $\exists x P(x)$ true in $\mathbf{S}$? Well, the answer is yes if there is an assignment $\mathbf{a}$ that renders $P(x)$ satisfied under $\mathbf{S}$ and $\mathbf{a}$, and otherwise, the answer is no. Thankfully, at the moment of writing this book (and hopefully, at the moment of reading it), there are pandas among the living things on the planet. Thus, $I(P)$ is a non-empty set, and so there should be an assignment that manages to assign an actual panda to $x$, thereby satisfying $P(x)$ in $\mathbf{S}$.

For example, in Figure 7.1, it is noted that the panda $\text{Tián Tián} \in I(P)$. Thus, we can find an assignment that makes $P(x)$ satisfied in $\mathbf{S}$, namely, any assignment that assigns Tián Tián to $x$. In fact, making use of $x$-variance, we can say that given any assignment $\mathbf{a}$, the $x$-variant assignment $\mathbf{a}^x_\text{Tián Tián}$ satisfies $P(x)$ in $\mathbf{S}$. In other words, $\mathbf{S} \models P(x)[\mathbf{a}^x_\text{Tián Tián}]$, since $I(x)[\mathbf{a}^x_\text{Tián Tián}]=\mathbf{a}^x_\text{Tián Tián}(a)=\text{Tián Tián}$ and $\text{Tián Tián} \in I(P)$.

Now remember that what we were evaluating originally is whether $\mathbf{S} \models \exists x P(x)$, i.e., whether $\exists x P(x)$ is true in $\mathbf{S}$. And we said that it is true if we can find and appropriate assignment under which $P(x)$ is satisfied in $\mathbf{S}$. Since we have found such an assignment, $\mathbf{S} \models \exists x P(x)$. Note that this is really just a precise way of saying: there is a panda!

Clearly, this is a lot of words, and as we have seen, in formal logic, it is possible to say a lot of things in very few words (symbols). In general, what we can say is the following:

$\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}']$.

Clearly, our previous reasoning does conform to this definition, since $\mathbf{a}^x_\text{Tián Tián}$ is such an assignment, as we have shown.

Now let’s see the same type of reasoning with the universal quantifier $\forall$. In fact, we can take the formula $\forall x P(x)$ relative to the structure $\mathbf{S}$, as before. In this case, the sentence can be read “For every $x$, $P(x)$”, or “Every $x$ is $P$”, or some variant of this. Now if $\exists x P(x)$ meant that there is an assignment under which $P(x)$ is satisfied in $\mathbf{S}$, then $\forall x P(x)$ says under every assignment, $P(x)$ is satisfied in $\mathbf{S}$. Again, we can express what $\forall x P(x)$ says in various ways. For example, it says that every member of the domain is in the interpretation of $P$, or that the domain $D=I(P)$, or that $P(x)$ has only solutions in $\mathbf{S}$. Or again, it says: everything is a panda!

Clearly, not everything is a panda in general, but focusing on $\mathbf{S}$, it is also not true that every living thing is a panda. Thus, it should be the case that $\forall x P(x)$ comes out false in $\mathbf{S}$. And indeed, this is the case. First, we have the general case where:

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

But again, is it true that for every $x$-variant assignment $\mathbf{a}'$, $\mathbf{S} \models P(x)[\mathbf{a}']$? Clearly not. For example, among the currently living things in the world, there is Kanzi the bonobo – that is, $\text{Kanzi} \in D$. Now Kanzi is not a panda, so $\text{Kanzi} \notin I(P)$. So if we take an $x$-variant assignment $\mathbf{a}^x_\text{Kanzi}$ (no matter what $\mathbf{a}$ was initially), then $P(x)$ is clearly not satisfied in $\mathbf{S}$. That is, $\mathbf{S} \not\models P(x)[\mathbf{a}^x_\text{Kanzi}]$. So it is not the case that every $x$-variant assignment $\mathbf{a}'$ is such that $\mathbf{S} \models P(x)[\mathbf{a}']$. So $\mathbf{S} \not\models \forall x P(x)[\mathbf{a}]$, as expected. In other words, $\forall x P(x)$ is false – not every living thing is a panda.

To reiterate what we have seen here, when we have $\exists x P(x)$ true in a structure, it means we can find at least one assignment under which $P(x)$ is satisfied, while if we have $\forall x P(x)$ true in a structure, it means we can find that every assignment of a value to $x$ satisfies $P(x)$.