Areas Mathematical logic Topic
Structures, satisfaction and truth
Summary
This topic is a part of mathematical logic. It covers Tarski's semantics for first-order logic, with structures, assignments, satisfaction, truth, models, validity and the basic lemmas.
Remarks
Reading order
- Structure: a domain with interpretations of the symbols of a signature.
- Satisfaction: Tarski's recursive clauses for .
- Truth in a structure: sentences true in and the theory .
- Model: structures in which every sentence of a theory is true.
- Validity: formulas true in every structure.
- Coincidence lemma: satisfaction depends only on the free variables and the symbols used.
- Substitution lemma (semantic): substitution of a term matches a change of the assignment.
- Isomorphism invariance of truth: isomorphic structures satisfy the same formulas.
- Herbrand universe: the closed terms of a signature.
- Herbrand structure: structures built from closed terms, and Herbrand models of universal sentences.
- Game-theoretic semantics: truth as the existence of a winning strategy for the verifier.
- Definable relations: relations defined by formulas, and non-definability by automorphisms.
- Drinker paradox: a valid sentence that sounds false.
Prerequisites
- First-order languages and syntax: signatures, terms, formulas, free variables and substitution.
- The propositional calculus: truth tables and tautologies, which the clauses for the connectives extend.
- Reasoning and proof: proof by cases and proof by induction, used in the proofs of the lemmas.
Everything in this topic
The members of this topic and each page that they need, 139 pages in all.
- Absolutely free algebra concept
- Alphabet concept
- Arity concept
- Bijective function concept
- Binary relation concept
- Binary tree concept
- Boolean function concept
- Cartesian product concept
- Catalan numbers concept
- Countermodel concept
- Definition by recursion concept
- Determinacy concept
- Directed graph concept
- Effectively decidable set concept
- Element definition
- Equality (mathematics) concept
- First-order variable concept
- Formal language concept
- Function concept
- Function composition concept
- Homomorphism concept
- Induction on well-formed formulas concept
- Integers object
- Natural numbers object
- Peano axioms concept
- Proposition concept
- Propositional letter concept
- Real numbers object
- Set concept
- String concept
- Term algebra concept
- Tuple concept
- Signature concept
- Set definition
- Logical connective definition
- Conjunction definition
- Disjunction definition
- Material implication definition
- Principle of bivalence concept
- Predicate concept
- Predicate definition
- Family of sets definition
- Ordered pair definition
- Union definition
- Biconditional definition
- Structure concept member
- Structure definition member
- Term concept
- Negation concept
- Negation definition
- Cartesian product definition
- Atomic formula concept
- A directed graph as a structure example member
- Truth table concept
- The natural numbers as a structure for the language of arithmetic example member
- Herbrand universe concept member
- Isomorphism definition
- Material implication concept
- Conjunction concept
- Disjunction concept
- Division does not interpret a function symbol on the real numbers example member
- Universal quantifier concept
- Biconditional concept
- Universal quantifier definition
- Existential quantifier definition
- Union of a family of sets definition
- Subset definition
- Uniqueness quantifier definition
- Logical connective concept
- Existential quantifier concept
- Binary relation definition
- Well-formed formula concept
- Propositional formula definition
- Propositional formula concept
- Function definition
- Free and bound variables concept
- Satisfaction definition member
- Satisfaction concept member
- Proof of unique readability by counting brackets proof
- Formal system concept
- Choice function definition
- Substitution concept
- Truth in a structure definition member
- Truth in a structure concept member
- Proof of the coincidence lemma by induction on terms and formulas proof member
- Unique readability theorem statement
- Satisfaction in a two-element structure, clause by clause example member
- Herbrand structure concept member
- Game-theoretic semantics concept member
- Proof of isomorphism invariance of truth by induction proof member
- The integers with their order have no least element example member
- A formula with free variables satisfied in the natural numbers example member
- Axiom of choice statement
- A formula with a free variable is neither true nor false example member
- The sentence that there are at least three elements example member
- Validity concept member
- Model definition member
- Coincidence lemma statement member
- Model concept member
- Truth valuation concept
- Isomorphism invariance of truth statement member
- An evaluation game with a negation example member
- Every number has a larger one, in the natural numbers and in a finite order example member
- An evaluation game with imperfect information is not determined example member
- Drinker paradox example member
- Proof of the semantic substitution lemma by induction proof member
- Proof of the equivalence of game and Tarski semantics by truth-preserving strategies proof member
- The path graph on three vertices as a model of the theory of graphs example member
- Definable relations definition member
- Logical consequence definition
- Logical consequence concept
- The natural numbers with less-or-equal are not a strict linear order example member
- The evaluation game for every number has a larger one example member
- Substitution lemma (semantic) statement member
- Equivalence of game-theoretic and Tarskian semantics statement member
- Validity definition member
- Rule of inference concept
- The even numbers are definable in the natural numbers with addition example member
- The order is definable in the field of reals example member
- The positive integers are not definable in the integers with addition example member
- The successor relation is definable in the integers with order example member
- If everything has a property then something has it example member
- If something has a property then everything has it is not valid example member
- Modus ponens concept
- Mathematical proof concept
- Mathematical induction concept
- Inductive and recursive definitions concept
- Herbrand universe definition member
- Structural induction concept
- Herbrand structure definition member
- A signature without constant symbols has no closed terms example member
- The Herbrand universe of one constant and one binary function symbol example member
- The Herbrand universe of one constant and one unary function symbol example member
- The Herbrand universe is an absolutely free algebra example member
- The Herbrand models of a recursive pair of clauses example member
- Proof that universal sentences have Herbrand models proof member
- Universal sentences have Herbrand models statement member
- A Herbrand model built from a finite model example member
- A satisfiable set without a Herbrand model example member
About this page
| Tag | NJDME6F845 |
|---|---|
| URI | m2://NJDME6F845 |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03B10 |
| Part of | Mathematical logic |
| Changed | 17 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a same_as or a source (0 of 1)
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
History
Each change to this page, from its provenance log. A change by an agent names its run.
| Date | Change | Field | By |
|---|---|---|---|
| 2026-11-17 | add | the whole node | tamnd |
| 2026-11-17 | add | the section Remarks | tamnd |
What links here
Nodes in this topic
- Definable relations
- The evaluation game for every number has a larger one
- A directed graph as a structure
- Satisfaction
- The Herbrand universe is an absolutely free algebra
- An evaluation game with a negation
- Satisfaction
- The Herbrand universe of one constant and one binary function symbol
- A satisfiable set without a Herbrand model
- The natural numbers with less-or-equal are not a strict linear order
- Validity
- A signature without constant symbols has no closed terms
- Truth in a structure
- A Herbrand model built from a finite model
- The integers with their order have no least element
- The Herbrand universe of one constant and one unary function symbol
- Drinker paradox
- Structure
- The positive integers are not definable in the integers with addition
- Substitution lemma (semantic)
- Proof that universal sentences have Herbrand models
- Validity
- Proof of the semantic substitution lemma by induction
- Universal sentences have Herbrand models
- Model
- If something has a property then everything has it is not valid
- Game-theoretic semantics
- The sentence that there are at least three elements
- The Herbrand models of a recursive pair of clauses
- Coincidence lemma
- Equivalence of game-theoretic and Tarskian semantics
- Herbrand structure
- Herbrand structure
- Herbrand universe
- The even numbers are definable in the natural numbers with addition
- Truth in a structure
- Satisfaction in a two-element structure, clause by clause
- Division does not interpret a function symbol on the real numbers
- Model
- Isomorphism invariance of truth
- Herbrand universe
- The successor relation is definable in the integers with order
- The path graph on three vertices as a model of the theory of graphs
- Proof of the coincidence lemma by induction on terms and formulas
- The order is definable in the field of reals
- Every number has a larger one, in the natural numbers and in a finite order
- The natural numbers as a structure for the language of arithmetic
- A formula with a free variable is neither true nor false
- Proof of isomorphism invariance of truth by induction
- Structure
- A formula with free variables satisfied in the natural numbers
- If everything has a property then something has it
- Proof of the equivalence of game and Tarski semantics by truth-preserving strategies
- An evaluation game with imperfect information is not determined