Satisfaction

We will say that a formula is true or false on some interpretation $\cal I$. If some formula $\psi$ is true on some $\cal I$, we write

$$\mbox{$\cal I$} \models \psi$$

Other ways to express such a fact include saying that $\cal I$ models $\psi$ (and hence that $\cal I$ is a model of $\psi$), or that $\cal I$ satisfies $\psi$. But what is an interpretation? An interpretation is an ordered pair $(\cal U,$ $\varphi$); the first of these elements is a structure, the second is an assignment. $\cal U$ is in turn a pair itself, viz., $(\cal D,$ $\alpha$). $\cal D$ is the interpretation's domain, which is simply a nonempty set; $\varphi$ is simply a mapping from the set of variables (in the alphabet for first-order languages introduced above) to $\cal D$. The ``meat" of an interpretation is found in $\alpha$. Let S be some fixed symbol set. Then, where $\cal D$ⁿ is $\overbrace{\mbox{$\cal D$ } \times \cdots \times \mbox{$\cal D$ }}^{\mbox{$n$\space times}}$, $\alpha$

• maps each constant c in S to some element $\alpha(c) \in$ $\cal D$ (we also write $c^{\mbox{{\scriptsize$\cal U$ }}}$ for $\alpha(c)$);
• maps each n-ary functor in S to a corresponding n-ary function $\alpha(f)$ on $\cal D$ (we also write $f^{\mbox{{\scriptsize$\cal U$ }}}$ for $\alpha(f)$);
• maps each n-ary relation R in S to an n-ary relation $\alpha(R) \subseteq$ $\cal D$ⁿ (we also write $R^{\mbox{{\scriptsize$\cal U$ }}}$ for $\alpha(R)$).

Let $\varphi$ be an assignment in some structure $\cal U$, let a be some element of the domain $\cal D$, and let x be some variable. We write

$$\varphi^a_x$$

for the assignment that maps x to a and maps other variables as $\varphi$ does. If $\cal I$ is some interpretation composed of a structure $\cal U$ and assignment $\varphi$,

$$\mbox{$\cal I$}^a_x = (\mbox{$\cal U$}, \varphi^a_x).$$

If x is a variable, set $\cal I$ $(x) = \varphi(x)$; and if c is a constant, let $\cal I$ $(c) = c^{\mbox{{\scriptsize$\cal U$ }}}$. Furthermore, if f is an n-ary functor, and $t_1, t_2, \ldots, t_n$ are terms, let

$$\mbox{$\cal I$}(f(t_1, \ldots, t_n)) = f^{\mbox{{\scriptsize $\cal U$}}}(\mbox{$\cal I$}(t_1), \ldots, \mbox{$\cal I$}(t_n)).$$

At this point we can say exactly when an interpretation $\cal I$ models or satisfies a formula; there are nine clauses in the definition:

$\cal I$ $\models (t_1 = t_2)$ iff $\cal I$(t₁) = $\cal I$(t₂)

$\cal I$ $\models Rt_1 \ldots t_n$ iff ($\cal I$(t₁), ..., $\cal I$(t_n)) $\in R^{\cal U}$

$\cal I$ $\models \neg\phi$ iff not $\cal I$ $\models \phi$

$\cal I$ $\models (\phi \wedge \psi)$ iff $\cal I$ $\models \phi$ and $\cal I$ $\models \psi$

$\cal I$ $\models (\phi \vee \psi)$ iff $\cal I$ $\models \phi$ or $\cal I$ $\models \psi$

$\cal I$ $\models (\phi \rightarrow \psi)$ iff if $\cal I$ $\models \phi$ then $\cal I$ $\models \psi$

$\cal I$ $\models (\phi \leftrightarrow \psi)$ iff $\cal I$ $\models \phi$ iff $\cal I$ $\models \psi$

$\cal I$ $\models \exists x \phi$ iff there exists at least one object o in the domain $\cal D$ such that $\cal I$_x^o $\models \phi$

$\cal I$ $\models \forall x \phi$ iff for all objects o in the domain $\cal D$, $\cal I$_x^o $\models \phi$

The satisfaction relation is easily extended to cover sets of formulas: If $\Phi$ is such a set, $\cal I$ $\models \Phi$ just in case $\cal I$ models every formula in $\Phi$.