Chapter 31 Truth in FOL
We have introduced you to interpretations. Since, among other things, they tell us which predicates are true of which objects, they will provide us with an account of the truth of atomic sentences. However, we now need to say, precisely, what it is for an arbitrary FOL sentence to be true or false in an interpretation.
We know from chapter 27 that there are three kinds of sentence in FOL:

1.
atomic sentences,

2.
sentences whose main logical operator is a sentential connective,

3.
sentences whose main logical operator is a quantifier.
We need to explain truth for all three kinds of sentence.
We will provide a completely general explanation in this section. However, to try to keep the explanation comprehensible, we will, at several points, use the following interpretation:
 domain:

all people born before 2000 ce
 $a$:

Aristotle
 $b$:

Beyoncé
 $P(x)$:

blank _{x} is a philosopher
 $R(x,y)$:

blank _{x} was born before blank _{y}
This will be our goto example in what follows.
31.1 Atomic sentences
The truth of atomic sentences should be fairly straightforward. For sentence letters, the interpretation specifies if they are true or false. The sentence ‘$P(a)$’ should be true just in case ‘$P(x)$’ is true of ‘$a$’. Given our goto interpretation, this is true iff Aristotle is a philosopher. Aristotle is a philosopher. So the sentence is true. Equally, ‘$P(b)$’ is false on our goto interpretation.
Likewise, on this interpretation, ‘$R(a,b)$’ is true iff the object named by ‘$a$’ was born before the object named by ‘$b$’. Well, Aristotle was born before Beyoncé. So ‘$R(a,b)$’ is true. Equally, ‘$R(a,a)$’ is false: Aristotle was not born before Aristotle.
Dealing with atomic sentences, then, is very intuitive. When $\mathcal{R}$ is an $n$place predicate and ${\U0001d4b6}_{1}$, ${\U0001d4b6}_{2}$, …, ${\U0001d4b6}_{n}$ are names,
The sentence $\mathcal{R}({\U0001d4b6}_{1},{\U0001d4b6}_{2},\mathrm{\dots},{\U0001d4b6}_{n})$ is true in an interpretation iff $\mathcal{R}$ is true of the objects named by ${\U0001d4b6}_{1}$, ${\U0001d4b6}_{2}$, …, ${\U0001d4b6}_{n}$ (in that order) in that interpretation.
Recall, though, that there is a special kind of atomic sentence: two names connected by an identity sign constitute an atomic sentence. This kind of atomic sentence is also easy to handle. Where $\U0001d4b6$ and $\U0001d4b7$ are any names,
$\U0001d4b6=\U0001d4b7$ is true in an interpretation iff $\U0001d4b6$ and $\U0001d4b7$ name the very same object in that interpretation.
So in our goto interpretation, ‘$a=b$’ is false, since Aristotle is distinct from Beyoncé.
31.2 Sentential connectives
We saw in chapter 27 that FOL sentences can be built up from simpler ones using the truthfunctional connectives that were familiar from TFL. The rules governing these truthfunctional connectives are exactly the same as they were when we considered TFL. Here they are:

‣
$\mathcal{A}\wedge \mathcal{B}$ is true in an interpretation iff both $\mathcal{A}$ is true and $\mathcal{B}$ is true in that interpretation.

‣
$\mathcal{A}\vee \mathcal{B}$ is true in an interpretation iff either $\mathcal{A}$ is true or $\mathcal{B}$ is true in that interpretation.

‣
$\neg \mathcal{A}$ is true in an interpretation iff $\mathcal{A}$ is false in that interpretation.

‣
$\mathcal{A}\to \mathcal{B}$ is true in an interpretation iff either $\mathcal{A}$ is false or $\mathcal{B}$ is true in that interpretation.

‣
$\mathcal{A}\leftrightarrow \mathcal{B}$ is true in an interpretation iff $\mathcal{A}$ has the same truth value as $\mathcal{B}$ in that interpretation.
This presents the very same information as the characteristic truth tables for the connectives; it just does so in a slightly different way. Some examples will probably help to illustrate the idea. (Make sure you understand them!) On our goto interpretation:

‣
‘$a=a\wedge P(a)$’ is true.

‣
‘$R(a,b)\wedge P(b)$’ is false because, although ‘$R(a,b)$’ is true, ‘$P(b)$’ is false.

‣
‘$a=b\vee P(a)$’ is true.

‣
‘$\neg a=b$’ is true.

‣
‘$P(a)\wedge \neg (a=b\wedge R(a,b))$’ is true, because ‘$P(a)$’ is true and ‘$a=b$’ is false.
Make sure you understand these examples.
31.3 When the main logical operator is a quantifier
The exciting innovation in FOL, though, is the use of quantifiers, but expressing the truth conditions for quantified sentences is a bit more fiddly than one might first expect.
Here is a naïve first thought. We want to say that ‘$\forall xF(x)$’ is true iff ‘$F(x)$’ is true of everything in the domain. This should not be too problematic: our interpretation will specify directly what ‘$F(x)$’ is true of.
Unfortunately, this naïve thought is not general enough. For example, we want to be able to say that ‘$\forall x\exists yL(x,y)$’ is true just in case (speaking roughly) ‘$\exists yL(x,y)$’ is true of everything in the domain. But our interpretation does not directly specify what ‘$\exists yL(x,y)$’ is true of. Instead, whether or not this is true of something should follow just from the interpretation of the predicate ‘$L$’, the domain, and the meanings of the quantifiers.
So here is a second naïve thought. We might try to say that ‘$\forall x\exists yL(x,y)$’ is to be true in an interpretation iff $\exists yL(\U0001d4b6,y)$ is true for every name $\U0001d4b6$ that we have included in our interpretation. Similarly, we might try to say that $\exists yL(\U0001d4b6,y)$ is true just in case $L(\U0001d4b6,\U0001d4b7)$ is true for some name $\U0001d4b7$ that we have included in our interpretation.
Unfortunately, this is not right either. To see this, observe that our goto interpretation only interprets two names, ‘$a$’ and ‘$b$’. But the domain—all people born before the year 2000 ce—contains many more than two people. (And we have no intention of trying to correct for this by naming all of them!)
So here is a third thought. (And this thought is not naïve, but correct.) Although it is not the case that we have named everyone, each person could have been given a name. So we should focus on this possibility of extending an interpretation by adding a new name. We will offer a few examples of how this might work, centering on our goto interpretation, and we will then present the formal definition.
In our goto interpretation, ‘$\exists xR(b,x)$’ should be true. After all, in the domain, there is certainly someone who was born after Beyoncé. Lady Gaga is one of those people. Indeed, if we were to extend our goto interpretation—temporarily, mind—by adding the name ‘$c$’ to refer to Lady Gaga, then ‘$R(b,c)$’ would be true on this extended interpretation. This, surely, should suffice to make ‘$\exists xR(b,x)$’ true on the original goto interpretation.
In our goto interpretation, ‘$\exists x(P(x)\wedge R(x,a))$’ should also be true. After all, in the domain, there is certainly someone who was both a philosopher and born before Aristotle. Socrates is one such person. Indeed, if we were to extend our goto interpretation by letting a new name, ‘$c$’, denote Socrates, then ‘$P(c)\wedge R(c,a)$’ would be true on this extended interpretation. Again, this should surely suffice to make ‘$\exists x(P(x)\wedge R(x,a))$’ true on the original goto interpretation.
In our goto interpretation, ‘$\forall x\exists yR(x,y)$’ should be false. After all, consider the last person born in the year 1999. We don’t know who that was, but if we were to extend our goto interpretation by letting a new name, ‘$d$’, denote that person, then we would not be able to find anyone else in the domain to denote with some further new name, perhaps ‘$e$’, in such a way that ‘$R(d,e)$’ would be true. Indeed, no matter whom we named with ‘$e$’, ‘$R(d,e)$’ would be false. This observation is surely sufficient to make ‘$\exists yR(d,y)$’ false in our extended interpretation, which in turn is surely sufficient to make ‘$\forall x\exists yR(x,y)$’ false on the original goto interpretation.
If you have understood these three examples, that’s what matters. It provides the basis for a formal definition of truth for quantified sentences.
Strictly speaking, though, we still need to give that definition. The result, sadly, is a bit ugly, and requires a few new definitions. Brace yourself!
Suppose that $\mathcal{A}$ is a formula, which usually contains at least one free occurrence of the variable $\U0001d4cd$, and possibly more than one. We will write this thus:
Suppose also that $\U0001d4b8$ is a name. Then we will write:
for the formula we obtain by replacing every free occurrence of $\U0001d4cd$ in $\mathcal{A}$ with $\U0001d4b8$. The resulting formula is called a substitution instance of $\forall \U0001d4cd\mathcal{A}$ and $\exists \U0001d4cd\mathcal{A}$. Also, $\U0001d4b8$ is called the instantiating name . So:
is a substitution instance of
with the instantiating name ‘$e$’ and instantiated variable ‘$y$’.
A brief aside: when substituting names for variables, we only allow the replacement of free variables. This is necessary since we allow formulas such as ‘$\exists x(\forall xF(x)\to G(x))$’, where different quantifiers bind the same variables. We consider only ‘$\forall xF(x)\to G(e)$’ as a substitution instance of this formula, and not ‘$F(e)\to G(e)$’, because the ‘$x$’ in ‘$F(x)$’ is not free—it is bound by ‘$\forall x$’. (You may want to review section 27.3 in this connection.)
Our interpretation will include a specification of which names correspond to which objects in the domain. Take any object in the domain, say, $d$, and a name $\U0001d4b8$ which is not already assigned by the interpretation. If our interpretation is $\mathbf{I}$, then we can consider the interpretation $\mathbf{I}[d/\U0001d4b8]$ which is just like $\mathbf{I}$ except it also assigns the object $d$ to the name $\U0001d4b8$. Then we can say that $d$ satisfies the formula $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ in the interpretation $\mathbf{I}$ if, and only if, $\mathcal{A}(\mathrm{\dots}\U0001d4b8\mathrm{\dots}\U0001d4b8\mathrm{\dots})$ is true in $\mathbf{I}[d/\U0001d4b8]$. (We assume that the name $\U0001d4b8$ does not already occur in $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$.) If $d$ satisfies $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ we also say that $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ is true of $d$.

‣
The interpretation $\mathbf{I}[d/\U0001d4b8]$ is just like the interpretation $\mathbf{I}$ except it also assigns the object $d$ to the name $\U0001d4b8$.

‣
An object $d$ satisfies $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ in interpretation $\mathbf{I}$ iff $\mathcal{A}(\mathrm{\dots}\U0001d4b8\mathrm{\dots}\U0001d4b8\mathrm{\dots})$ is true in $\mathbf{I}[d/\U0001d4b8]$ (where the name $\U0001d4b8$ does not already occur in $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$).
So, for instance, Socrates satisfies the formula $P(x)$ since $P(c)$ is true in the interpretation $\mathbf{I}[\text{Socrates}/c]$, i.e., the interpretation:
 domain:

all people born before 2000 ce
 $a$:

Aristotle
 $b$:

Beyoncé
 $c$:

Socrates
 $P(x)$:

blank _{x} is a philosopher
 $R(x,y)$:

blank _{x} was born before blank _{y}
Armed with this notation, the rough idea is as follows. The sentence $\forall \U0001d4cd\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ will be true in $\mathbf{I}$ iff, for any object $d$ in the domain, $\mathcal{A}(\mathrm{\dots}\U0001d4b8\mathrm{\dots}\U0001d4b8\mathrm{\dots})$ is true in $\mathbf{I}[d/\U0001d4b8]$, i.e., no matter what object (in the domain) we name by the new name $\U0001d4b8$. In other words, $\forall \U0001d4cd\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ is true iff every object in the domain satisfies $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$. Similarly, the sentence $\exists \U0001d4cd\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ will be true iff there is some object that satisifes $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$, i.e., $\mathcal{A}(\mathrm{\dots}\U0001d4b8\mathrm{\dots}\U0001d4b8\mathrm{\dots})$ is true in $\mathbf{I}[d/\U0001d4b8]$ for some object $d$ and a new name $\U0001d4b8$.

‣
$\forall \U0001d4cd\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ is true in an interpretation iff every object in the domain satisfies $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$.

‣
$\exists \U0001d4cd\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$ is true in an interpretation iff at least one object in the domain satisfies $\mathcal{A}(\mathrm{\dots}\U0001d4cd\mathrm{\dots}\U0001d4cd\mathrm{\dots})$.
To be clear: all this is doing is formalizing (very pedantically) the intuitive idea expressed above. The result is a bit ugly, and the final definition might look a bit opaque. Hopefully, though, the spirit of the idea is clear.
Practice exercises
A. Consider the following interpretation:

‣
The domain comprises only Corwin and Benedict

‣
‘$A(x)$’ is to be true of both Corwin and Benedict

‣
‘$B(x)$’ is to be true of Benedict only

‣
‘$N(x)$’ is to be true of no one

‣
‘$c$’ is to refer to Corwin
Determine whether each of the following sentences is true or false in that interpretation:

1.
$B(c)$

2.
$A(c)\leftrightarrow \neg N(c)$

3.
$N(c)\to (A(c)\vee B(c))$

4.
$\forall xA(x)$

5.
$\forall x\neg B(x)$

6.
$\exists x(A(x)\wedge B(x))$

7.
$\exists x(A(x)\to N(x))$

8.
$\forall x(N(x)\vee \neg N(x))$

9.
$\exists xB(x)\to \forall xA(x)$
B. Consider the following interpretation:

‣
The domain comprises only Lemmy, Courtney and Eddy

‣
‘$G(x)$’ is to be true of Lemmy, Courtney and Eddy.

‣
‘$H(x)$’ is to be true of and only of Courtney

‣
‘$M(x)$’ is to be true of and only of Lemmy and Eddy

‣
‘$c$’ is to refer to Courtney

‣
‘$e$’ is to refer to Eddy
Determine whether each of the following sentences is true or false in that interpretation:

1.
$H(c)$

2.
$H(e)$

3.
$M(c)\vee M(e)$

4.
$G(c)\vee \neg G(c)$

5.
$M(c)\to G(c)$

6.
$\exists xH(x)$

7.
$\forall xH(x)$

8.
$\exists x\neg M(x)$

9.
$\exists x(H(x)\wedge G(x))$

10.
$\exists x(M(x)\wedge G(x))$

11.
$\forall x(H(x)\vee M(x))$

12.
$\exists xH(x)\wedge \exists xM(x)$

13.
$\forall x(H(x)\leftrightarrow \neg M(x))$

14.
$\exists xG(x)\wedge \exists x\neg G(x)$

15.
$\forall x\exists y(G(x)\wedge H(y))$
C. Following the diagram conventions introduced at the end of chapter 30, consider the following interpretation:
Determine whether each of the following sentences is true or false in that interpretation:

1.
$\exists xR(x,x)$

2.
$\forall xR(x,x)$

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

4.
$\exists x\forall yR(y,x)$

5.
$\forall x\forall y\forall z((R(x,y)\wedge R(y,z))\to R(x,z))$

6.
$\forall x\forall y\forall z((R(x,y)\wedge R(x,z))\to R(y,z))$

7.
$\exists x\forall y\neg R(x,y)$

8.
$\forall x(\exists yR(x,y)\to \exists yR(y,x))$

9.
$\exists x\exists y(\neg x=y\wedge R(x,y)\wedge R(y,x))$

10.
$\exists x\forall y(R(x,y)\leftrightarrow x=y)$

11.
$\exists x\forall y(R(y,x)\leftrightarrow x=y)$

12.
$\exists x\exists y(\neg x=y\wedge R(x,y)\wedge \forall z(R(z,x)\leftrightarrow y=z))$