A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A first-order structure (or interpretation) for a signature consists of a non-empty domain D and an assignment of: each constant to an element of D, each n-ary function symbol to an n-ary function on D, and each n-ary predicate symbol to an n-ary relation on D. A variable assignment maps each variable to a domain element. Satisfaction (M, s ⊨ φ) is defined recursively: atomic formulas by checking relations, Boolean connectives compositionally, and quantifiers by ranging over all domain elements. A sentence is true in M (written M ⊨ φ) if it is satisfied under any variable assignment.
Work through small finite structures (sets of 2–4 elements) and evaluate FOL sentences by hand. Verify that the same formula can be true in one structure and false in another to build intuition for model-dependence.
The satisfaction relation (M, s ⊨ φ) was formalized by Alfred Tarski in the 1930s, giving logic a rigorous compositional semantics. The approach here — structures, domains, variable assignments — is standard across model theory, database theory (where relations in a database are exactly first-order structures), and formal verification.
First-order logic syntax gives you a language — variables, constants, predicate symbols, quantifiers — but syntax alone doesn't tell you what sentences *mean*. Semantics is the bridge between symbols and meaning: it defines what it takes for a formula to be *true* in a given context. That context is called a structure (or interpretation).
A structure M for a given signature has two parts. First, a non-empty domain D — the set of objects the variables will range over. Second, an interpretation function that assigns meaning to every symbol: each constant is assigned a specific element of D, each function symbol is assigned a function on D, and each predicate symbol is assigned a relation on D. Nothing in the syntax forces the domain to be the natural numbers or any familiar set — a structure for arithmetic could have domain {●, ▲, ■} if you wanted. The domain is your choice.
Given a structure, satisfaction is defined recursively. An atomic formula like P(x, y) is satisfied when the pair (s(x), s(y)) — where s is the current variable assignment — falls inside the relation interpreting P. Boolean connectives work compositionally: φ ∧ ψ is satisfied when both are. Quantifiers are where the semantics becomes truly powerful: ∃x φ(x) is satisfied when *some* element of D satisfies φ when assigned to x; ∀x φ(x) is satisfied when *every* element does. This means evaluating a universally quantified sentence requires, in principle, checking every domain element.
The key philosophical payoff is model-dependence: the same sentence can be true in one structure and false in another. The sentence ∀x∀y (x = y) is true in any one-element structure and false in any structure with two or more elements. A model of a sentence φ is simply a structure M such that M ⊨ φ. Model theory — the study of which structures satisfy which sentences — grows directly from these definitions. When you move on to soundness and completeness theorems, you will be asking exactly whether the provability relation and the satisfaction relation track each other.
A common stumbling block is confusing the domain with some canonical set. In practice, textbook examples often use ℕ or ℝ because they are familiar, but this is purely for convenience. Another stumbling block is handling variables: a formula with free variables (like P(x)) isn't true or false on its own — it is satisfied (or not) relative to a specific variable assignment. Only sentences — formulas with no free variables — have a definite truth value in a structure independent of any assignment.