# Interpretation (logic)
In logic, an interpretation is the semantic structure that gives meaning to a formal language: it fixes a domain of objects and assigns each non-logical symbol of the language, such as constants, function symbols, and predicate symbols, a concrete denotation over that domain. Once an interpretation is fixed, every sentence of the language receives a definite truth value, and the central semantic notions of validity, satisfiability, and logical consequence are defined in terms of interpretations.[1](https://slc.openlogicproject.org/slc-print.pdf)
| Key fact | Detail |
|---|---|
| Components | An interpretation specifies a domain D, a mapping of constants to elements of D, a mapping of each n-argument predicate symbol to a relation on Dn, and a mapping of each n-argument function symbol to a function from Dn to D[2](https://www.cse.iitb.ac.in/~cs717/notes/classNotes/LectureNotes-16-20.pdf) |
| Terminology | The same notion appears in the literature as "structure," "interpretation," or "model"; some authors reserve "structure" for the domain plus the mappings, distinguished from the vocabulary[1](https://slc.openlogicproject.org/slc-print.pdf) • [2](https://www.cse.iitb.ac.in/~cs717/notes/classNotes/LectureNotes-16-20.pdf) |
| Model | An interpretation under which a formula evaluates to true is called a model for that formula[3](https://www.usna.edu/Users/cs/wcbrown/courses/F23SI242/lec/l13/lec.html) |
| Validity and satisfiability | A formula is valid, written \( \models \phi \), iff every interpretation satisfies it; it is satisfiable iff some interpretation satisfies it[4](https://tarski.readthedocs.io/en/stable/notebooks/first-order-logics.html) |
| Undecidability | Determining whether a first-order sentence is valid, or satisfiable, is undecidable; the negative answers date to Church and Turing in 1936 (satisfiability) and Trakhtenbrot in 1950 (finite satisfiability)[4](https://tarski.readthedocs.io/en/stable/notebooks/first-order-logics.html) • [5](https://research.manchester.ac.uk/en/publications/fragments-of-first-order-logic/) |
| Historical source | Alfred Tarski's 1933 truth definition covered fully interpreted languages, and the 1956 revision with Robert Vaught serves as a truth definition for model-theoretic languages[6](https://plato.sydney.edu.au/entries//////////tarski-truth/) |
## What an interpretation contains
Formally, an interpretation in predicate logic is a specification of four things: a domain D, which must be a non-empty set; a mapping of each constant symbol to an element of D; a mapping of each n-argument predicate symbol to a relation on Dn, where Dn is the n-fold Cartesian product of D with itself; and a mapping of each n-argument function symbol to a function from Dn to D.[2](https://www.cse.iitb.ac.in/~cs717/notes/classNotes/LectureNotes-16-20.pdf) The domain is what the quantifiers range over and what the variables take their values from.[1](https://slc.openlogicproject.org/slc-print.pdf)
A small example shows how the mappings fix truth values. Take the formal sentence \( \mathrm{Likes}(\mathrm{fred}, \mathrm{bananas}) \), built from a predicate symbol and two constant symbols. An interpretation first identifies a domain of objects, then associates the constant symbols with particular objects in that domain, and finally associates the predicate symbol with a concrete relation. The atomic sentence is true exactly when the ordered pair of objects denoted by the two constants belongs to the relation assigned to the predicate symbol; in the textbook example the pair is not in the relation, so the sentence is false under that interpretation.[2](https://www.cse.iitb.ac.in/~cs717/notes/classNotes/LectureNotes-16-20.pdf)
The same formal language can receive many different interpretations. For the sentence \( \forall x\,[\neg P(f(x), c)] \), one interpretation over the domain \(\{1, 2, 3\}\) makes it true, an interpretation over \(\{\mathrm{dog}, \mathrm{cat}\}\) makes it false, and an interpretation over the integers with \( P(a,b) \) read as \( a < b \), \( f(a) \) as \( a^2 \), and \( c \) as 0 makes it say that no square of an integer is negative, which is true. Verifying truth under a finite interpretation proceeds by checking each domain element in turn, while refuting it requires only a single counterexample.[3](https://www.usna.edu/Users/cs/wcbrown/courses/F23SI242/lec/l13/lec.html)
## Terminology: structure, interpretation, model
Textbooks do not use one uniform name for this notion. The Open Logic Project notes that structures are "variously called 'structures,' 'interpretations,' or 'models' in the literature."[1](https://slc.openlogicproject.org/slc-print.pdf) Some authors, when they use "structure," distinguish the vocabulary, meaning the constants, function symbols, and predicate symbols, from the structure itself, meaning the domain together with the three mappings; retaining "interpretation" keeps continuity with propositional logic, where an interpretation simply assigns truth values to variables.[2](https://www.cse.iitb.ac.in/~cs717/notes/classNotes/LectureNotes-16-20.pdf) In propositional logic, an interpretation under which a formula evaluates to true is called a model, and the same terminology carries over to first-order formulas.[3](https://www.usna.edu/Users/cs/wcbrown/courses/F23SI242/lec/l13/lec.html)
Many-sorted versions of the definition assign a separate universe \( \mathcal{U}_{\tau} \) to each sort \( \tau \), interpret each n-ary function symbol of type \( (\tau_1, \ldots, \tau_n, \tau_{n+1}) \) as a function \( \mathcal{U}_{\tau_1} \times \cdots \times \mathcal{U}_{\tau_n} \to \mathcal{U}_{\tau_{n+1}} \), and interpret each n-ary predicate symbol as a subset of the corresponding product of universes; a constant symbol of type \( \tau \) is interpreted as an element of \( \mathcal{U}_{\tau} \).[7](https://tarski.readthedocs.io/en/latest/notebooks/first-order-logics.html)
## Satisfaction and truth
The bridge between interpretations and formulas is the satisfaction relation. Because formulas may contain free variables, truth is defined relative to a variable assignment, a function mapping each free variable to an element of the appropriate universe. The assignment extends to a denotation function on all terms: a variable denotes whatever the assignment gives it, and a compound term \( f(t_1, \ldots, t_n) \) denotes the result of applying the interpreted function \( f^{\mathcal{M}} \) to the denotations of its arguments.[4](https://tarski.readthedocs.io/en/stable/notebooks/first-order-logics.html)
Satisfaction is then defined by induction on the structure of the formula, using the truth tables for the connectives and clauses for the quantifiers: \( \mathcal{M} \models (\exists x)\,\phi(\sigma) \) holds iff \( \phi \) is satisfied under some assignment that changes only x, and \( \mathcal{M} \models (\forall x)\,\phi(\sigma) \) iff it is satisfied under every such assignment.[4](https://tarski.readthedocs.io/en/stable/notebooks/first-order-logics.html) • [1](https://slc.openlogicproject.org/slc-print.pdf) For a sentence, one with no free variables, the variable assignment is irrelevant, so sentences are simply satisfied or not in a structure.[1](https://slc.openlogicproject.org/slc-print.pdf)
On this basis the standard semantic notions are defined. A sentence is valid, \( \models \phi \), if every structure satisfies it; it is entailed by a set of sentences \( \Gamma \), written \( \Gamma \models \phi \), if every structure satisfying all sentences of \( \Gamma \) also satisfies \( \phi \); and a set of sentences is satisfiable if some structure satisfies all of them at once.[1](https://slc.openlogicproject.org/slc-print.pdf) An interpretation under which a formula comes out true is a model of that formula.[3](https://www.usna.edu/Users/cs/wcbrown/courses/F23SI242/lec/l13/lec.html)
## Historical development
The modern model-theoretic notion descends from [Alfred Tarski](https://www.edgepedia.org/alfred-tarski)'s work on truth. In 1933 Tarski published, in Polish, an analysis of what a definition of "true sentence" for a formal language should satisfy, together with examples of such definitions; the languages he considered there were fully interpreted, meaning every sentence already had a determinate meaning. In 1956 he and his colleague Robert Vaught published a revision of one of the 1933 definitions to serve as a truth definition for model-theoretic languages, in which meanings are supplied by structures rather than fixed in advance.[6](https://plato.sydney.edu.au/entries//////////tarski-truth/) Tarski's definition proceeds through a separate notion of satisfaction, which is then used to define truth.[8](https://milnepublishing.geneseo.edu/concise-introduction-to-logic/chapter/17-some-advanced-topics-in-logic/)
The metalogical theorems of the 1930s fixed the powers and limits of interpretations in first-order logic. [Kurt Gödel](https://www.edgepedia.org/kurt-godel) proved in 1930 that first-order logic is complete, in the sense that every sentence true under every interpretation is derivable within the logic.[9](https://plato.stanford.edu/archives/win2025/entries/realism-sem-challenge/model-theory-completeness.html) The satisfiability problem, asking whether a given sentence is true in some structure, was shown undecidable in 1936 by Church and Turing, and the finite satisfiability problem by Trakhtenbrot in 1950.[5](https://research.manchester.ac.uk/en/publications/fragments-of-first-order-logic/)
## What interpretations can and cannot distinguish
Two theorems describe the range of models a set of sentences can have. The downward [Löwenheim–Skolem theorem](https://www.edgepedia.org/lowenheim-skolem-theorem) states that a satisfiable set of sentences of a language with finitely or denumerably many non-logical constants has an equivalent model whose domain is finite or denumerably infinite; the upward theorem, a corollary of compactness, guarantees arbitrarily large models for any satisfiable set with no finite bound on model size. Together they imply that no satisfiable set of first-order sentences can guarantee that all its models are denumerably infinite, nor that they are uncountable: in the model theory, first-order languages cannot express the notion of "denumerably infinite."[10](https://plato.stanford.edu/archives/spr2014/entries/logic-classical/)
The compactness theorem itself states that if every finite subset of a first-order theory has a model, then the whole theory has a model. Anatolii Mal'tsev first gave the theorem in 1938 for first-order logic of any signature and used it in 1940/41 to prove theorems about groups, apparently the first application of model theory within classical mathematics; Leon Henkin and [Abraham Robinson](https://www.edgepedia.org/abraham-robinson) independently rediscovered it a few years later.[11](https://plato.stanford.edu/entries/modeltheory-fo/) Compactness holds because derivations use only finitely many premises, connecting the space of possible interpretations to the proof system.[10](https://plato.stanford.edu/archives/spr2014/entries/logic-classical/)
Because full first-order satisfiability is undecidable, a substantial research program identifies decidable fragments, restricted subsets of formulas for which satisfiability can be decided effectively. Major examples include the two-variable fragment, the guarded fragment, and the fluted fragment (a restricted formula class with decidable satisfiability), along with extensions by counting quantifiers; determining the decidability and complexity of such fragments has been a central goal of mathematical logic research in recent decades.[12](https://bartoszjanbednarczyk.github.io/esslli2026.html) Decidability results also follow when every satisfiable formula in a fragment is guaranteed a finitely representable, or symbolic, model, since model-checking against such a representation is decidable.[13](https://arxiv.org/abs/2605.05840)
## References
1. [Semantics of First-Order Logic, Open Logic Project (SLC print edition)](https://slc.openlogicproject.org/slc-print.pdf)
2. [Sets, Relations and Logic, lecture notes, IIT Bombay (chapter on first-order logic)](https://www.cse.iitb.ac.in/~cs717/notes/classNotes/LectureNotes-16-20.pdf)
3. [SI242: More first order logic, United States Naval Academy](https://www.usna.edu/Users/cs/wcbrown/courses/F23SI242/lec/l13/lec.html)
4. [First-Order Logics in Tarski, Tarski 0.7.0 documentation](https://tarski.readthedocs.io/en/stable/notebooks/first-order-logics.html)
5. [Ian Pratt-Hartmann, *Fragments of First-Order Logic*, Oxford University Press, 2023](https://research.manchester.ac.uk/en/publications/fragments-of-first-order-logic/)
6. [Tarski's Truth Definitions, Stanford Encyclopedia of Philosophy](https://plato.sydney.edu.au/entries//////////tarski-truth/)
7. [First-Order Logics in Tarski (latest), Tarski documentation](https://tarski.readthedocs.io/en/latest/notebooks/first-order-logics.html)
8. [Some Advanced Topics in Logic, *A Concise Introduction to Logic*, Milne Publishing](https://milnepublishing.geneseo.edu/concise-introduction-to-logic/chapter/17-some-advanced-topics-in-logic/)
9. [The Model-Theoretic Argument and the Completeness Theorem, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/archives/win2025/entries/realism-sem-challenge/model-theory-completeness.html)
10. [Classical Logic, Stanford Encyclopedia of Philosophy (Spring 2014 edition)](https://plato.stanford.edu/archives/spr2014/entries/logic-classical/)
11. [First-order Model Theory, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/modeltheory-fo/)
12. [Computational perspectives on the classical decision problem, ESSLLI 2026 course page](https://bartoszjanbednarczyk.github.io/esslli2026.html)
13. [Neta Elad and Sharon Shoham, Decidability Results for Fragments of First-Order Logic via a Symbolic Model Property, arXiv](https://arxiv.org/abs/2605.05840)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Logical calculi and logical syntax › Predicate logic › First-order semantics and structures*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license