2.5.8: Truth in a Structure

It is at last time to tie together the syntax and the semantics. We have some formal rules about what constitutes a language, and we can identify the terms, formulas, and sentences of a language. We can also identify $\mathcal{L}$-structures for a given language $\mathcal{L}$. In this section we will decide what it means to say that an $\mathcal{L}$-formula $\phi$ is true in an $\mathcal{L}$-structure $\mathfrak{A}$.

To begin the process of tying together the symbols with the structures, we will introduce assignment functions. These assignment functions will formalize what it means to interpret a term or a formula in a structure.

Definition 1.7.1. If $\mathfrak{A}$ is an $\mathcal{L}$-structure, a variable assignment function into $\mathfrak{A}$ is a function $s$ that assigns to each variable an element of the universe $A$. So a variable assignment function into $\mathfrak{A}$ is any function with domain $Vars$ and codomain $A$.

Variable assignment functions need not be injective or bijective. For example, if we work with $\mathcal{L}_{NT}$ and the standard structure $\mathfrak{N}$, then the function $s$ defined by $s \left( v_i \right) = i$ is a variable assignment function, as is the function $s'$ defined by

$$s' \left( v_i \right) = \: \text{the smallest prime number that does not divide} \: i.$$

We will have occasion to want to fix the value of the assignment function $s$ for certain variables.

Definition 1.7.2. If $s$ is a variable assignment function into $\mathfrak{A}$ and $x$ is a variable and $a \in A$, then $s \left[ x | a \right]$ is the variable assignment function into $\mathfrak{A}$ defined as follows:

$$s \left[ x | a \right] = \begin{cases} s \left( v \right) \: \: \: \text{if} \: v \: \text{is a variable other than} \: x \\ a \: \: \: \: \: \: \: \: \: \: \: \text{if} \: v \: \text{is the variable} \: x \end{cases}$$

We call the function $s \left[ x | a \right]$ an $x$-modification of the assignment function $s$.

So an $x$-modification of $s$ is just like $s$, except that the variable $x$ is assigned to a particular element of the universe.

What we will do next is extend a variable assignment function $s$ to a term assignment function, $\bar{s}$. This function will assign an element of the universe to each term of the language $\mathcal{L}$.

Definition 1.7.3. Suppose that $\mathfrak{A}$ is an $\mathcal{L}$-structure and $s$ is a variable assignment function into $\mathfrak{A}$. The function $\bar{s}$, called the term assignment function generated by $s$, is the function with domain consisting of the set of $\mathcal{L}$-terms and codomain $A$ defined recursively as follows:

1. If $t$ is a variable, $\bar{s} \left( t \right) = s \left( t \right)$.
2. If $t$ is a constant symbol $c$, then $\bar{s} \left( t \right) = c^\mathfrak{A}$.
3. If $t : \equiv f t_1 t_2 \ldots t_n$, then $\bar{s} \left( t \right) = f^\mathfrak{A} \left( \bar{s} \left( t_1 \right), \bar{s} \left( t_2 \right), \ldots, \bar{s} \left( t_n \right) \right)$.

Although we will be primarily interested in truth of sentences, we will first describe truth (or satisfaction) for arbitrary formulas, relative to an assignment function.

Definition 1.7.4. Suppose that $\mathfrak{A}$ is an $\mathcal{L}$-structure, $\phi$ is an $\mathcal{L}$-formula, and $s : Vars \rightarrow A$ is an assignment function. We will say that $\mathfrak{A}$ satisfies $\phi$ with assignment $s$, and write $\mathfrak{A} \models \phi \left[ s \right]$, in the following circumstances:

1. If $\phi : \equiv t_1 t_2$ and $\bar{s} \left( t_1 \right)$ is the same element of the universe $A$ as $\bar{s} \left( t_2 \right)$, or
2. If $\phi : \equiv R t_1 t_2 \ldots t_n$ and $\left( \bar{s} \left( t_1 \right), \bar{s} \left( t_2 \right), \ldots, \bar{s} \left( t_n \right) \right) \in R^\mathfrak{A}$, or
3. If $\phi : \equiv \left( \neg \alpha \right)$ and $\mathfrak{A} \not\models \alpha \left[ s \right]$, (where $\not\models$ means "does not satisfy"), or
4. If $\phi : \equiv \left( \alpha \lor \beta \right)$ and $\mathfrak{A} \models \alpha \left[ s \right]$, or $\mathfrak{A} \models \beta \left[ s \right]$ (or both), or
5. If $\phi : \equiv \left( \forall x \right) \left( \alpha \right)$ and, for each element $a$ of $A$, $\mathfrak{A} \models \alpha \left[ s \left( x | a \right) \right]$.

If $\Gamma$ is a set of $\mathcal{L}$-formulas, we say that $\mathfrak{A}$ satisfies $\Gamma$ with assignment $s$, and write $\mathfrak{A} \models \Gamma \left[ s \right]$ if for each $\gamma \in \Gamma$, $\mathfrak{A} \models \gamma \left[ s \right]$.

Chaff: Notice that the symbol $\models$ is not part of the language $\mathcal{L}$. Rather, $\models$ is a metalinguistic symbol that we use to talk about formulas in the language and structures for the language.

Chaff: Also notice that we have at last tied together the syntax and semantics of our language! The definition above is the place where we formally put the meanings on the symbols that we will use, so that $\lor$ means "or" and $\forall$ means "for all".

Example 1.7.5. Let us work with the empty language, so $\mathcal{L}$ has no constant symbols, no function symbols, and no relation symbols. So an $\mathcal{L}$-structure is simply a nonempty set, and let us consider the $\mathcal{L}$-structure $\mathfrak{A}$, where $A = \{ \text{Humphrey, Ingrid}\}$. Consider the formula $x = y$ and the assignment function $s$, where $s \left( x \right)$ is Humphrey and $s \left( y \right)$ is also Humphrey. If we ask whether $\mathfrak{A} \models x = y \left[ s \right]$, we have to check whether $bar{s} \left( x \right)$ is the same element of $A$ as $\bar{s} \left( y \right)$. Since the two objects are identical, the formula is true.

To emphasize this, the formula $x = y$ can be true in some universes with some assignment functions. Although the variables $x$ and $y$ are distinct, the truth or falsity of the formula depends not on the variables (which are not equal) but rather, on which elements of the structure the variables denote, the values of the variables (which are equal for this example). Of course, there are other assignment functions and other structures that make our formula false. We are sure you can think of some.

To talk about the truth or falsity of a sentence in a structure, we will take our definition of satisfaction relative to an assignment function and prove that for sentences, the choice of the assignment function is inconsequential. Then we will say that a sentence $\sigma$ is true in a structure $\mathfrak{A}$ if and only if $\mathfrak{A} \models \sigma \left[ s \right]$ for any (and therefore all) variable assignment functions $s$.

Chaff: The next couple of proofs are proofs by induction on the complexity of terms or formulas. You may want to reread the proof of Theorem 1.4.2 if you find these difficult.

Lemma 1.7.6. Suppose that $s_1$ and $s_2$ are variable assignment functions into a structure $\mathfrak{A}$ such that $s_1 \left( v \right) = s_2 \left( v \right)$ for every variable $v$ in the term $t$. Then $\bar{s_1} \left( t \right) = \bar{s_2} \left( t \right)$.

Proof. We use induction on the complexity of the term $t$. If $t$ is either a variable or a constant symbol, the result is immediate. If $t : \equiv f t_1 t_2 \ldots t_n$, then as $\bar{s_1} \left( t_i \right) = \bar{s_2} \left( t_i \right)$ for $1 \leq i \leq n$ by the inductive hypothesis, the definition of $\bar{s_1} \left( t \right)$ and the definition of $\bar{s_2} \left( t \right)$ are identical, and thus $\bar{s_1} \left( t \right) = \bar{s_2} \left( t \right)$.

Proposition 1.7.7. Suppose that $s_1$ and $s_2$ are variable assignment functions into a structure $\mathfrak{A}$ such that $s_1 \left( v \right) = s_2 \left( v \right)$ for every free variable $v$ in the formula $\phi$. Then $mathfrak{A} \models \phi \left[ s_1 \right]$ if and only if $\mathfrak{A} \models \phi \left[ s_2 \right]$.

Proof. We use induction on the complexity of $\phi$. If $\phi : \equiv = t_1 t_2$, then the free variables of $\phi$ are exactly the variables that occur in $\phi$. Thus Lemma 1.7.6 tells us that $\bar{s_1} \left( t_1 \right) = \bar{s_2} \left( t_1 \right)$ and $\bar{s_1} \left( t_2 \right) = \bar{s_2} \left( t_2 \right)$, meaning that they are the same element of the universe $A$, so $\mathfrak{A} \models \left( = t_1 t_2 \right) \left[ s_1 \right]$ if and only if $\mathfrak{A} \models \left( = t_1 t_2 \right) \left[ s_2 \right]$, as needed.

The other base case, if $\phi : \equiv R t_1 t_2 \ldots t_n$, is similar and is left as part of Exercise 6.

To begin the first inductive clause, if $\phi : \equiv \neg \alpha$, notice that the free variables of $\phi$ are exactly the free variables of $\alpha$, so $s_1$ and $s_2$ agree on the free variables of $\alpha$. By the inductive hypothesis, $\mathfrak{A} \models \alpha \left[ s_1 \right]$ if and only if $\mathfrak{A} \models \alpha \left[ s_2 \right]$, and thus (by the definition of satisfaction), $\mathfrak{A} \models \phi \left[ s_1 \right]$ if and only if $\mathfrak{A} \models \phi \left[ s_2 \right]$. The second inductive clause, if $\phi : \equiv \alpha \lor \beta$, is another part of Exercise 6.

If $\phi : \equiv \left( \forall x \right) \left( \alpha \right)$, we first note that the only variable that might be free in $\alpha$ that is not free in $\phi$ is $x$. Thus, if $a \in A$, the assignment functions $s_1 \left[ x | a \right]$ and $s_2 \left[ x | a \right]$ agree on all of the free variables of $\alpha$. Therefore, by inductive hypothesis, for each $a \in A$, $\mathfrak{A} \ = \alpha \left[ s_1 \left[ x | a \right] \right]$ if and only if $\mathfrak{A} \models \alpha \left[ s_2 \left[ x | a \right] \right]$. So, by Definition 1.7.4, $\mathfrak{A} \models \phi \left[ s_1 \right]$ if and only if \(\mathfrak{A} \models \phi \left[ s_2 \right]|). This finishes the last inductive clause, and our proof.

Corollary 1.7.8 If $\sigma$ is a sentence in the language $\mathcal{L}$ and $\mathfrak{A}$ is an $\mathcal{L}$-structure, either $\mathfrak{A} \models \sigma \left[ s \right]$ for all assignment functions $s$, or $\mathfrak{A} \models \sigma \left[ s \right]$ for no assignment function $s$.

Proof. There are no free variables in $\sigma$, so if $s_1$ and $s_2$ are two assignment functions, they agree on all of the free variables of $\sigma$, there just aren't all that many of them. So by Proposition 1.7.7, $\mathfrak{A} \models \sigma \left[ s_1 \right]$ if and only if $\mathfrak{A} \models \sigma \left[ s_2 \right]$, as needed.

Definition 1.7.9. If $\phi$ is a formula in the language $\mathcal{L}$ and $\mathfrak{A}$ is an $\mathcal{L}$-structure, we say that $\mathfrak{A}$ is a model of $\phi$, and write $\mathfrak{A} \models \phi$, if and only if $\mathfrak{A} \models \phi \left[ s \right]$ for every assignment function $s$. If $\Phi$ is a set of $\mathcal{L}$-formulas, we will say that $\mathfrak{A}$ models $\Phi$, and write $\mathfrak{A} \models \Phi$, if and only if $\mathfrak{A} \models \phi$ for each $\phi \in \Phi$.

Notice that if $\sigma$ is a sentence, then $\mathfrak{A} \models \sigma$ if and only if $\mathfrak{A} \models \sigma \left[ s \right]$ for any assignment function $s$. In this case we will say that the sentence $\sigma$ is true in $\mathfrak{A}$.

Example 1.7.10. Let's work in $\mathcal{L}_{NT}$, and let

$$\mathfrak{N} = \left( \mathbb{N}, 0, S, +, \cdot, E, < \right)$$

be the standard structure. Let $s$ be the variable assignment function that assigns $v_i$ to the number $2i$. Now let the formula $\phi \left( v_1 \right)$ be $v_1 + v_2 = SSSS0$.

To show that $\mathfrak{N} \models \phi \left[ s \right]$, notice that

$$\begin{align} \bar{s} \left( v_1 + v_1 \right) \: &\text{is} \: +^\mathfrak{N} \left( \bar{s} \left( v_1 \right), \bar{s} \left( v_1 \right) \right) \\ &\text{is} \: +^\mathfrak{N} \left( 2, 2 \right) \\ &\text{is} \: 4 \end{align}$$

while

$$\begin{align} \bar{s} \left( SSSS0 \right) \: &\text{is} \: S^\mathfrak{N} \left( S^\mathfrak{N} \left( S^\mathfrak{N} \left( S^\mathfrak{N} \left( 0^\mathfrak{N} \right) \right) \right) \right) \\ &\text{is} \: 4 \end{align}$$

Now, in the same setting, consider $\sigma$, the sentence

$$\left( \forall v_1 \right) \neg \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_1 \right),$$

which states that everything is even. [That is hard to see unless you know to look for that $\neg \left( \forall v_2 \right) \neg$ and to read it as $\left( \exists v_2 \right)$. See the last couple of paragraphs of this section.] You know that $\sigma$ is false in the standard structure, but to show how the formal argument goes, let $s$ be any variable assignment function and notice that

$$\begin{align} \mathfrak{N} \models \sigma \left[ s \right] \: &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \mathfrak{N} \models \neg \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_2 \right) s \left[ v_1 | a \right] \\ &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \mathfrak{N} \not\models \left( \forall v_2 \right) \neg \left( v_1 = v_2 + v_2 \right) s \left[ v_1 | a \right] \\ &\text{iff} \: \text{For every } a \in \mathbb{N}, \: \text{there is a } b \in \mathbb{N}, \: \mathfrak{N} \models v_1 = v_2 + v_2 \: s \left[ v_1 | a \right] \left[ v_2 | b \right]. \end{align}$$

Now, if we consider the case when $a$ is the number 3, it is perfectly clear that there is no such $b$, so we have shown $\mathfrak{N} \not\models \sigma \left[ s \right]$. Then, by Definition 1.7.9, we see that the sentence $\sigma$ is false in the standard structure. As you well knew.

When you were introduced to symbolic logic, you were probably told that there were five connectives. In the mathematics that you have learned recently, you have been using two quantifiers. We hope you have noticed that we have not used all of those symbols in this book, but is now time to make those symbols available. Rather than adding the symbols to our language, however, we will introduce them as abbreviations. This will help us to keep our proofs slightly less complex (as our inductive proofs will have fewer cases) but will still allow us to use the more familiar symbols, at least as shorthand.

Thus, let us agree to use the following abbreviations in constructing $\mathcal{L}$-formulas: We will write $\left( \alpha \land \beta \right)$ instead of $\left( \neg \left( \left( \neg \alpha \right) \lor \left( \neg \beta \right) \right) \right)$, $\left( \alpha \rightarrow \beta \right)$ instead of $\left( \left( \neg \alpha \right) \lor \beta \right)$, and $\left( \alpha \leftrightarrow \beta \right)$ instead of $\left( \left( \alpha \rightarrow \beta \right) \land \left( \beta \rightarrow \alpha \right) \right)$. We will also introduce our missing existential quantifier as an abbreviation, writing $\left( \exists x \right) \left( \alpha \right)$ instead of $\left( \neg \left( \forall x \right) \left( \neg \alpha \right) \right)$. It is an easy exercise to check that the introduced connectives $\land$, $\rightarrow$, and $\leftrightarrow$ behave as you would expect them to. Thus $\mathfrak{A} \models \left( \alpha \land \beta \right) \left[ s \right]$ if and only if both $\mathfrak{A} \models \alpha \left[ s \right]$ and $\mathfrak{A} \models \beta \left[ s \right]$. The existential quantifier is only slightly more difficult. See Exercise 7.

Exercises

1. We suggested after Definition 1.5.3 that the truth or falsity of the sentences $1 + 1 = 2$ and $\left( \forall x \right) \left( x + 1 = x \right)$ might not be automatic. Find a structure for the language discussed there that makes the sentence $1 + 1 = 2$ true. Find another structure where $1 + 1 = 2$ is false. Prove your assertions. Then show that you can find a structure where $\left( \forall x \right) \left( x + 1 = x \right)$ is true, and another structure where it is false.
2. Let the language $\mathcal{L}$ be $\{ S, C \}$, where $S$ is a unary function symbol and $<$ is a binary relation symbol. Let $\phi$ be the formula $\left( \forall x \right) \left( \exists y \right) \left( Sx < y \right)$.
   (a) Find an $\mathcal{L}$-structure $\mathfrak{A}$ such that $\mathfrak{A} \models \phi$.
   (b) Find an $\mathcal{L}$-structure $\mathfrak{B}$ such that $\mathfrak{B} \models \left( \neg \phi \right)$.
   (c) Prove that your answer to part (a) or part (b) is correct.
   (d) Write an $\mathcal{L}$-sentence that is true in a structure $\mathfrak{A}$ if and only if the universe $A$ of $\mathfrak{A}$ consists of exactly two elements.
3. Consider the language and structure of Example 1.6.4. Write two nontrivial sentences in the language, one of which is true in the structure and one of which (not the denial of the first) is false in the structure. Justify your assertions.
4. Consider the sentence $\sigma$: $\left( \forall x \right) \left( \exists y \right) \left[ x < y \rightarrow x + 1 \neg y \right]$. Find two structures for a suitable language, one of which makes $\sigma$ true, and the other of which makes $\sigma$ false.
5. One more bit of shorthand. Assume that the language $\mathcal{L}$ contains the binary relation symbol $\in$, which you are intending to use to mean the elementhood relation (so $p \in q$ will mean that $p$ is an element of $q$). Often, it is the case that you want to claim that $\phi \left( x \right)$ is true for every element of a set $b$. Of course, to do this you could write
   $$\left( \forall x \right) \left[ \left( x \in b \right) \rightarrow \phi \left( x \right) \right].$$
   We will abbreviate this formula as
   $$\left( \forall x \in b \right) \left( \phi \left( x \right) \right).$$
   Similarly, $\left( \exists x \in b \right) \left( \phi \left( x \right) \right)$ will be an abbreviation for the formula $\left( \exists x \right) \left[ \left( x \in b \right) \land \phi \left( x \right) \right]$. Notice that this formula has a conjunction where the previous formula had an implication!. We do that just to see if you are paying attention. (Well, if you think about what the abbreviations are supposed to mean, you'll see that the change is necessary. We'll have to do something else just to see if you're paying attention.)
   Now suppose that $\mathfrak{A}$ is a structure for the language of set theory. So $\mathcal{L}$ has only this one binary relation symbol, $\in$, which is interpreted as the elementhood relation. Suppose, in addition, that
   $$A = \{ u, v, w, \{ u \}, \{ u, v \}, \{ u, v, w \} \}.$$
   In particular, notice that there is no element $x$ of $A$ such that $x \in x$. Consider the sentence
   $$\left( \forall y \in y \right) \left( \exists x \in x \right) \left( x = y \right).$$
   Is this sentence true or false in $\mathfrak{A}$?
6. Fill in the details to complete the proof of Proposition 1.7.7.
7. Show that $\mathfrak{A} \models \left( \exists x \right) \left( \alpha \right) \left[ s \right]$ if and only if there is an element $a \in A$ such that $\mathfrak{A} \models \alpha \left[ s \left[ x | a \right] \right]$.