# 2.4 Satisfaction and Models

Satisfaction is the formal relation that connects syntax with semantics in first order logic, and it tells us when a formula is true in a structure under a given assignment of objects to its free variables.

### Satisfaction

Let $\mathcal{M}$ be a structure with domain $M$, and let $s$ be an assignment:
$$
s : \mathrm{Var} \to M
$$

The notation:
$$
\mathcal{M}, s \models A
$$
means that the formula $A$ is satisfied in the structure $\mathcal{M}$ under the assignment $s$.

This notation is used because formulas may contain free variables, and the truth of such a formula can depend on which elements of the domain are assigned to those variables.

### Definition 2.29 (Satisfaction for Atomic Formulas)

Let $\mathcal{M}$ be a structure, let $s$ be an assignment, and let $t_1, \dots, t_n$ be terms.

If $P$ is an $n$-ary predicate symbol, then:
$$
\mathcal{M}, s \models P(t_1, \dots, t_n)
$$
if and only if:
$$
(t_1^{\mathcal{M}, s}, \dots, t_n^{\mathcal{M}, s}) \in P^{\mathcal{M}}
$$

If the atomic formula is an equality:
$$
t_1 = t_2
$$
then:
$$
\mathcal{M}, s \models t_1 = t_2
$$
if and only if:
$$
t_1^{\mathcal{M}, s} = t_2^{\mathcal{M}, s}
$$

Thus atomic formulas are evaluated by first evaluating their terms and then checking whether the corresponding relation or equality holds in the structure.

### Definition 2.30 (Satisfaction for Connectives)

The satisfaction relation extends from atomic formulas to compound formulas by following the truth rules for the logical connectives.

For negation:
$$
\mathcal{M}, s \models ¬A
$$
if and only if:
$$
\mathcal{M}, s \not\models A
$$

For conjunction:
$$
\mathcal{M}, s \models A \land B
$$
if and only if:
$$
\mathcal{M}, s \models A
\quad \text{and} \quad
\mathcal{M}, s \models B
$$

For disjunction:
$$
\mathcal{M}, s \models A \lor B
$$
if and only if:
$$
\mathcal{M}, s \models A
\quad \text{or} \quad
\mathcal{M}, s \models B
$$

For implication:
$$
\mathcal{M}, s \models A \to B
$$
if and only if either:
$$
\mathcal{M}, s \not\models A
$$
or:
$$
\mathcal{M}, s \models B
$$

For biconditional:
$$
\mathcal{M}, s \models A \leftrightarrow B
$$
if and only if:
$$
\mathcal{M}, s \models A
$$
and:
$$
\mathcal{M}, s \models B
$$
have the same truth value.

### Definition 2.31 (Changing an Assignment)

Let $s$ be an assignment, let $x$ be a variable, and let $a \in M$.

We write:
$$
s[x \mapsto a]
$$
for the assignment that sends $x$ to $a$ and agrees with $s$ on every variable other than $x$.

Thus:
$$
s[x \mapsto a](x)=a
$$
and if $y \ne x$, then:
$$
s[x \mapsto a](y)=s(y)
$$

This notation is used to define the semantics of quantifiers, since quantifiers vary the value assigned to one variable while leaving the other variables fixed.

### Definition 2.32 (Satisfaction for Quantifiers)

For the universal quantifier:
$$
\mathcal{M}, s \models \forall x \, A
$$
if and only if for every $a \in M$:
$$
\mathcal{M}, s[x \mapsto a] \models A
$$

Thus $\forall x \, A$ is true when $A$ is true no matter which element of the domain is assigned to $x$.

For the existential quantifier:
$$
\mathcal{M}, s \models \exists x \, A
$$
if and only if there exists $a \in M$ such that:
$$
\mathcal{M}, s[x \mapsto a] \models A
$$

Thus $\exists x \, A$ is true when $A$ is true for at least one element of the domain assigned to $x$.

### Example 2.33

Let $\mathcal{N}$ be the usual structure of natural numbers:
$$
\mathcal{N} = (\mathbb{N}; 0, S, +, \times, <)
$$

Consider the formula:
$$
\forall x \, \exists y \, (x < y)
$$

To check satisfaction, choose any element $a \in \mathbb{N}$ for $x$.

We need to find some element $b \in \mathbb{N}$ such that:
$$
a < b
$$

Taking:
$$
b = a + 1
$$
works for every natural number $a$, and therefore:
$$
\mathcal{N} \models \forall x \, \exists y \, (x < y)
$$

This sentence expresses the fact that the natural numbers have no greatest element.

### Example 2.34

Let $\mathcal{A}$ be the finite ordered structure:
$$
\mathcal{A} = (\{0,1,2\}; <)
$$
where $<$ is the usual order restricted to the set $\{0,1,2\}$.

The sentence:
$$
\forall x \, \exists y \, (x < y)
$$
is false in $\mathcal{A}$.

Indeed, if $x$ is assigned the value $2$, then there is no element $y \in \{0,1,2\}$ such that:
$$
2 < y
$$

Thus:
$$
\mathcal{A} \not\models \forall x \, \exists y \, (x < y)
$$

The same formula can therefore be true in one structure and false in another structure.

### Lemma 2.35 (Dependence on Free Variables)

Let $A$ be a formula, and let $s$ and $s'$ be assignments in a structure $\mathcal{M}$.

If $s$ and $s'$ agree on every free variable of $A$, then:
$$
\mathcal{M}, s \models A
$$
if and only if:
$$
\mathcal{M}, s' \models A
$$

Proof

The proof is by structural induction on the formula $A$.

For atomic formulas, the truth of the formula depends only on the values of the variables occurring in its terms, and these variables are free in the atomic formula, so the two assignments give the same values to all relevant terms.

For negation and binary connectives, the result follows directly from the induction hypothesis applied to the immediate subformulas.

For a quantified formula such as:
$$
\forall x \, B
$$
the variable $x$ is bound, so the free variables of $\forall x \, B$ are the free variables of $B$ except for $x$.

To evaluate the universal quantifier, we compare:
$$
\mathcal{M}, s[x \mapsto a] \models B
$$
and:
$$
\mathcal{M}, s'[x \mapsto a] \models B
$$
for each $a \in M$.

The modified assignments agree on all free variables of $B$, because they both send $x$ to $a$ and because $s$ and $s'$ agree on the remaining free variables.

The existential case is similar.

### Corollary 2.36 (Truth of Sentences)

If $A$ is a sentence, then its truth in a structure does not depend on the choice of assignment.

Proof

A sentence has no free variables.

Therefore any two assignments agree on all free variables of $A$, because there are none.

By Lemma 2.35, the truth value of $A$ is the same under all assignments.

### Models

A model is a structure in which a sentence or set of sentences is true.

### Definition 2.37 (Model of a Sentence)

Let $A$ be a sentence. A structure $\mathcal{M}$ is a model of $A$ if:
$$
\mathcal{M} \models A
$$

This means that $A$ is true in $\mathcal{M}$.

### Definition 2.38 (Model of a Theory)

A theory is a set of sentences.

Let $T$ be a theory. A structure $\mathcal{M}$ is a model of $T$ if:
$$
\mathcal{M} \models A
$$
for every sentence $A \in T$.

In this case we write:
$$
\mathcal{M} \models T
$$

Thus a model of a theory is a structure satisfying all sentences in that theory.

### Example 2.39

The group axioms form a first order theory in a language with a binary function symbol, a unary function symbol, and a constant symbol.

A structure is a model of this theory exactly when its domain and operations form a group.

Similarly, the axioms for rings, fields, partial orders, and graphs can be written as first order theories, and their models are precisely the corresponding mathematical structures.

### Example 2.40

Let $T$ be the theory containing the sentence:
$$
\forall x \, \exists y \, (x < y)
$$

The usual natural number structure:
$$
(\mathbb{N}; <)
$$
is a model of $T$.

The finite ordered structure:
$$
(\{0,1,2\}; <)
$$
is not a model of $T$.

Thus the same theory may have some structures as models and exclude others.