---
title: Structures, Truth, and Satisfaction
module: First-Order Languages and Structures
moduleNumber: 3
lessonNumber: 2
order: 302
summary: >
  A structure interprets a language: a nonempty universe plus a meaning for
  every predicate, function, and constant symbol. Tarski's recursion defines
  when a structure satisfies a formula under a variable assignment, and hence
  when a sentence is true. From satisfaction we recover logical implication,
  validity, and logical equivalence for first-order logic.
topics: [First-Order Languages and Structures]
sources:
  - book: Enderton
    ref: "Ch. 2 — First-Order Logic; §2.2 Truth and Models (satisfaction, logical implication)"
draft: false
---

A first-order language fixes which strings are
[terms, wffs, and sentences](/logic/first-order-languages/first-order-languages),
but none of it carries meaning. In
[sentential logic](/logic/sentential-logic/truth-assignments-and-tautologies) a
**truth assignment** supplied meaning by declaring which sentence symbols were
true. The first-order analogue is a **structure**, which does more: it names a
universe of objects and says what each parameter denotes over that universe.
From a structure, satisfaction of a formula and truth of a sentence are defined
in purely mathematical terms, without appeal to any English translation.

## Structures

A structure supplies two things: a domain for the quantifier to range over, and
a denotation for every parameter.[^struct]

> **Definition (Structure).** A structure $\fA$ for a language is a
> function on the parameters such that
>
> - $\fA$ assigns to $\forall$ a nonempty set $|\fA|$, the
>   **universe** (or domain);
> - to each $n$-place predicate symbol $P$, an $n$-ary relation
>   $P^{\fA} \subseteq |\fA|^n$;
> - to each constant symbol $c$, an element $c^{\fA} \in
>   |\fA|$;
> - to each $n$-place function symbol $f$, a total operation
>   $f^{\fA} : |\fA|^n \to |\fA|$.

Two requirements matter. The universe must be **nonempty**, since
$\forall$ ranging over nothing would make quantified sentences behave
strangely; and each $f^{\fA}$ must be **total**, defined on all of
$|\fA|^n$, with no provision for partial functions. We write a structure by
listing its components after the universe, as
$\fA = (|\fA|;\, P^{\fA}, f^{\fA},
c^{\fA}, \dots)$, suppressing that it is officially a function on
parameters. Distinguish carefully the function _symbol_ $f$, a piece of
syntax, from the operation $f^{\fA}$, a piece of the structure.

Two examples recur. First, take the language of set theory (only parameter
$\in$) and the structure with universe $\mathbb{N}$ and $\in^{\fA} =
\{\langle m, n\rangle : m < n\}$, reading membership as "less than." Second, take
the language with a two-place predicate $E$ and the finite structure
$\fB$ with universe $\{a, b, c, d\}$ and edge relation
$E^{\fB} = \{\langle a, b\rangle, \langle b, a\rangle, \langle b,
c\rangle, \langle c, c\rangle\}$, which we picture as a directed graph.

$$
% caption: The finite structure $\fB$ over $\{a,b,c,d\}$ with edge
% relation $E$; reading $E x y$ as "an edge runs from $x$ to $y$", vertex $d$ is
% the only one no edge points to.
\begin{tikzpicture}[font=\small, >=stealth,
  v/.style={draw, circle, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[v] (a) at (0,0)   {$a$};
  \node[v] (b) at (2.4,0) {$b$};
  \node[v] (c) at (4.8,0) {$c$};
  \node[v, draw=acc] (d) at (7.2,0) {$d$};
  \draw[->, bend left=18] (a) to (b);
  \draw[->, bend left=18] (b) to (a);
  \draw[->] (b) to (c);
  \draw[->] (c) to[out=35, in=-35, looseness=5] (c);
  \node[acc, font=\footnotesize] at (7.2,-1.1) {no edge in};
\end{tikzpicture}
$$

Under the set-theory structure the sentence $\exists x\, \forall y\, \neg\, y
\in x$ ("there is an empty set") translates to "there is a natural number than
which none is smaller," which is true, so $\fA$ is a **model** of that
sentence. Under $\fB$ the sentence $\exists x\, \forall y\, \neg\, y E
x$ asserts a vertex with no in-edge; it is true, witnessed by $d$. Intuition
settles these cases, but intuition is not a definition. We want "$\sigma$ is
true in $\fA$" as a mathematical statement — one that never routes
through an English translation or a private sense of which sentences are true.
(Try any such private sense on "this sentence is false.")

## Variable assignments and the value of a term

Because free variables have no fixed referent, truth is defined first for the
finer notion of satisfaction, which supplies temporary values for variables.

> **Definition (Variable assignment).** A function $s : V \to |\fA|$
> from the set $V$ of all variables into the universe.

An assignment names an object for every variable at once. From it we compute
the object each _term_ names, by extending $s$ to a function $\bar{s} : T \to
|\fA|$ on all terms.

> **Definition (Value of a term).** The extension $\bar{s}$ is defined by
> recursion:
>
> - $\bar{s}(x) = s(x)$ for a variable $x$;
> - $\bar{s}(c) = c^{\fA}$ for a constant symbol $c$;
> - $\bar{s}(f\, t_1 \cdots t_n) = f^{\fA}(\bar{s}(t_1), \dots,
>   \bar{s}(t_n))$.

The value climbs the term's formation tree: leaves get their values from $s$
or from the structure's constants, and each function symbol applies its
operation to the values already computed below it. A term with no function
symbols beyond constants is evaluated at its leaf directly.

$$
% caption: Evaluating the term $f f v_3$ in $\fA = (\mathbb{N};\, \le,
% S, 0)$ under $s(v_i) = i-1$, so $f$ is successor; values rise leaf-to-root
% $2$ then $3$ then $4$.
\begin{tikzpicture}[font=\small, level distance=13mm,
  every node/.style={draw, circle, inner sep=1.5pt, minimum size=7mm},
  edge from parent/.style={draw, black}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[label={[font=\footnotesize, acc]right:value $4$}] {$f$}
    child {node[label={[font=\footnotesize, acc]right:value $3$}] {$f$}
      child {node[label={[font=\footnotesize, acc]right:value $2$}] {$v_3$}}};
\end{tikzpicture}
$$

Here $\bar{s}(v_3) = s(v_3) = 2$, then $\bar{s}(f v_3) = S(2) = 3$, and
$\bar{s}(f f v_3) = S(3) = 4$. The value $\bar{s}(t)$ depends on both $s$ and
$\fA$; a notation displaying that dependence would be
$t^{\fA}[s]$.

## The satisfaction recursion

Satisfaction, written $\models_{\fA} \varphi[s]$, is defined by
recursion on $\varphi$. The informal reading anchors it: $\models_{\fA}
\varphi[s]$ holds iff the translation of $\varphi$ determined by $\fA$,
with each free variable $x$ read as $s(x)$, comes out true. The formal
definition does not depend on that reading.[^struct]

> **Definition (Satisfaction).** For a structure $\fA$ and assignment
> $s$:
>
> - **atomic, equality:** $\models_{\fA} {=}t_1 t_2\,[s]$ iff
>   $\bar{s}(t_1) = \bar{s}(t_2)$;
> - **atomic, predicate:** $\models_{\fA} P\, t_1 \cdots t_n\,[s]$ iff
>   $\langle \bar{s}(t_1), \dots, \bar{s}(t_n)\rangle \in P^{\fA}$;
> - **negation:** $\models_{\fA} \neg\, \varphi\,[s]$ iff **not**
>   $\models_{\fA} \varphi\,[s]$;
> - **conditional:** $\models_{\fA} (\varphi \rightarrow \psi)[s]$ iff
>   $\models_{\fA} \psi[s]$ whenever $\models_{\fA}
>   \varphi[s]$;
> - **universal:** $\models_{\fA} \forall x\, \varphi\,[s]$ iff for
>   every $d \in |\fA|$, $\models_{\fA} \varphi[s(x \mid d)]$.

The equality clause fixes $=$ as genuine identity in every structure, which is
why it is a logical symbol rather than a parameter open to interpretation. The
quantifier clause uses the **modified assignment**

$$
s(x \mid d)(y) =
\begin{cases}
s(y) & \text{if } y \neq x, \\
d & \text{if } y = x,
\end{cases}
$$

the function agreeing with $s$ everywhere except that it sends $x$ to $d$. So
$\forall x\, \varphi$ is satisfied exactly when $\varphi$ is satisfied no
matter which element of the universe we plug in for $x$. Like the value of a
term, satisfaction is well defined only because wffs have unique formation
trees; the recursion theorem then delivers a unique satisfaction relation.

### Satisfaction on the arithmetic structure

> **Worked example.** Take $\fA = (\mathbb{N};\, \le, S, 0)$ for the language
> with a two-place predicate $P$, one-place function $f$, and constant $c$,
> interpreted as $P^{\fA} = {\le}$, $f^{\fA} = S$, $c^{\fA} = 0$.
> Let $s(v_i) = i - 1$, so $s(v_1) = 0$, $s(v_2) = 1$, and so on. Check three
> formulas by running the recursion down to membership in ${\le}$.
>
> First, $\models_{\fA} P c\, f v_1\,[s]$. Evaluate the two terms: $\bar{s}(c) =
> c^{\fA} = 0$ and $\bar{s}(f v_1) = S(\bar{s}(v_1)) = S(0) = 1$. The atomic
> clause asks whether $\langle 0, 1\rangle \in {\le}$, which holds — the English
> reading is the true "$0 \le 1$." So $\models_{\fA} P c\, f v_1\,[s]$.
>
> Second, $\models_{\fA} \forall v_1\, P c v_1\,[s]$. The universal clause
> requires $\models_{\fA} P c v_1\,[s(v_1 \mid n)]$ for every $n \in \mathbb{N}$,
> which reduces to $\langle 0, n\rangle \in {\le}$, i.e. $0 \le n$. That holds
> for all $n$, so the sentence is satisfied.
>
> Third, $\models_{\fA} \neg\, \forall v_1\, P v_2 v_1\,[s]$. By the negation
> clause this holds iff $\forall v_1\, P v_2 v_1$ fails under $s$, i.e. iff some
> $m$ has $\langle s(v_2), m\rangle \notin {\le}$. Since $s(v_2) = 1$, take $m =
> 0$: $\langle 1, 0\rangle \notin {\le}$ because $1 \le 0$ is false. The
> existential witness exists, so the negation is satisfied.

The recursion reduces every question about a formula to membership questions
about the interpreted relations.

$$
% caption: The universal clause for $\forall v_1\, P c v_1$ on $(\mathbb{N};
% \le, S, 0)$ fans over every element $d$ of the universe; each branch reduces to
% the membership test $\langle 0, d\rangle \in {\le}$, which holds for all $d$, so
% the sentence is satisfied.
\begin{tikzpicture}[font=\small, >=stealth,
  rt/.style={draw, align=center, inner sep=4pt, font=\footnotesize},
  lf/.style={draw, align=center, inner sep=3pt, font=\footnotesize, minimum width=17mm}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[rt] (root) at (0,1.4) {true for all $v_1$: $P c\, v_1$};
  \node[lf] (d0) at (-4.2,-0.4) {$v_1 = 0$};
  \node[lf] (d1) at (-1.4,-0.4) {$v_1 = 1$};
  \node[lf] (d2) at (1.4,-0.4) {$v_1 = 2$};
  \node[font=\footnotesize, black] (dd) at (4.2,-0.4) {and so on};
  \foreach \d in {d0,d1,d2} \draw[->, black] (root) -- (\d);
  \draw[->, black] (root) -- (dd);
  \node[acc, font=\footnotesize] (c0) at (-4.2,-1.5) {holds};
  \node[acc, font=\footnotesize] (c1) at (-1.4,-1.5) {holds};
  \node[acc, font=\footnotesize] (c2) at (1.4,-1.5) {holds};
  \foreach \p/\q in {d0/c0,d1/c1,d2/c2} \draw[->, black] (\p) -- (\q);
\end{tikzpicture}
$$

The same mechanism runs on the finite graph $\fB$, where satisfaction turns
entirely on which pairs lie in the edge relation.

> **Worked example.** On the digraph $\fB$ with $|\fB| = \{a, b, c, d\}$ and
> $E^{\fB} = \{\langle a, b\rangle, \langle b, a\rangle, \langle b, c\rangle,
> \langle c, c\rangle\}$, find every $s$ satisfying $\forall v_2\, \neg\, E v_2
> v_1$ — "no edge points to $v_1$."
>
> The universal clause requires, for each $x \in |\fB|$, that $\neg\, E v_2
> v_1$ hold under $s(v_2 \mid x)$; the negation clause turns this into: no $x$
> has $\langle x, s(v_1)\rangle \in E^{\fB}$. Read off the in-edges of each
> vertex:
> $$
> a:\ \langle b, a\rangle;\qquad b:\ \langle a, b\rangle;\qquad
> c:\ \langle b, c\rangle,\ \langle c, c\rangle;\qquad d:\ \text{none}.
> $$
> Only $d$ has no incoming edge, so
> $$
> \models_{\fB} \forall v_2\, \neg\, E v_2 v_1\,[s]
> \quad\text{iff}\quad s(v_1) = d.
> $$
> Negating, $\models_{\fB} \exists v_2\, E v_2 v_1\,[s]$ iff $s(v_1) \in \{a, b,
> c\}$ — the vertices that some edge reaches. The formula $\exists v_2\, E v_2
> v_1$ thus defines the range of the edge relation.

## Dependencies of satisfaction

The assignment $s$ carries an infinite amount of information, a value for
every variable, yet a formula has only finitely many free variables. Only
those values can matter.

> **Theorem (Agreement on free variables).** If $s_1$ and $s_2$ agree on every
> variable that occurs free in $\varphi$, then $\models_{\fA}
> \varphi[s_1]$ iff $\models_{\fA} \varphi[s_2]$.

> **Proof.** Induction on $\varphi$. For atomic $\varphi = P t_1 \cdots t_n$
> every variable present occurs free, so $s_1$ and $s_2$ agree on all of them,
> forcing $\bar{s_1}(t_i) = \bar{s_2}(t_i)$ and hence the same satisfaction
> verdict. The connective cases are immediate from the inductive hypothesis. For
> $\varphi = \forall x\, \psi$, the free variables of $\varphi$ are those of
> $\psi$ except $x$; so for any $d$, the modified assignments $s_1(x \mid d)$ and
> $s_2(x \mid d)$ agree on all variables free in $\psi$, and the inductive
> hypothesis closes the case.

An analogous fact holds for structures: if $\fA$ and $\fB$ agree on the
parameters occurring in $\varphi$, they agree on whether $\varphi$ is satisfied.

Two consequences follow. When all free variables of $\varphi$ lie among $v_1,
\dots, v_k$, we may write

$$
\models_{\fA} \varphi[[a_1, \dots, a_k]]
$$

to mean $\fA$ satisfies $\varphi$ with some (equivalently, any)
assignment sending $v_i$ to $a_i$. And for a sentence, which has no free
variables, the choice of $s$ drops out entirely.

> **Corollary (Truth of a sentence).** For a sentence $\sigma$, either
> $\fA$ satisfies $\sigma$ with every assignment or with none. In the
> first case $\sigma$ is **true** in $\fA$, written
> $\models_{\fA} \sigma$, and $\fA$ is a **model** of
> $\sigma$; in the second, $\sigma$ is false in $\fA$.

The two cases are exhaustive and exclusive because the universe is nonempty.
A structure is a model of a _set_ $\Sigma$ of sentences iff it is a model of
each member. So "true in $\fA$" is now a mathematical property of the
pair $(\fA, \sigma)$, exactly as intended.

$$
% caption: The sentence $\exists x (x \cdot x = 1 + 1)$ holds in the real field
% $(\mathbb{R};\, 0, 1, +, \cdot)$ — a square root of $2$ exists — and fails in
% the rational field $(\mathbb{Q};\, 0, 1, +, \cdot)$, where none does; one
% sentence separates the two structures.
\begin{tikzpicture}[font=\small,
  b/.style={draw, minimum width=42mm, minimum height=20mm, align=center}]
  \definecolor{acc}{HTML}{4A6FA5}
  \definecolor{red}{HTML}{C0392B}
  \node[b, draw=acc] (r) at (0,0) {the reals $\mathbb{R}$\\with plus and times};
  \node[b, draw=red] (q) at (6.2,0) {the rationals $\mathbb{Q}$\\with plus and times};
  \node[acc, font=\footnotesize] at (0,-1.55) {a model of the sentence};
  \node[red, font=\footnotesize] at (6.2,-1.55) {not a model};
\end{tikzpicture}
$$

## Logical implication

With truth defined, the central semantic relation transfers from sentential
logic almost verbatim.

> **Definition (Logical implication).** A set $\Gamma$ of wffs **logically
> implies** $\varphi$, written $\Gamma \models \varphi$, iff every structure
> $\fA$ and assignment $s$ that satisfies every member of $\Gamma$
> also satisfies $\varphi$.

We reuse the symbol $\models$ from
[tautological implication](/logic/sentential-logic/truth-assignments-and-tautologies),
but from now on it means logical implication. Two derived notions come with
it. Formulas $\varphi$ and $\psi$ are **logically equivalent** ($\varphi
\mathbin{\models\!\mid} \psi$) iff each logically implies the other. A wff
$\varphi$ is **valid**, written $\models \varphi$, iff $\varnothing \models
\varphi$ — satisfied by every structure under every assignment, the
first-order counterpart of a tautology. For sentences the quantifier over
assignments collapses:

> **Corollary (Implication for sentences).** For sets of sentences, $\Gamma
> \models \tau$ iff every model of $\Gamma$ is a model of $\tau$; and $\tau$ is
> valid iff it is true in every structure.

A few valid implications can be checked directly against the definition:

| Claim | Why |
| --- | --- |
| $\forall v_1\, Q v_1 \models Q v_2$ | if $Q$ holds of everything, it holds of the value of $v_2$ |
| $Q v_1 \not\models \forall v_1\, Q v_1$ | a two-element universe with $Q$ holding of one point refutes it |
| $\models \neg\, \neg\, \sigma \rightarrow \sigma$ | double negation, proved in the metalanguage |
| $\forall v_1\, Q v_1 \models \exists v_2\, Q v_2$ | the universe is nonempty |
| $\exists x\, \forall y\, P x y \models \forall y\, \exists x\, P x y$ | one witness $x$ serves every $y$ |
| $\forall y\, \exists x\, P x y \not\models \exists x\, \forall y\, P x y$ | the witness may vary with $y$ |

These definitions echo the sentential ones but differ sharply in difficulty.
Deciding whether a sentential wff is a tautology means checking finitely many
truth assignments, each a finite object, so tautologyhood is
[decidable](/logic/sentential-logic/compactness-and-effectiveness). Deciding
whether a first-order wff is valid means quantifying over every structure:
every nonempty set, with every interpretation of the parameters, and for
infinite universes every assignment. Validity is in fact
[undecidable](/logic/incompleteness/incompleteness-and-undecidability). The
[deductive calculus](/logic/deductive-calculus/a-deductive-calculus) shows that
this semantic notion nonetheless coincides with a syntactic one, deducibility,
whose definition is nearly finitary.

## Syntax and semantics

It helps to keep straight which notions are syntactic and which are semantic;
they are defined by different means and later shown to match.

| Notion | Level | Defined by |
| --- | --- | --- |
| term, wff, sentence, free variable | syntax | recursion on strings |
| structure $\fA$ | semantics | function on parameters |
| value $\bar{s}(t)$, satisfaction $\models_{\fA} \varphi[s]$ | semantics | recursion, using $\fA$ |
| truth $\models_{\fA} \sigma$, model of $\Sigma$ | semantics | satisfaction by all/any $s$ |
| logical implication $\Gamma \models \varphi$, validity | semantics | quantify over all $\fA, s$ |

Satisfaction is the hinge, with syntax on one side and the interpreting
structure on the other. Holding the structure fixed and varying the formula
asks which subsets and relations of a universe a formula can
[pick out](/logic/first-order-languages/definability-and-elementary-equivalence);
holding a set of sentences fixed and varying the structure asks when two
structures satisfy exactly the same sentences.

[^struct]: Enderton, §2.2 — structures as interpretations of the parameters, variable assignments and the recursive value of a term, Tarski's recursive definition of satisfaction, the agreement theorem on free variables, truth of a sentence, and the definitions of logical implication, validity, and logical equivalence.