$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 1.5: Sentences

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Among the formulas in the language $$\mathcal{L}$$, there are some in which we will be especially interested. These are the sentences of $$\mathcal{L}$$ - the formulas that can be either true or false in a given mathematical model.

Let us use an example to introduce a language that will be vitally important to us as we work through this book.

Definition 1.5.1. The language $$\mathcal{L}_{NT}$$ is $$\{0, S, +, \cdot, E, <\}$$, where 0 is a constant symbol, $$S$$ is a unary function symbol, $$+$$, $$\cdot$$, and $$E$$ are binary function symbols, and $$<$$ is a binary relation symbol. This will be referred to as the language of number theory.

Chaff: Although we are not fixing the meanings of these symbols yet, we probably ought to tell you that the standard interpretation of $$\mathcal{L}_{NT}$$ will use 0, $$+$$, $$\cdot$$, and $$<$$ in the way that you expect. The symbol $$S$$ will stand for the successor function that maps a number $$x$$ to the number $$x + 1$$, and $$E$$ will be used for exponentiation: $$E32$$ is supposed to be $$3^2$$.

Consider the following two formulas of $$\mathcal{L}_{NT}$$:

$\neg \left( \forall x \right) \left[ \left( y < x \right) \lor \left( y = x \right) \right].$

$\left( \forall x \right) \left( \forall y \right) \left[ \left( x < y \right) \lor \left( x = y \right) \lor \left( y < x \right) \right].$

(Did you notice that we have begun using an informal presentation of the formulas?)

The second formula should look familiar. It is nothing more than the familiar trichotomy law of $$<$$, and you would agree that the second formula is a true statement about the collection of natural numbers, where you are interpreting $$<$$ in the usual way.

The first formula above is different. It "says" that not every $$x$$ is greater than or equal to $$y$$. The truth of that statement is indeterminate: It depends on what natural number $$y$$ represents. The formula might be true, or it might be false - it all depends on the value of $$y$$. So our goal in this section is to separate the formulas of $$\mathcal{L}$$ into one of two classes: the sentences (like the second example above) and the nonsentences. To begin this task, we must talk about free variables.

Free variables are the variables upon which the truth value of a formula may depend. The variable $$y$$ is free in the first formula above. To draw an analogy from calculus, if we look at

$\int_1^x \frac{1}{t} dt,$

the variable $$x$$ is free in this expression, as the value of the integral depends on the value of $$x$$. The variable $$t$$ is not free, and in fact it doesn't make any sense to decide on a value for $$t$$. The same distinction holds between free and nonfree variables in an $$\mathcal{L}$$-formula. Let us try to make things a little more precise.

Definition 1.5.2. Suppose that $$v$$ is a variable and $$\phi$$ is a formula. We will say that $$v$$ is free in $$\phi$$ if

1. $$\phi$$ is atomic and $$v$$ occurs in (is a symbol in) $$\phi$$, or
2. $$\phi : \equiv \left( \neg \alpha \right)$$ and $$v$$ is free in $$\alpha$$, or
3. $$\phi : \equiv \left( \alpha \lor \beta \right)$$ and $$v$$ is free in at least on of $$\alpha$$ or $$\beta$$, or
4. $$\phi : \equiv \left( \forall u \right) \left( \alpha \right)$$ and $$v$$ is not $$u$$ and $$v$$ is free in $$\alpha$$.

Thus, if we look at the formula

$\forall v_2 \neg \left( \forall v_3 \right) \left( v_1 = S \left( v_2 \right) \lor v_3 = v_2 \right),$

the variable $$v_1$$ is free whereas the variables $$v_2$$ and $$v_3$$ are not free. A slightly more complicated example is

$\left( \forall v_1 \forall v_2 \left( v_1 + v_2 = 0 \right) \right) \lor v_1 = S \left( 0 \right).$

In this formula, $$v_1$$ is free whereas $$v_2$$ is not free. Especially when a formula is presented informally, you must be careful about the scope of the quantifiers and the placement of parentheses.

We will have occasion to use the informal notation $$\forall x \phi \left( x \right)$$. This will mean that $$\phi$$ is a formula and $$x$$ is among the free variables of $$\phi$$. If we then write $$\phi \left( t \right)$$, where $$t$$ is an $$\mathcal{L}$$-term, that will denote the formula obtained by taking $$\phi$$ and replacing each occurrence of the variable $$x$$ with the term $$t$$. This will all be defined more formally and more precisely in Definition 1.8.2.

Definition 1.5.3. A sentence in a language $$\mathcal{L}$$ is a formula of $$\mathcal{L}$$ that contains no free variables.

For example, if a language contained the constant symbols 0, 1, and 2 and the binary function symbol $$+$$, then the following are sentences: $$1 + 1 = 2$$ and $$\left( \forall x \right) \left( x + 1 = x \right)$$. You are probably convinced that the first of these is true and the second of these is false. In the next two sections we will see that you might be correct. But then again, you might not be.

## Exercises

1. For each of the following, find the free variables, if any, and decide if the given formula is a sentence. The language includes a binary function symbol $$+$$, a binary relation symbol $$<$$, and constant symbols 0 and 2.
(a) $$\left( \forall x \right) \left( \forall y \right) \left( x + y = 2 \right)$$
(b) $$\left( x + y < x \right) \lor \left( \forall z \right) \left( z < 0 \right)$$
(c) $$\left( \left( \forall y \right) \left( y < x \right) \right) \lor \left( \left( \forall x \right) \left( x < y \right) \right)$$
2. Explain precisely, using the definition of a free variable, how you know that the variable $$v_2$$ is free in the formula
$\left( \forall v_1 \right) \left( \neg \left( \forall v_5 \right) \left( v_2 = v_1 + v_5 \right) \right).$
3. In mathematics, we often see statements such as $$\sin^2 x + \cos^2 x = 1$$. Notice that this is not a sentence, as the variable $$x$$ is free. But we all agree that this statement is true, given the usual interpretations of the symbols. How can we square this with the claim that sentences are the formulas that can be either true or false?
4. If we look at the first of our example formulas in this section,
$\neg \left( \forall x \right) \left[ \left( y < x \right) \lor \left( y = x \right) \right],$
and we interpret the variables as ranging over the natural numbers, you will probably agree that the formula is false if $$y$$ represents the natural number 0 and true if $$y$$ represents any other number. (If you aren't happy with 0 being a natural number, then use 1.) On the other hand, if we interpret the variables as ranging over the integers, what can we say about the truth or falsehood of this formula? Can you think of an interpretation for the symbols that would make sense if wy try to apply this formula to the collection of complex numbers?
5. A variable may occur several times in a given formula. For example, the variable $$v_1$$ occurs four times in the formula
$\left( \forall v_1 \right) \left[ \left( v_1 = v_3 \right) \lor \left( v_1 = S v_2 \right) \lor \left( 0 + v_{17} < v_1 - S0 \right) \right].$
What should it mean for an occurrence of a variable to be free? Write a definition that begins: The $$n$$th occurrence of a variable $$v$$ in a formula $$\phi$$ is said to be free if .... An occurrence of $$v$$ in $$\phi$$ that is not free is said to be bound. Give an example of a formula in a suitable language that contains both free and bound occurrences of a variable $$v$$.
6. Look at the formula
$\left[ \left( \forall y \right) \left( x = y \right) \right] \lor \left[ \left( \forall x \right) \left( x < 0 \right) \right].$
If we denote this formula by $$\phi \left( x \right)$$ and $$t$$ is the term $$S0$$, find $$\phi \left( t \right)$$. [Suggestion: The trick here is to see that there is a bit of a lie in the discussion of $$\phi \left( t \right)$$ in the text. Having completed Exercise 5, we can now say that we only replace the free occurrence of the variable $$x$$ when we move from $$\phi \left( x \right)$$ to $$\phi \left( t \right)$$.]