Model Interpretation and Satisfaction

Graduate Depth 9 in the knowledge graph I know this Set as goal
Unlocks 73 downstream topics
semantics satisfaction truth Tarski valuation

Core Idea

Satisfaction formalizes what it means for a formula to be true in a structure through recursive definition: atomic formulas are satisfied by checking the actual interpretation; logical connectives and quantifiers are evaluated inductively. A model of a set of sentences is a structure in which all sentences are satisfied. This Tarskian framework unifies logic and mathematics under a single unified notion of truth.

Explainer

From your study of first-order semantics, you know that a structure provides the raw material for evaluating first-order formulas: a non-empty domain, an assignment of domain elements to constant symbols, functions on the domain to function symbols, and relations on the domain to predicate symbols. Model theory's central question is: when exactly does a formula become *true* in a given structure? Tarski's satisfaction relation, written M ⊨ φ, gives a precise, recursive answer.

The definition proceeds in two stages. For atomic formulas — the simplest kind, like P(a) or a = b — satisfaction is checked directly against the interpretation. P(a) is satisfied in M iff the element that a denotes in M is in the set that P denotes in M. This is just checking a fact about the structure itself: does the named object have the named property? There is no logical decomposition to do; truth is read off from the model.

For compound formulas, satisfaction is defined inductively by the outermost connective or quantifier. M ⊨ ¬φ iff M does not satisfy φ. M ⊨ φ ∧ ψ iff M satisfies both φ and ψ. M ⊨ ∃x φ(x) iff there exists at least one element d in the domain such that the structure with x assigned to d satisfies φ. M ⊨ ∀x φ(x) iff every element d in the domain satisfies φ when x is assigned to d. Each clause reduces the truth of a complex formula to truth of simpler subformulas, until atomic cases are reached.

A common confusion is between satisfiability and validity. Saying M ⊨ φ (φ is true in the specific structure M) is different from saying ⊨ φ (φ is true in *every* structure — it is logically valid). A sentence can be true in some structures and false in others. A theory T is a set of sentences; M is a model of T when M ⊨ φ for every φ in T. The existence of a model witnesses that T is consistent — since contradiction is false in every structure, a model shows T cannot derive contradiction.

This framework is more powerful than it first appears. By varying what a structure looks like while holding sentences fixed, or by varying sentences while holding a structure fixed, you can ask questions like: do two structures satisfy exactly the same sentences? Does a theory have a model of every infinite cardinality? These are the questions that drive the deeper theorems of model theory — but they all rest on Tarski's foundational definition of what it means for a formula to be satisfied in a structure.

Practice Questions 3 questions

Prerequisite Chain

Longest path: 10 steps · 33 total prerequisite topics

Prerequisites (7)

Leads To (10)