Chapter 31 Truth in FOL

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 $ℛ$ is an $n$-place predicate and ${𝒶}_1$, ${𝒶}_2$, …, ${𝒶}_n$ are names,

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 $𝒶$ and $𝒷$ are any names,

So in our go-to interpretation, ‘$a=b$’ is false, since Aristotle is distinct from Beyoncé.

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:

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.

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 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 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 if⁠f $\exists yL(𝒶,y)$ is true for every name $𝒶$ that we have included in our interpretation. Similarly, we might try to say that $\exists yL(𝒶,y)$ is true just in case $L(𝒶,𝒷)$ is true for some name $𝒷$ 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 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 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 xR(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 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 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 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 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 $𝒜$ is a formula, which usually contains at least one free occurrence of the variable $𝓍$, and possibly more than one. We will write this thus:

Suppose also that $𝒸$ is a name. Then we will write:

for the formula we obtain by replacing every free occurrence of $𝓍$ in $𝒜$ with $𝒸$. The resulting formula is called a substitution instance of $\forall 𝓍𝒜$ and $\exists 𝓍𝒜$. Also, $𝒸$ 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 $𝒸$ which is not already assigned by the interpretation. If our interpretation is $𝐈$, then we can consider the interpretation $𝐈[d/𝒸]$ which is just like $𝐈$ except it also assigns the object $d$ to the name $𝒸$. Then we can say that $d$ satisfies the formula $𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$ in the interpretation $𝐈$ if, and only if, $𝒜(\mathrm{\dots }𝒸\mathrm{\dots }𝒸\mathrm{\dots })$ is true in $𝐈[d/𝒸]$. (We assume that the name $𝒸$ does not already occur in $𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$.) If $d$ satisfies $𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$ we also say that $𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$ is true of $d$.

So, for instance, Socrates satisfies the formula $P(x)$ since $P(c)$ is true in the interpretation $𝐈[\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 𝓍𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$ will be true in $𝐈$ if⁠f, for any object $d$ in the domain, $𝒜(\mathrm{\dots }𝒸\mathrm{\dots }𝒸\mathrm{\dots })$ is true in $𝐈[d/𝒸]$, i.e., no matter what object (in the domain) we name by the new name $𝒸$. In other words, $\forall 𝓍𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$ is true if⁠f every object in the domain satisfies $𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$. Similarly, the sentence $\exists 𝓍𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$ will be true if⁠f there is some object that satisifes $𝒜(\mathrm{\dots }𝓍\mathrm{\dots }𝓍\mathrm{\dots })$, i.e., $𝒜(\mathrm{\dots }𝒸\mathrm{\dots }𝒸\mathrm{\dots })$ is true in $𝐈[d/𝒸]$ for some object $d$ and a new name $𝒸$.

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.