# 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. 1.

atomic sentences,

2. 2.

sentences whose main logical operator is a sentential connective,

3. 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)$:

blankx is a philosopher

$R(x,y)$:

blankx was born before blanky

This will be our go-to 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 go-to interpretation, this is true if⁠f Aristotle is a philosopher. Aristotle is a philosopher. So the sentence is true. Equally, ‘$P(b)$’ is false on our go-to interpretation.

Likewise, on this interpretation, ‘$R(a,b)$’ is true if⁠f 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 $\mathscr{R}$ is an $n$-place predicate and $\mathscr{a}_{1}$, $\mathscr{a}_{2}$, …, $\mathscr{a}_{n}$ are names,

The sentence $\mathscr{R}(\mathscr{a}_{1},\mathscr{a}_{2},\dots,\mathscr{a}_{n})$ is true in an interpretation if⁠f $\mathscr{R}$ is true of the objects named by $\mathscr{a}_{1}$, $\mathscr{a}_{2}$, …, $\mathscr{a}_{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 $\mathscr{a}$ and $\mathscr{b}$ are any names,

$\mathscr{a}=\mathscr{b}$ is true in an interpretation if⁠f $\mathscr{a}$ and $\mathscr{b}$ name the very same object in that interpretation.

So in our go-to 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 truth-functional connectives that were familiar from TFL. The rules governing these truth-functional connectives are exactly the same as they were when we considered TFL. Here they are:

• $\mathscr{A}\wedge\mathscr{B}$ is true in an interpretation if⁠f both $\mathscr{A}$ is true and $\mathscr{B}$ is true in that interpretation.

• $\mathscr{A}\vee\mathscr{B}$ is true in an interpretation if⁠f either $\mathscr{A}$ is true or $\mathscr{B}$ is true in that interpretation.

• $\neg\mathscr{A}$ is true in an interpretation if⁠f $\mathscr{A}$ is false in that interpretation.

• $\mathscr{A}\rightarrow\mathscr{B}$ is true in an interpretation if⁠f either $\mathscr{A}$ is false or $\mathscr{B}$ is true in that interpretation.

• $\mathscr{A}\leftrightarrow\mathscr{B}$ is true in an interpretation if⁠f $\mathscr{A}$ has the same truth value as $\mathscr{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 go-to 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 x\,F(x)$’ is true if⁠f ‘$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 y\,L(x,y)$’ is true just in case (speaking roughly) ‘$\exists y\,L(x,y)$’ is true of everything in the domain. But our interpretation does not directly specify what ‘$\exists y\,L(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 y\,L(x,y)$’ is to be true in an interpretation if⁠f $\exists y\,L(\mathscr{a},y)$ is true for every name $\mathscr{a}$ that we have included in our interpretation. Similarly, we might try to say that $\exists y\,L(\mathscr{a},y)$ is true just in case $L(\mathscr{a},\mathscr{b})$ is true for some name $\mathscr{b}$ that we have included in our interpretation.

Unfortunately, this is not right either. To see this, observe that our go-to 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 go-to interpretation, and we will then present the formal definition.

In our go-to interpretation, ‘$\exists x\,R(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 go-to 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 x\,R(b,x)$’ true on the original go-to interpretation.

In our go-to 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 go-to 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 go-to interpretation.

In our go-to interpretation, ‘$\forall x\exists y\,R(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 go-to 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 y\,R(d,y)$false in our extended interpretation, which in turn is surely sufficient to make ‘$\forall x\exists y\,R(x,y)$’ false on the original go-to 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 $\mathscr{A}$ is a formula, which usually contains at least one free occurrence of the variable $\mathscr{x}$, and possibly more than one. We will write this thus:

$\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$

Suppose also that $\mathscr{c}$ is a name. Then we will write:

$\mathscr{A}(\ldots\mathscr{c}\ldots\mathscr{c}\ldots)$

for the formula we obtain by replacing every free occurrence of $\mathscr{x}$ in $\mathscr{A}$ with $\mathscr{c}$. The resulting formula is called a substitution instance of $\forall\mathscr{x}\mathscr{A}$ and $\exists\mathscr{x}\mathscr{A}$. Also, $\mathscr{c}$ is called the instantiating name . So:

$\exists x(R(e,x)\leftrightarrow F(x))$

is a substitution instance of

$\forall y\exists x(R(y,x)\leftrightarrow F(x))$

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 x\,F(x)\rightarrow G(x))$’, where different quantifiers bind the same variables. We consider only ‘$\forall x\,F(x)\rightarrow G(e)$’ as a substitution instance of this formula, and not ‘$F(e)\rightarrow 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 $\mathscr{c}$ which is not already assigned by the interpretation. If our interpretation is $\mathbf{I}$, then we can consider the interpretation $\mathbf{I}[d/\mathscr{c}]$ which is just like $\mathbf{I}$ except it also assigns the object $d$ to the name $\mathscr{c}$. Then we can say that $d$ satisfies the formula $\mathscr{A}(\dots\mathscr{x}\dots\mathscr{x}\dots)$ in the interpretation $\mathbf{I}$ if, and only if, $\mathscr{A}(\dots\mathscr{c}\dots\mathscr{c}\dots)$ is true in $\mathbf{I}[d/\mathscr{c}]$. (We assume that the name $\mathscr{c}$ does not already occur in $\mathscr{A}(\dots\mathscr{x}\dots\mathscr{x}\dots)$.) If $d$ satisfies $\mathscr{A}(\dots\mathscr{x}\dots\mathscr{x}\dots)$ we also say that $\mathscr{A}(\dots\mathscr{x}\dots\mathscr{x}\dots)$ is true of $d$.

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

• An object $d$ satisfies $\mathscr{A}(\dots\mathscr{x}\dots\mathscr{x}\dots)$ in interpretation $\mathbf{I}$ if⁠f $\mathscr{A}(\dots\mathscr{c}\dots\mathscr{c}\dots)$ is true in $\mathbf{I}[d/\mathscr{c}]$ (where the name $\mathscr{c}$ does not already occur in $\mathscr{A}(\dots\mathscr{x}\dots\mathscr{x}\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)$:

blankx is a philosopher

$R(x,y)$:

blankx was born before blanky

Armed with this notation, the rough idea is as follows. The sentence $\forall\mathscr{x}\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$ will be true in $\mathbf{I}$ if⁠f, for any object $d$ in the domain, $\mathscr{A}(\ldots\mathscr{c}\ldots\mathscr{c}\ldots)$ is true in $\mathbf{I}[d/\mathscr{c}]$, i.e., no matter what object (in the domain) we name by the new name $\mathscr{c}$. In other words, $\forall\mathscr{x}\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$ is true if⁠f every object in the domain satisfies $\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$. Similarly, the sentence $\exists\mathscr{x}\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$ will be true if⁠f there is some object that satisifes $\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$, i.e., $\mathscr{A}(\ldots\mathscr{c}\ldots\mathscr{c}\ldots)$ is true in $\mathbf{I}[d/\mathscr{c}]$ for some object $d$ and a new name $\mathscr{c}$.

• $\forall\mathscr{x}\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$ is true in an interpretation if⁠f every object in the domain satisfies $\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$.

• $\exists\mathscr{x}\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$ is true in an interpretation if⁠f at least one object in the domain satisfies $\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$.

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. 1.

$B(c)$

2. 2.

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

3. 3.

$N(c)\rightarrow(A(c)\vee B(c))$

4. 4.

$\forall x\,A(x)$

5. 5.

$\forall x\neg B(x)$

6. 6.

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

7. 7.

$\exists x(A(x)\rightarrow N(x))$

8. 8.

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

9. 9.

$\exists x\,B(x)\rightarrow\forall x\,A(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. 1.

$H(c)$

2. 2.

$H(e)$

3. 3.

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

4. 4.

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

5. 5.

$M(c)\rightarrow G(c)$

6. 6.

$\exists x\,H(x)$

7. 7.

$\forall x\,H(x)$

8. 8.

$\exists x\,\neg M(x)$

9. 9.

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

10. 10.

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

11. 11.

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

12. 12.

$\exists x\,H(x)\wedge\exists x\,M(x)$

13. 13.

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

14. 14.

$\exists x\,G(x)\wedge\exists x\neg G(x)$

15. 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. 1.

$\exists x\,R(x,x)$

2. 2.

$\forall x\,R(x,x)$

3. 3.

$\exists x\forall y\,R(x,y)$

4. 4.

$\exists x\forall y\,R(y,x)$

5. 5.

$\forall x\forall y\forall z((R(x,y)\wedge R(y,z))\rightarrow R(x,z))$

6. 6.

$\forall x\forall y\forall z((R(x,y)\wedge R(x,z))\rightarrow R(y,z))$

7. 7.

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

8. 8.

$\forall x(\exists y\,R(x,y)\rightarrow\exists y\,R(y,x))$

9. 9.

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

10. 10.

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

11. 11.

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

12. 12.

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