Structures, Truth, and Satisfaction

A first-order language fixes which strings are terms, wffs, and sentences, but none of it carries meaning. In sentential logic 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.¹

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

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

The finite structure

B

over

{a, b, c, d}

with edge relation

E

; reading

E x y

as "an edge runs from

x

y

", vertex

d

is the only one no edge points to.

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 $A$ is a model of that sentence. Under $B$ 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 $σ$ is true in $A$ 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.

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 $\overset{s}{ˉ} : T \to ∣ A ∣$ on all terms.

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.

Evaluating the term

f f v_{3}

A = (N; \leq, S, 0)

under

s (v_{i}) = i - 1

, so

f

is successor; values rise leaf-to-root

2

then

3

then

4

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

The satisfaction recursion

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

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 ∣ d) (y) = {s (y) d if y \neq = x, if y = x,

the function agreeing with $s$ everywhere except that it sends $x$ to $d$ . So $\forall x φ$ is satisfied exactly when $φ$ 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 $A = (N; \leq, S, 0)$ for the language with a two-place predicate $P$ , one-place function $f$ , and constant $c$ , interpreted as $P^{A} = \leq$ , $f^{A} = S$ , $c^{A} = 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 $\leq$ .

First, $⊨_{A} P c f v_{1} [s]$ . Evaluate the two terms: $\overset{s}{ˉ} (c) = c^{A} = 0$ and $\overset{s}{ˉ} (f v_{1}) = S (\overset{s}{ˉ} (v_{1})) = S (0) = 1$ . The atomic clause asks whether $⟨ 0, 1 ⟩ \in \leq$ , which holds — the English reading is the true $0 \leq 1$ . So $⊨_{A} P c f v_{1} [s]$ .

Second, $⊨_{A} \forall v_{1} P c v_{1} [s]$ . The universal clause requires $⊨_{A} P c v_{1} [s (v_{1} ∣ n)]$ for every $n \in N$ , which reduces to $⟨ 0, n ⟩ \in \leq$ , i.e. $0 \leq n$ . That holds for all $n$ , so the sentence is satisfied.

Third, $⊨_{A} \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 $⟨ s (v_{2}), m ⟩ \in / \leq$ . Since $s (v_{2}) = 1$ , take $m = 0$ : $⟨ 1, 0 ⟩ \in / \leq$ because $1 \leq 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.

The universal clause for

\forall v_{1} P c v_{1}

(N; \leq, S, 0)

fans over every element

d

of the universe; each branch reduces to the membership test

⟨ 0, d ⟩ \in \leq

, which holds for all

d

, so the sentence is satisfied.

The same mechanism runs on the finite graph $B$ , where satisfaction turns entirely on which pairs lie in 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.

An analogous fact holds for structures: if $A$ and $B$ agree on the parameters occurring in $φ$ , they agree on whether $φ$ is satisfied.

Two consequences follow. When all free variables of $φ$ lie among $v_{1}, \dots, v_{k}$ , we may write

⊨_{A} φ [[a_{1}, \dots, a_{k}]]

to mean $A$ satisfies $φ$ 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.

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

The sentence

\exists x (x \cdot x = 1 + 1)

holds in the real field

(R; 0, 1, +, \cdot)

— a square root of

2

exists — and fails in the rational field

(Q; 0, 1, +, \cdot)

, where none does; one sentence separates the two structures.

Logical implication

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

We reuse the symbol $⊨$ from tautological implication, but from now on it means logical implication. Two derived notions come with it. Formulas $φ$ and $ψ$ are logically equivalent ( $φ ⊨ ∣ ψ$ ) iff each logically implies the other. A wff $φ$ is valid, written $⊨ φ$ , iff $\emptyset ⊨ φ$ — satisfied by every structure under every assignment, the first-order counterpart of a tautology. For sentences the quantifier over assignments collapses:

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

Claim	Why
$\forall v_{1} Q v_{1} ⊨ Q v_{2}$	if $Q$ holds of everything, it holds of the value of $v_{2}$
$Q v_{1} \neq ⊨ \forall v_{1} Q v_{1}$	a two-element universe with $Q$ holding of one point refutes it
$⊨ \neg \neg σ \to σ$	double negation, proved in the metalanguage
$\forall v_{1} Q v_{1} ⊨ \exists v_{2} Q v_{2}$	the universe is nonempty
$\exists x \forall y P x y ⊨ \forall y \exists x P x y$	one witness $x$ serves every $y$
$\forall y \exists x P x y \neq ⊨ \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. 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. The 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 $A$	semantics	function on parameters
value $\overset{s}{ˉ} (t)$ , satisfaction $⊨_{A} φ [s]$	semantics	recursion, using $A$
truth $⊨_{A} σ$ , model of $Σ$	semantics	satisfaction by all/any $s$
logical implication $Γ ⊨ φ$ , validity	semantics	quantify over all $A, 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; holding a set of sentences fixed and varying the structure asks when two structures satisfy exactly the same sentences.

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. ↩ ↩²

Structures

Variable assignments and the value of a term

The satisfaction recursion

Satisfaction on the arithmetic structure

Dependencies of satisfaction

Logical implication

Syntax and semantics

Footnotes