2.3 Semantics of FOL: interpretations, models, and truth assignments

Interpretations, Models, and Truth Assignments

First-order logic goes beyond propositional logic by giving meaning to the internal structure of statements. An interpretation assigns real-world significance to abstract symbols, and a model is an interpretation that makes a given formula true. Understanding how these work is central to evaluating whether FOL formulas are true, satisfiable, or valid.

Defining Interpretations, Models, and Truth Assignments

An interpretation $\mathcal{I}$ for a first-order language consists of two things:

1. A domain of discourse $D$ (a non-empty set of objects the quantifiers range over).
2. An assignment of meaning to every non-logical symbol: constants get mapped to elements of $D$, function symbols to functions on $D$, and predicate symbols to relations on $D$.

A model of a formula $\varphi$ is an interpretation under which $\varphi$ evaluates to true. If at least one model exists, the formula is satisfiable.

A variable assignment is a function $s$ that maps each variable to an element of $D$. This is what handles free variables: to evaluate a formula with free variables, you need both an interpretation and a variable assignment. Together, $\mathcal{I}$ and $s$ determine a truth value for every formula in the language.

Mapping Symbols to Elements, Functions, and Relations

Here's what an interpretation does to each type of non-logical symbol:

• Constant symbols get mapped to specific elements of $D$. For example, if $D = \mathbb{N}$, the constant $a$ might be mapped to the number 3.
• $n$-ary function symbols get mapped to $n$-ary functions on $D$. For example, a binary function symbol $f$ could be mapped to the addition function, so $f(x, y) = x + y$.
• $n$-ary predicate symbols get mapped to $n$-ary relations on $D$ (subsets of $D^n$). For example, a unary predicate $P$ might be mapped to the set of even numbers $\{0, 2, 4, 6, \ldots\}$, so $P(x)$ holds exactly when $x$ is even.

A concrete interpretation might look like this:

• $D = \{1, 2, 3\}$
• $c^{\mathcal{I}} = 2$
• $P^{\mathcal{I}} = \{1, 3\}$ (the odd numbers in $D$)
• $f^{\mathcal{I}}(x) = x$ (the identity function)

With this interpretation fully specified, you can evaluate any formula built from these symbols.

Truth Values in First-Order Logic

Assigning Truth Values to Atomic Formulas

Evaluating a formula under an interpretation works from the inside out. You start with atomic formulas and build up.

An atomic formula like $P(a)$ is true under $\mathcal{I}$ if and only if the element that $a$ denotes (under $\mathcal{I}$) is in the relation that $P$ denotes. Using the example above where $a \mapsto 3$ and $P \mapsto \{0, 2, 4, \ldots\}$: since 3 is not even, $P(a)$ is false.

For compound formulas built with connectives ($\land, \lor, \rightarrow, \neg$), truth values are computed using the same truth tables as propositional logic. The new machinery comes with quantifiers.

Evaluating Quantified Formulas

Quantifiers are what make FOL semantics genuinely different from propositional logic. Here's how each one works:

• Universal quantifier: $\forall x\, \varphi(x)$ is true under $\mathcal{I}$ if and only if $\varphi(x)$ is true for every element $d \in D$ when $x$ is assigned to $d$. If even one element makes $\varphi$ false, the whole formula is false.
• Existential quantifier: $\exists x\, \varphi(x)$ is true under $\mathcal{I}$ if and only if $\varphi(x)$ is true for at least one element $d \in D$.

With $D = \mathbb{N}$ and $P(x)$ meaning "$x$ is even":

• $\forall x\, P(x)$ is false (1 is not even).
• $\exists x\, P(x)$ is true (2 is even).

Nested quantifiers require careful attention to order. Consider these two formulas over $\mathbb{N}$ with the standard $<$ relation:

• $\forall x\, \exists y\, (x < y)$: For every number, there exists a larger one. True in $\mathbb{N}$.
• $\exists y\, \forall x\, (x < y)$: There exists a single number larger than all numbers. False in $\mathbb{N}$.

The formulas have identical symbols but different quantifier order, which completely changes the meaning. When evaluating nested quantifiers, work from the outside in: fix the outermost variable first, then evaluate the inner formula relative to that choice.

Satisfiability and Validity of Formulas

Satisfiability and Models

• A formula is satisfiable if there exists at least one interpretation (model) that makes it true. To demonstrate satisfiability, you just need to exhibit one such model.
• A formula is unsatisfiable if no interpretation makes it true.

For example, $\exists x\, P(x)$ is satisfiable: take $D = \{0\}$ and let $P^{\mathcal{I}} = \{0\}$. That's a model.

The formula $\forall x\, P(x) \land \forall x\, \neg P(x)$ is unsatisfiable. It requires every element to both satisfy and not satisfy $P$, which is a contradiction regardless of the domain or the interpretation of $P$.

Validity and Interpretations

A formula is valid (also called a logical truth) if it is true under every interpretation with every non-empty domain. Every interpretation is a model for a valid formula.

• $\forall x\, P(x) \lor \neg \forall x\, P(x)$ is valid because it's an instance of the tautology $\varphi \lor \neg \varphi$.
• $\forall x\, (P(x) \lor \neg P(x))$ is also valid: for any element and any predicate, either the element satisfies the predicate or it doesn't.

Proving validity is harder than proving satisfiability. For satisfiability, one model suffices. For validity, you must show truth holds across all possible interpretations, which typically requires a proof method like natural deduction, semantic tableaux, or a direct semantic argument.

To show a formula is not valid, you only need one countermodel: a single interpretation where the formula comes out false.

Syntax vs. Semantics in First-Order Logic

Syntax: Structure and Rules

Syntax concerns the formal rules for building well-formed formulas (wffs). It tells you which strings of symbols are grammatically correct, without saying anything about what they mean. For instance, $\forall x\, (P(x) \land Q(x))$ is syntactically well-formed because it follows the construction rules for quantifiers and connectives. The string $\forall \land P x)(Q$ is not.

Syntax gives you the framework for expressing statements. Semantics tells you whether those statements are true.

Semantics: Meaning and Truth

Semantics assigns meaning to syntactically correct formulas by specifying an interpretation. The formula $\forall x\, (P(x) \land Q(x))$ is true under $\mathcal{I}$ if, for every element in the domain, both $P$ and $Q$ hold for that element.

The same syntactic formula can be true under one interpretation and false under another. That's the whole point: syntax is fixed, but truth depends on interpretation.

Relationship Between Syntax and Semantics

Satisfiability and validity are semantic properties because they depend on interpretations and models, not on the formula's syntactic shape alone. Two formulas can look very different syntactically but have the same truth value under every interpretation (they're logically equivalent). Conversely, two formulas with similar syntactic structure can differ in satisfiability.

The connection between syntax and semantics is formalized by key metatheorems you'll encounter later in the course: soundness (if a formula is provable, it's valid) and completeness (if a formula is valid, it's provable). These results show that the syntactic proof machinery and the semantic notion of truth line up perfectly in first-order logic.