Models & Satisfaction

When a structure satisfies a sentence, and building models to test it.

The idea

A structure gives the symbols of a first-order language their meaning, and satisfaction is the relation between a structure and the sentences true in it. A formula by itself is pure syntax: $P(x, y)$ asserts nothing until we say what $P$ means and what $x$ and $y$ range over.

A structure $\mathcal{M}$ consists of a nonempty set, its domain, together with an interpretation of every symbol: each constant symbol names an element of the domain, each function symbol becomes a function on the domain, and each predicate symbol becomes a relation — for a two-place $P$, the set of ordered pairs on which $P$ holds.

With every symbol interpreted, we evaluate a sentence from the inside out. The quantifiers range over the domain: $\forall x\,\varphi$ is true when $\varphi$ holds of every element, and $\exists x\,\varphi$ when it holds of at least one. When the sentence comes out true we write $\mathcal{M} \models \varphi,$ read as $\mathcal{M}$ satisfies $\varphi$, and call $\mathcal{M}$ a model of $\varphi$.

Truth in first-order logic is always truth in a structure: one structure can satisfy a sentence that another refutes.

Ways to work on it

• Walkthrough. Read a structure and evaluate quantified sentences in it.
• Practice. Decide whether a quantified sentence is true in a small structure.
• Hardest. Use validity and build a countermodel for a quantifier-swap.

Not sure where to start? Take the ten-question placement test.