Chapter 27 Sentences of FOL

There are six kinds of symbols in FOL:

1. 1.
   ​

   Predicates: $A$, $B$, $C$, …, $Z$, or with subscripts, as needed: $A_1$, $B_1$, $Z_1$, $A_2$, $A_{25}$, $J_{375}$, …

2. 2.
   ​

   Names: $a$, $b$, $c$, …, $r$, or with subscripts, as needed: $a_1$, $b_{224}$, $h_7$, $m_{32}$, …

3. 3.
   ​

   Variables: $s$, $t$, $u$, $v$, $w$, $x$, $y$, $z$, or with subscripts, as needed: $x_1$, $y_1$, $z_1$, $x_2$, …

4. 4.
   ​

   Connectives: $\neg$, $\wedge$, $\vee$, $\to$, $\leftrightarrow$

5. 5.
   ​

   Brackets: ( , )

6. 6.
   ​

   Quantifiers: $\forall$, $\exists$

We define an expression of FOL as any string of symbols of FOL. Take any of the symbols of FOL and write them down, in any order, and you have an expression.

In chapter 6, we went straight from the statement of the vocabulary of TFL to the definition of a sentence of TFL. In FOL, we will have to go via an intermediary stage: via the notion of a formula . The intuitive idea is that a formula is any sentence, or anything which can be turned into a sentence by adding quantifiers out front. But this intuitive idea will take some time to unpack.

We start by defining the notion of a term.

So, here are some terms:

Next we need to define atomic formulas.

Note that we consider sentence letters also formulas of FOL, so every sentence of TFL is also a formula of FOL.

The use of script letters here follows the conventions laid down in chapter 8. So, ‘$ℛ$’ is not itself a predicate of FOL. Rather, it is a symbol of our metalanguage (augmented English) that we use to talk about any predicate of FOL. Similarly, ‘${𝓉}_1$’ is not a term of FOL, but a symbol of the metalanguage that we can use to talk about any term of FOL. So, where ‘$F$’ is a one-place predicate, ‘$G$’ is a three-place predicate, and ‘$S$’ is a six-place predicate, here are some atomic formulas:

Once we know what atomic formulas are, we can offer recursion clauses to define arbitrary formulas. The first few clauses are exactly analogous to those in the definition of ‘sentence of TFL’.

So, assuming again that ‘$F$’ is a one-place predicate, ‘$G$’ is a three-place predicate and ‘$S$’ is a six place-predicate, here are some formulas you can build this way:

We can now give a formal definition of scope, which incorporates the definition of the scope of a quantifier. Here we follow the case of TFL, though we note that a logical operator can be either a connective or a quantifier:

So we can graphically illustrate the scope of the quantifiers in the preceding example thus:

Recall that we are largely concerned in logic with assertoric sentences: sentences that can be either true or false. Many formulas are not sentences. Consider the following symbolization key:

domain:

people

$L(x,y)$:

blank_x loves blank_y

$b$:

Boris

Consider the atomic formula ‘$L(z,z)$’. All atomic formulas are formulas, so ‘$L(z,z)$’ is a formula, but can it be true or false? You might think that it will be true just in case the person named by ‘$z$’ loves themself, in the same way that ‘$L(b,b)$’ is true just in case Boris (the person named by ‘$b$’) loves himself. However, ‘$z$’ is a variable, and does not name anyone or any thing.

Of course, if we put an existential quantifier out front, obtaining ‘$\exists zL(z,z)$’, then this would be true if⁠f someone loves themselves. Equally, if we wrote ‘$\forall zL(z,z)$’, this would be true if⁠f everyone loves themselves. The point is that we need a quantifier to tell us how to deal with a variable.

Let’s make this idea precise.

For example, consider the formula

The scope of the universal quantifier ‘$\forall x$’ is ‘$\forall x(E(x)\vee D(y))$’, so the first ‘$x$’ is bound by the universal quantifier. However, the second and third occurrence of ‘$x$’ are free. Equally, the ‘$y$’ is free. The scope of the existential quantifier ‘$\exists z$’ is ‘$\exists z(E(x)\to L(z,x))$’, so ‘$z$’ is bound.

Formulas that do not have free variables, i.e., every variable is bound, are called sentences . Only sentences can be true or false.

Note that in the formation rules given in section 27.2, specifically in the clauses for $\forall$ and $\exists$, we did not require that the variable $𝓍$ in $\forall 𝓍𝒜$ and $\exists 𝓍𝒜$ does not already occur as a bound variable in $𝒜$. So we allow, for instance, ‘$\exists x(\forall xF(x)\to G(x))$’ as a sentence. We won’t be meeting such special cases often, since we can always rename bound variables to obtain an equivalent sentence that avoids such weirdness; in this case, e.g., ‘$\exists x(\forall yF(y)\to G(x))$’. But since it is allowed to happen, we should clarify which quantifiers bind which variables: An occurrence of a bound variable is always bound by the quantifier with the same matching variable that is closest to it. By “closest” we mean: it is the main logical operator of the smallest subformula into the scope of which the occurrence of the variable falls. So in our previous example, ‘$\forall x$’ binds the occurrence of $x$ in ‘$F(x)$’, since it is the main logical operator of ‘$\forall xF(x)$’. The ‘$\forall x$’ does not bind the ‘$x$’ in ‘$G(x)$’, however. The ‘$\exists x$’ does not bind the ‘$x$’ in ‘$F(x)$’, but it does bind the ‘$x$’ in ‘$G(x)$’.

The rules also do not require that the bound variable $𝓍$ actually occurs free in $𝒜$ (or even at all). So our rules also allow ‘$\exists xF(a)$’ and ‘$\exists x\forall xG(x)$’ as formulas. In each case, the ‘$\exists x$’ does not bind ‘$x$’, because ‘$x$’ does not occur free in ‘$F(a)$’ or in ‘$\forall xG(x)$’. In the former case, ‘$x$’ does not occur at all; in the latter, it is already bound by ‘$\forall x$’. This is called vacuous quantification . It rarely appears in practice, and isn’t harmful. The two sentences are equivalent to the sentences without the ‘$\exists x$’, i.e., to ‘$F(a)$’ and ‘$\forall xG(x)$’.

We will adopt the same notational conventions governing brackets that we did for TFL (see chapters 6 and 11.3.) First, we may omit the outermost brackets of a formula. Second, we may use square brackets, ‘[’ and ‘]’, in place of brackets to increase the readability of formulas.

Sentences of FOL used in our examples can become quite cumbersome, and so we also introduce a convention to deal with conjunctions and disjunctions of more than two sentences. We stipulate that $A_1\wedge A_2\wedge \mathrm{\cdots }\wedge A_n$ and $A_1\vee A_2\vee \mathrm{\cdots }\vee A_n$ are to be interpreted as, respectively:

• ​

  $(\mathrm{\dots }(A_1\wedge A_2)\wedge \mathrm{\cdots }\wedge A_n)$

• ​

  $(\mathrm{\dots }(A_1\vee A_2)\vee \mathrm{\cdots }\vee A_n)$

In practice, this just means that you are allowed to leave out parentheses in long conjunctions and disjunctions. But remember that (unless they are the outermost parentheses of the sentence) you must still enclose the entire conjunction or disjunction in parentheses. Also, you cannot mix conjunctions and disjunctions with each other or with other connectives. So the following are still not allowed, and would be ambiguous if they were:

• ​

  $A\vee B\wedge C\wedge D$

• ​

  $B\vee C\to D$

Above, we said that an $n$-place predicate followed by $n$ terms is an atomic formula. But there is a small issue with this definition: the symbols we use for predicates do not, themselves, indicate how many places the predicate has. Indeed, in some places in this book, we have used the letter ‘$G$’ as a one-place predicate; in other places we have used it as a three-place predicate. So, unless we state explicitly whether we want to use ‘$G$’ as a one-place predicate or as a three place predicate, it is indeterminate whether ‘$G(a)$’ is an atomic formula or not.

There is an easy way to avoid this, which many books adopt. Instead of saying that our predicates are just capital letters (with numerical subscripts as necessary), we could say that they are capital letters with numerical superscripts (and with numerical subscripts as necessary). The purpose of the superscript would be to say explicitly how many places the predicate has. On this approach, ‘$G^1$’ would be a one-place predicate, and ‘$G^3$’ would be an (entirely different) three places predicate. They would need to have different entries in any symbolisation key. And ‘$G^1(a)$’ would be an atomic formula, whereas ‘$G^3(a)$’ would not; likewise ‘$G^3(a,b,c)$’ would be an atomic formula, and ‘$G^1(a,b,c)$’ would not.

So, we could add superscripts to all our predicates. This would have the advantage of making certain things completely explicit. However, it would have the disadvantage of making our formulas much harder to read; the superscripts would distract the eye. So, we will not bother to make this change. Our predicates will remain without superscripts. (And, in practice, any book which includes superscripts almost immediately stops including them!)

However, this leaves open a possibility of ambiguity. So, when any ambiguity could arise—in practice, very rarely—you should say, explicitly, how many places your predicate(s) have.