10. Semantics of First-Order Logic
In propositional logic, we saw how to use truth tables to evaluate formulas. In first-order logic, the evaluation of sentences (or closed formulas) requires a bit more machinery.
Domains and Structures
The signature of a first-order language specifies which symbols are used to represent constants, functions, and predicates. But it does not specify how we interpret those symbols. The interpretation is given by a structure.
Definition. The structure \(\mathcal{M}\) for a signature specifies:
- The domain \(D\) is the non-empty set of elements.
- An element \(c^\mathcal{M} \in D\) for each constant \(c\) in the signature.
- A function \(f^\mathcal{M} \colon D^n \to D\) for each \(n\)-ary function \(f\) in the signature.
- A subset \(P^\mathcal{M} \subseteq D^n\) for each \(n\)-ary predicate \(P\) in the signature.
Note that the domain in a structure can be either finite or infinite. And infinite domains can be countable or not. They can also contain any arbitrary sets of elements. But they must include at least one element.
Examples.
- One structure for the number theory signature \(\{0,S,+,\times\}\) fixes \(\mathbb{N} = \{0,1,2,\ldots\}\) as the domain, the usual definitions for \(+\) and \(\times\), and \(S(n) = n+1\) for each \(n \in \mathbb{N}.\)
- Different structures for number theory are obtained by choosing the set of integers \(\mathbb{Z}\), the real numbers \(\mathbb{R}\), or even a finite set \(\mathbb{Z}_4 = \{0,1,2,3\}\) for the domain.
In general the structure need not correspond to a natural interpretation of a signature. For instance,
- Another structure for the number theory signature above fixes the domain \(\mathbb{Z}\) but defines \(+\) to be the function that maps each pair of integers \(m,n\) to \(0\) and \(\times\) to be the function that maps the pair \(m,n\) to \(7\) when \(m\) divides \(n\) and \(13\) when it does not.
Or, we can also obtain a structure \(\mathcal{M}_f\) for the same signature by taking the domain
\[D = \{ \mathrm{apple}, \mathrm{banana}, \mathrm{cherry}\},\]setting \(0^{\mathcal{M}_f} = \mathrm{apple},\) defining the \(+\) function to be the function defined by the table
\(+\) apple banana cherry apple apple apple apple banana cherry banana banana cherry apple banana banana and defining the \(\times\) function with the table
\(\times\) apple banana cherry apple apple banana cherry banana banana cherry apple cherry cherry apple banana
Evaluating Formulas
Once we have fixed a structure \(\mathcal{M}\) on the first-order language with a given signature, we can then evaluate the truth value of sentences.
Definition. The valuation of a sentence \(\phi\) with respect to the structure \(\mathcal{M}\) over the signature \(\sigma\), denoted \(\mathrm{val}_{\mathcal{M}}(\phi),\) is defined recursively.
\[\begin{align*} \mathrm{val}_\mathcal{M}(\phi \wedge \psi) &= \mathrm{val}_\mathcal{M}(\phi) \wedge \mathrm{val}_\mathcal{M}(\psi) \\ \mathrm{val}_\mathcal{M}(\phi \vee \psi) &= \mathrm{val}_\mathcal{M}(\phi) \vee \mathrm{val}_\mathcal{M}(\psi) \\ \mathrm{val}_\mathcal{M}(\neg \phi &= \neg \mathrm{val}_\mathcal{M}(\phi) \\ \mathrm{val}_\mathcal{M}(\phi \to \psi) &= \mathrm{val}_\mathcal{M}(\phi) \to \mathrm{val}_\mathcal{M}(\psi) \\ \mathrm{val}_\mathcal{M}(\phi \leftrightarrow \psi) &= \mathrm{val}_\mathcal{M}(\phi) \leftrightarrow \mathrm{val}_\mathcal{M}(\psi). .\end{align*}\]
Evaluation of terms. For any constant \(c\), function \(f\), and term \(t\),
\[\begin{align*} \mathrm{val}_{\mathcal{M}}(c) &= c^\mathcal{M} \\ \mathrm{val}_{\mathcal{M}}(f(t)) &= f^\mathcal{M}( \mathrm{val}_{\mathcal{M}}(t)) \end{align*}\]Evaluation of predicates. For any terms \(t_1,t_2,\ldots,t_n\) and predicate \(P\),
\[\begin{align*} \mathrm{val}_{\mathcal{M}}\big((t_1 = t_2)\big) &= \begin{cases} True & \mbox{if } \mathrm{val}_{\mathcal{M}}(t_1) = \mathrm{val}_{\mathcal{M}}(t_2) \\ False & \mbox{otherwise} \end{cases} \\ \mathrm{val}_{\mathcal{M}}\big(P(t_1,\ldots,t_n)\big) &= \begin{cases} True & \mbox{if } (\mathrm{val}_{\mathcal{M}}(t_1),\ldots,\mathrm{val}_{\mathcal{M}}(t_n))) \in P^{\mathcal{M}} \\ False & \mbox{otherwise} \end{cases} \end{align*}\]Evaluation of quantifiers. For any variable \(v\) and formula \(\phi\), if we let \(\phi_{[d/v]}\) denote the formula obtained by replacing all free occurrences of \(v\) in \(\phi\) with \(d\) for some element \(d \in D\), then
\[\begin{align*} \mathrm{val}_\mathcal{M}(\exists v \, \phi) &= \begin{cases} True &\mbox{if } \exists d \in D \mbox{ such that } \mathrm{val}_\mathcal{M}( \phi_{[v/d]} ) = True \\ False & \mbox{otherwise} \end{cases} \\ \mathrm{val}_\mathcal{M}(\forall v \, \phi) &= \begin{cases} True &\mbox{if } \forall d \in D, \mathrm{val}_\mathcal{M}(\phi_{[d/v]}) = True \\ False & \mbox{otherwise} \end{cases} \end{align*}\]Evaluation of connectives. The evaluation of compound formulas follows the same rules as in propositional logic:
With this recursive method of evaluation, a structure \(\mathcal{M}\) causes all closed formulas to evaluate to either True or False. All formulas that contain free variables are not assigned a truth value.
Example.
- In the standard structure for number theory with domain \(\mathbb{N}\), the sentence \(\forall x_1 ((x_1 = 0) \vee \neg(x_1 + x_1 = x_1)\) evaluates to True. To see this, we have to evaluate \(((n = 0) \vee \neg(n + n = n)\) for every \(n \in \mathbb{N}\). When \(n=0\), this formula evaluates to True because \((n=0)\) evaluates to True. And when \(n \neq 0\), it evaluates to True because \(n+n = 2n\) and \(2n \neq n\) for all \(n > 0\).
Validity and Satisfiability
Definition. The structure \(\mathcal{M}\) satisfies the sentence \(\phi\), which we write as
\[\mathcal{M} \vDash \phi,\]when \(\mathrm{val}_{\mathcal{M}}(\phi) = True\).
The sentence \(\phi\) is satisfiable when there exists a structure \(\mathcal{M}\) that satisfies \(\phi.\)
The sentence \(\phi\) is (logically) valid when every structure \(\mathcal{M}\) satisfies \(\phi.\) We write \(\vDash \phi\) when \(\phi\) is valid.
Examples.
The sentence
\[\forall x_1 \forall x_2 ((x_1 + x_2) = (x_2 + x_1))\]in the number theory signature is satisfiable. The standard structure with domains \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{R}\), and \(\mathbb{Z}_4\), for instance, all satisfy it.
The sentence above is not valid. The fruit structure \(\mathcal{M}_f\), for example, has \(\mathrm{apple} + \mathrm{banana} \neq \mathrm{banana} + \mathrm{apple}\).
For any signature with the unary predicate \(P\), the sentence
\[(\forall x_1 \neg P(x_1) \to \neg \exists x_1 P(x_1))\]is valid.
Valid formulas in first-order logic are analogous to tautologies in propositional logic. Of even more interest, however, is the extension of the notion of logical consequence in propositional logic to first-order logic.
Definition. The sentence \(\phi\) is a (logical) consequence of the set \(\Gamma\) of sentences, denoted
\[\Gamma \vDash \phi,\]when every structure \(\mathcal{M}\) that satisfies all the sentences in \(\Gamma\) also satisfies \(\phi.\)
Examples. Fix any signature that includes unary predicates \(P\) and \(Q\). Then
\(\big\{ \forall x_1 \neg P(x_1) \big\} \vDash \neg \exists x_1 P(x_1)\) and
\(\big\{ \forall x_1 (P(x_1) \to Q(x_1)) \big\} \vDash (\forall x_1 P(x_1) \to \forall x_1 Q(x_1))\).
However,
- \(\{ (\forall x_1 P(x_1) \to \forall x_1 Q(x_1)\} \not\vDash \forall x_1 (P(x_1) \to Q(x_1))\).
As the last three examples demonstrate, it’s usually not obvious if a logical consequence holds or not. We will explore how to establish or refute logical consequences in the next lecture. But for today, we conclude with the last bit of terminology that we use extensively in the study of first-order logic.
Axioms, Theories, and Models
A set of axioms in a first-order language is a set \(\Gamma\) of sentences in that language.
The (first-order) theory corresponding to a set of axioms \(\Gamma\) is the set of sentences that are logical consequences of \(\Gamma.\)
Definition. A model for the theory corresponding to the set \(\Gamma\) of axioms is a structure that satisfies all of the sentences in \(\Gamma.\)
Example.
\[\begin{align*} &\forall x_1 (((1 \cdot x_1) = x_1) \wedge ((x_1 \cdot 1) = x_1)), \\ &\forall x_1 (((x_1 \cdot \mathrm{inv}(x_1)) = 1) \wedge ((\mathrm{inv}(x_1) \cdot x_1) = 1)), \mbox{ and} \\ &\forall x_1 \forall x_2 \forall x_3 ((x_1 \cdot (x_2 \cdot x_3)) = ((x_1 \cdot x_2) \cdot x_3)). \end{align*}\]
- One signature for group theory includes the constant \(1\), the unary function \(\mathrm{inv}\), and the binary function \(\cdot\). A set of standard axioms for group theory is the set \(\Gamma_{g}\) of the 3 axioms
The theory of the axiom system \(\Gamma_g\) is the set of sentences that are true for all groups. Every group also forms a model for the theory of \(\Gamma_g\). (The simplest model of this theory is obtained by considering a domain \(D\) that consists of a single element, and defining \(1\), \(\mathrm{inv}\), and \(\cdot\) accordingly.)
We will see many other theories and models in the next lecture.