4.2 Models and interpretations of first-order theories

Models and interpretations in first-order logic

Defining models and interpretations

A model (also called a structure) for a first-order language is a mathematical object that gives concrete meaning to every non-logical symbol in that language. An interpretation is the specific assignment of meanings that a model provides. Once you have a model, every sentence in the language becomes determinately true or false.

A model $\mathfrak{A}$ has two parts:

1. A domain (or universe) $A$: a non-empty set of objects over which the quantifiers range. This could be the natural numbers, the real numbers, a set of people, or any non-empty set you choose.
2. An interpretation function that assigns meaning to each non-logical symbol:
   • Each constant symbol $c$ is mapped to a specific element of $A$. For example, if $A = \mathbb{N}$, you might interpret $c$ as the number 5.
   • Each n-ary function symbol $f$ is mapped to a function $f^{\mathfrak{A}}: A^n \to A$. For instance, a binary function symbol could be interpreted as addition on $\mathbb{N}$, taking pairs of natural numbers to their sum.
   • Each n-ary predicate symbol $P$ is mapped to a subset of $A^n$, representing the tuples for which the predicate holds. A unary predicate $P$ on $\mathbb{N}$ might be interpreted as the set of even numbers, so $P(x)$ is true exactly when $x$ is even.

Different models can share the same language but differ in domain, interpretation, or both. This is why the same formula can be true in one model and false in another.

Components at a glance

A model is complete in the sense that it assigns meaning to every non-logical symbol in the language, leaving nothing uninterpreted.

Truth values of formulas under interpretations

Evaluating atomic and complex formulas

Truth in a model is defined recursively, starting from atomic formulas and building up.

Atomic formulas. The truth value of an atomic formula like $P(t_1, \ldots, t_n)$ depends on whether the tuple of values assigned to the terms $t_1, \ldots, t_n$ falls within the interpretation of $P$. If $P^{\mathfrak{A}}$ is the set of even numbers and $a^{\mathfrak{A}} = 4$, then $P(a)$ is true because $4$ is even.

Complex formulas. Logical connectives combine formulas according to the standard truth tables from propositional logic:

• Negation $\neg\varphi$: true iff $\varphi$ is false
• Conjunction $\varphi \wedge \psi$: true iff both $\varphi$ and $\psi$ are true
• Disjunction $\varphi \vee \psi$: true iff at least one of $\varphi$, $\psi$ is true
• Implication $\varphi \rightarrow \psi$: false only when $\varphi$ is true and $\psi$ is false
• Biconditional $\varphi \leftrightarrow \psi$: true iff $\varphi$ and $\psi$ share the same truth value

You evaluate complex formulas by recursively working inward until you reach atomic formulas whose truth values you can read off directly from the model.

Evaluating quantified formulas

Quantifiers are where models really matter, because their truth depends on what's in the domain.

• Universal quantifier: $\forall x\, \varphi(x)$ is true in $\mathfrak{A}$ iff $\varphi(a)$ holds for every element $a \in A$.
• Existential quantifier: $\exists x\, \varphi(x)$ is true in $\mathfrak{A}$ iff $\varphi(a)$ holds for at least one element $a \in A$.

The domain choice can flip truth values entirely. Consider $\forall x\, (x \geq 0)$: this is true when the domain is $\mathbb{N}$ but false when the domain is $\mathbb{Z}$. Similarly, $\exists x\, (x < 0)$ is false over $\mathbb{N}$ but true over $\mathbb{Z}$.

Technically, evaluating a quantified formula requires a variable assignment $s$ that maps each variable to an element of $A$. When you encounter $\forall x\, \varphi(x)$, you check whether $\varphi$ is satisfied under every variant of $s$ that differs from $s$ at most on what it assigns to $x$. For sentences (formulas with no free variables), the choice of assignment doesn't matter, so truth depends only on the model itself.

Constructing models for first-order formulas

Steps for constructing models

Building a model that satisfies a given set of formulas $\Sigma$ is one of the most common tasks you'll encounter. Here's a systematic approach:

1. Identify the non-logical symbols. List every constant, function symbol, and predicate symbol that appears in $\Sigma$.
2. Choose a domain. Pick a non-empty set $A$ that can plausibly satisfy the constraints imposed by $\Sigma$. Start small: if nothing in $\Sigma$ forces an infinite domain, try a finite set first.
3. Assign interpretations. For each non-logical symbol, define its interpretation over $A$. Work through the formulas in $\Sigma$ one at a time to make sure each one comes out true.
4. Verify. Check every formula in $\Sigma$ against your model. A single false formula means the model fails.

Example: Suppose $\Sigma = \{\forall x\,(P(x) \rightarrow Q(x)),\; \exists x\, P(x)\}$. You need a domain with at least one element satisfying $P$, and every element satisfying $P$ must also satisfy $Q$. A minimal model: let $A = \{0\}$, $P^{\mathfrak{A}} = \{0\}$, $Q^{\mathfrak{A}} = \{0\}$. Both formulas are satisfied.

Key considerations

• Size constraints. Some formulas force the domain to have a minimum size. The formula $\exists x\, \exists y\, (x \neq y)$ requires $|A| \geq 2$. The formula $\exists x\,(x \neq a)$ requires at least one domain element distinct from $a^{\mathfrak{A}}$.
• Structural constraints. Formulas can impose algebraic properties on function symbols. For instance, $\forall x\, \forall y\, (f(x, y) = f(y, x))$ forces $f^{\mathfrak{A}}$ to be commutative.
• Incremental construction. For a large set $\Sigma$, it often helps to build a model for a subset of the formulas first, then extend or adjust it to accommodate the rest, checking consistency at each step.
• Non-uniqueness. A satisfiable set of formulas can have many non-isomorphic models. Exploring different models deepens your understanding of what the theory actually pins down and what it leaves open.

Models and consistency of first-order theories

Relationship between models and consistency

The connection between models and consistency is one of the central results in first-order logic:

The "if" direction is straightforward: if a model $\mathfrak{A}$ makes every axiom of $T$ true, then $T$ cannot derive a contradiction, because $\mathfrak{A}$ would have to make that contradiction true as well, which is impossible.

The "only if" direction is the deep result: Gödel's Completeness Theorem guarantees that every consistent first-order theory has a model. The model may be infinite and non-constructive, but it exists.

A theory containing both $\forall x\, P(x)$ and $\exists x\, \neg P(x)$ as axioms is inconsistent because no single domain and interpretation of $P$ can make both true simultaneously.

Proving consistency by constructing models

The most direct way to prove a theory $T$ is consistent is to exhibit a model:

1. Identify the language of $T$ (all non-logical symbols).
2. Define a domain $A$.
3. Provide interpretations for every non-logical symbol.
4. Verify that every axiom of $T$ evaluates to true in the resulting structure.

If you succeed, you've proven consistency outright. This is often the cleanest method for finite or well-understood theories.

For more complex situations, other tools are available:

• The Compactness Theorem lets you establish consistency of an infinite theory by showing that every finite subset has a model.
• Proof-theoretic methods show consistency by demonstrating that no derivation of a contradiction exists.

But the model-existence criterion remains the foundational one. Whenever you can build a concrete structure that satisfies all the axioms, you have the strongest possible evidence that the theory is consistent.