Mathematics
Model Theory Basics: Satisfaction, Consistency, and Completeness
Quick fact
In model theory, a structure can satisfy a statement even if that statement is not provable in a formal system. For example, a countably infinite structure can satisfy statements that imply the existence of uncountable sets, a phenomenon known as Skolem's paradox.
Why this is interesting
Imagine a formal language as a set of rules for building 'sentences.' How do we decide whether those sentences are actually true? In model theory, truth is not about the world—it's about a specific structure.
Read the full explanation
Understanding Model Theory Basics: Satisfaction, Consistency, and Completeness
Think of a formal language as a game where you have a set of symbols and rules (like chess pieces and moves). A 'sentence' is a well-formed expression that could be true or false in a particular 'universe'—but only when we assign meaning to the symbols. That assignment is called an 'interpretation' or 'structure': it specifies a set of objects (the domain) and gives fixed meanings to the symbols (e.g., a relation < on the domain). Now, a sentence is 'satisfied' by a structure if, when we replace the symbols with their interpretations, the sentence becomes a true statement about that domain. For example, the sentence "∀x ∃y (y x)" is satisfied by the natural numbers with the usual order, because for every natural number, there is a larger one. If we switched the domain to the integers, the sentence would still be satisfied; but if we used a finite set, it would be false. So satisfaction is the bridge between syntax (the formal sentence) and semantics (the domain).
A deeper explanation
Now, a 'theory' is just a set of sentences. A theory is 'consistent' if there is at least one structure that satisfies all its sentences—we say that structure is a 'model' of the theory. If no structure can satisfy all the sentences together, the theory is inconsistent. This is different from 'proof-theoretic consistency' (no contradiction can be derived), but by Gödel's completeness theorem, the two notions coincide for first-order logic: a theory has a model if and only if it is consistent in the formal sense of derivations. The property of 'completeness' belongs to the logic itself, not to a particular theory: a logic is complete if every sentence that is true in every model of a theory can be proven from that theory. First-order logic is complete (Gödel, 1930). But that doesn't mean every theory is complete: a theory is incomplete if there is a sentence that is true in some models and false in others, so neither it nor its negation follows. Recognizing these layers is key: satisfaction is a relation between a structure and a sentence; consistency is a property of a set of sentences with respect to existence of a model; completeness is a property of the logical system relating semantic truth to syntactic proof. Understanding these distinctions reveals the interplay between meaning and syntax, and sets the stage for the limitations of formal methods, such as Gödel's incompleteness theorems.