Models and Interpretations

A formula of first-order logic — say \forall x\,\exists y\,(x < y) — is, on its own, just a string of symbols. It has no truth value yet. The symbol < could mean "less than", "divides", "is an ancestor of", or nothing at all. To turn syntax into a genuine truth we must say what world we are talking about: what things exist, and what the symbols mean in that world. That is exactly what a structure (also called an interpretation or a model) does — and it is the bridge from syntax (the marks on the page) to semantics (their meaning).

The wonderful, slightly unsettling consequence: the same axioms can describe wildly different worlds. One list of first-order sentences might be true of the integers, of a clock face, of a family tree, and of some structure nobody has ever pictured — all at once. This page is about the machine that decides, given a world and a sentence, whether the sentence comes out true there.

Signature: the symbols we get to interpret

Before we can build a world we must fix the signature (or language) \sigma — the list of non-logical symbols we are allowed to use. There are three kinds:

Constant symbols (e.g. 0, 1) — names for particular elements;
Function symbols (e.g. +, \cdot), each with an arity (how many inputs it takes);
Relation / predicate symbols (e.g. <, =), again each with an arity.

The logical furniture — variables x, y, z, the connectives \land, \lor, \lnot, \rightarrow, the quantifiers \forall, \exists, and equality — is fixed and means the same thing everywhere. Only the signature symbols are up for interpretation.

What a structure actually is

A structure \mathcal{M} for a signature \sigma is a non-empty domain M (the "universe", the things that exist) together with an interpretation of every symbol in \sigma:

each constant c is assigned an element c^{\mathcal{M}} \in M;
each n-ary function symbol f is assigned an actual function f^{\mathcal{M}} : M^n \to M;
each n-ary relation symbol R is assigned an actual relation R^{\mathcal{M}} \subseteq M^n — the set of tuples for which it holds.

The domain must be non-empty (classical first-order logic assumes at least one thing exists, so \exists x\,(x = x) is always true). Notice the careful distinction: < is a symbol; <^{\mathcal{M}} is a set of pairs living inside the structure. Confusing the two is the classic beginner's slip — more on that below.

A structure \mathcal{M} for a signature \sigma consists of:

a non-empty domain M;
an element c^{\mathcal{M}} \in M for each constant c;
a function f^{\mathcal{M}} : M^n \to M for each n-ary function symbol f;
a relation R^{\mathcal{M}} \subseteq M^n for each n-ary relation symbol R.

From a structure to a truth value: satisfaction

A structure interprets the symbols, but a formula can also have free variables (like the x in x < y). To pin those down we add a variable assignment s, a function sending each variable to an element of the domain. Given \mathcal{M} and s, every term names an element and every formula gets a truth value, built up piece by piece:

an atomic formula R(t_1,\dots,t_n) is true iff the tuple of values (t_1^{\mathcal{M}},\dots,t_n^{\mathcal{M}}) lies in R^{\mathcal{M}};
\lnot\varphi, \varphi \land \psi, … get their truth values from the usual truth tables;
\forall x\,\varphi is true iff \varphi holds for every choice of element for x; \exists x\,\varphi iff it holds for at least one.

We write \mathcal{M} \models \varphi[s] — read "\mathcal{M} satisfies \varphi under the assignment s", or "\mathcal{M} models \varphi". That double turnstile \models is the central symbol of the whole subject: it is the satisfaction relation, the formal answer to "is this formula true here?"

When \varphi is a sentence — a formula with no free variables, every variable bound by a quantifier — the assignment s makes no difference. Then we simply write \mathcal{M} \models \varphi and say \varphi is true in \mathcal{M}. A sentence is flatly true or false in a given structure; an open formula only becomes true-or-false once you also fix its free variables.

Worked example: one sentence, two worlds

Fix the tiny signature \sigma = \{<\} with a single binary relation symbol, and the sentence

\varphi \;:\; \forall x\,\exists y\,(x < y)

In words: "every element has something strictly larger". Whether \varphi is true depends entirely on the structure.

World A — the integers. Take \mathcal{Z} = (\mathbb{Z}, <): domain \mathbb{Z}, and < interpreted as the usual ordering. Given any integer x, the integer y = x+1 is larger. So there is always a witness, and \mathcal{Z} \models \varphi. True.

World B — a finite line. Take \mathcal{F} = (\{0,1,2\}, <): the same symbol <, but now over a three-element domain. The element 2 is the top — there is no y in the domain with 2 < y. So the "every" fails at x = 2, and \mathcal{F} \not\models \varphi. False.

Same signature, same sentence, opposite verdicts — because the worlds differ. That is the whole point of semantics: truth is relative to a structure. The figure below lets you watch the sentence being checked, arrow by arrow, in a small finite world.

Satisfiable, valid, unsatisfiable

Once we can ask "true in this structure?", three global properties fall out by ranging over all structures. For a sentence \varphi:

\varphi is satisfiable if it is true in some structure — at least one world makes it work.
\varphi is valid (a logical truth) if it is true in every structure — no world can make it fail. We write \models \varphi.
\varphi is unsatisfiable (a contradiction) if it is true in no structure.

These are not independent: \varphi is valid exactly when \lnot\varphi is unsatisfiable, and satisfiable exactly when \lnot\varphi is not valid. Our example \forall x\,\exists y\,(x < y) is satisfiable (true in \mathbb{Z}) but not valid (false in the three-point world). By contrast \forall x\,(x = x) is valid — true in absolutely every structure — while \exists x\,(x \ne x) is unsatisfiable.

A structure \mathcal{M} is a model of a set of sentences \Sigma if \mathcal{M} \models \varphi for every \varphi \in \Sigma.
\varphi is satisfiable iff it has at least one model; unsatisfiable iff it has none.
\varphi is valid (\models \varphi) iff every structure is a model — iff \lnot\varphi is unsatisfiable.

Models of a set of axioms

Most interesting mathematics packages several sentences together as axioms. A model of a set \Sigma is a single structure that satisfies all of them at once. Consider the signature \sigma = \{\,<\,\} and the axioms for a strict linear order:

\forall x\,\lnot(x < x), \qquad \forall x\,\forall y\,\forall z\,\big((x < y \land y < z) \rightarrow x < z\big), \qquad \forall x\,\forall y\,\big(x \ne y \rightarrow (x < y \lor y < x)\big).

The integers (\mathbb{Z}, <), the rationals, the reals, and our finite (\{0,1,2\}, <) are all models of these three axioms — utterly different sizes and shapes of world, yet each satisfies every axiom. Add a fourth sentence like \forall x\,\exists y\,(x < y) and you carve the finite orders away, keeping only the ones with no greatest element. This is how logic sculpts a class of structures out of the space of all possible worlds: each axiom is a cut.

The single most common confusion in a first logic course is blurring these two:

Satisfiable = true in some structure (there exists a model). A low bar — one lucky world is enough.
Valid = true in every structure (all models). A very high bar — no world may escape.

Every valid sentence is satisfiable, but the reverse fails badly: \exists x\,\exists y\,(x \ne y) is satisfiable (any two-element world works) yet not valid (a one-element world refutes it). If you find yourself proving "it's true in this example, therefore it's valid" — stop. One example shows only satisfiability. To show validity you must argue about every structure; to refute validity you need just one counter-structure, exactly as a single counterexample kills a universal claim.

A structure teaches you to hold the symbol and its interpretation apart. Nothing forces the constant symbol 0 to denote the number zero, or < to mean "less than". You could build a perfectly legal structure on the domain \{\text{cat}, \text{dog}\} where 0^{\mathcal{M}} = \text{cat} and <^{\mathcal{M}} = \{(\text{cat}, \text{dog})\}.

The symbols are just ink until a structure breathes meaning into them. This freedom is precisely what makes the same axioms describe so many different worlds — and it is why the completeness and compactness theorems, later in this course, can conjure up structures you never intended. Keep the ink (syntax) and the meaning (semantics) in separate hands and first-order logic stops feeling slippery.