Lesson 4

The truth of an expression is determined by the values of its constituents, much as in Boolean logic. However, variables, functions, and relations can now take on much more complex values than just \(\texttt{True}\) and \(\texttt{False}\). The analog of a truth assignment for first-order logic is a far more complicated mathematical object called a model.

A model appropriate to \(\Sigma\) is a pair \(M = (U, \mu)\), where \(U\) is a set (any non-empty set), called the universe of \(M\), and \(\mu\) is a function assigning to each variable, function symbol, and relation symbol in \(V \cup \Phi \cup \Pi\) actual objects in \(U\).

• For each variable \(x\), \(\mu\) assigns an element \(x^{M} \in U\) (notice that we denote the values of mapping \(\mu\) by the superscript \(M\), instead of \(\mu(\cdot)\)).


• For each \(k\)-ary function symbol \(f \in \Phi\), \(\mu\) assigns an actual function \(f^{M} \colon U^{k} \to U\) (thus, if \(c \in \Phi\) is a constant, \(c^{M}\) is an element of \(U\)).


• Finally, to each \(k\)-ary relation symbol \(R \in \Pi\), \(\mu\) assigns an actual relation \(R^{M} \subseteq U^{k}\). However, to the equality relation symbol \(=\), \(\mu\) is required to assign the relation \(=^{M}\), which is always \(\{(u,u) : u \in U\}\).

Suppose now that \(\phi\) is an expression over vocabulary \(\Sigma\), and that \(M\) is a model appropriate to \(\Sigma\). We shall define when \(M\) satisfies \(\phi\), written \(M \models \phi\). First, we must define, for an arbitrary term \(t\) over \(\Sigma\), what is its meaning under \(M\), \(t^{M}\). We are already off to a good start: If \(t\) is a variable or a constant, \(t^{M}\) is defined explicitly by \(\mu\).

So, if \(t = f(t_{1}, …, t_{k})\), where \(f\) is a \(k\)-ary function symbol and \(t_{1}, …, t_{k}\) are terms, then \(t^{M}\) is defined to be \(f^{M}(t_{1}^{M}, …, t_{k}^{M})\). This completes our definition of the semantics of terms.

Suppose then that \(\phi\) is an atomic expression, \(\phi = R(t_{1}, …, t_{k})\), where \(t_{1}, …, t_{k}\) are terms. Then \(M\) satisfies \(\phi\) if \((t_{1}^{M}, …, t_{k}^{M}) \in R^{M}\).

If expression \(\phi\) is not atomic, satisfaction will be defined by induction on the structure of \(\phi\).

• If \(\phi = \lnot \psi\), then \(M \models \phi\) if \(M \not\models \psi\).


• If \(\phi = \psi_{1} \lor \psi_{2}\), \(M \models \phi\) if \(M \models \psi_{1}\) or \(M \models \psi_{2}\).


• If \(\phi = \psi_{1} \land \psi_{2}\), \(M \models \phi\) if \(M \models \psi_{1}\) and \(M \models \psi_{2}\).


• If \(\phi = \forall x \ \psi\), then \(M \models \phi\) if the following is true: For any \(u \in U\), let \(M_{x = u}\) be the model that is identical to \(M\) in all details, except that \(x^{M_{x = u}}= u\). The requirement is that, for all \(u \in U\), \(M_{x = u}\models \psi\).