Math 2.0

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

  1. Structure: a domain with interpretations of the symbols of a signature.
  2. Satisfaction: Tarski's recursive clauses for ℳ⊨φ[s]\mathcal{M} \models \varphi[s].
  3. Truth in a structure: sentences true in ℳ\mathcal{M} and the theory Th⁡(ℳ)\operatorname{Th}(\mathcal{M}).
  4. Model: structures in which every sentence of a theory is true.
  5. Validity: formulas true in every structure.
  6. Coincidence lemma: satisfaction depends only on the free variables and the symbols used.
  7. Substitution lemma (semantic): substitution of a term matches a change of the assignment.
  8. Isomorphism invariance of truth: isomorphic structures satisfy the same formulas.
  9. Herbrand universe: the closed terms of a signature.
  10. Herbrand structure: structures built from closed terms, and Herbrand models of universal sentences.
  11. Game-theoretic semantics: truth as the existence of a winning strategy for the verifier.
  12. Definable relations: relations defined by formulas, and non-definability by automorphisms.
  13. Drinker paradox: a valid sentence that sounds false.

Prerequisites

Everything in this topic

The members of this topic and each page that they need, 139 pages in all.

  1. Absolutely free algebra concept
  2. Alphabet concept
  3. Arity concept
  4. Bijective function concept
  5. Binary relation concept
  6. Binary tree concept
  7. Boolean function concept
  8. Cartesian product concept
  9. Catalan numbers concept
  10. Countermodel concept
  11. Definition by recursion concept
  12. Determinacy concept
  13. Directed graph concept
  14. Effectively decidable set concept
  15. Element definition
  16. Equality (mathematics) concept
  17. First-order variable concept
  18. Formal language concept
  19. Function concept
  20. Function composition concept
  21. Homomorphism concept
  22. Induction on well-formed formulas concept
  23. Integers object
  24. Natural numbers object
  25. Peano axioms concept
  26. Proposition concept
  27. Propositional letter concept
  28. Real numbers object
  29. Set concept
  30. String concept
  31. Term algebra concept
  32. Tuple concept
  33. Signature concept
  34. Set definition
  35. Logical connective definition
  36. Conjunction definition
  37. Disjunction definition
  38. Material implication definition
  39. Principle of bivalence concept
  40. Predicate concept
  41. Predicate definition
  42. Family of sets definition
  43. Ordered pair definition
  44. Union definition
  45. Biconditional definition
  46. Structure concept member
  47. Structure definition member
  48. Term concept
  49. Negation concept
  50. Negation definition
  51. Cartesian product definition
  52. Atomic formula concept
  53. A directed graph as a structure example member
  54. Truth table concept
  55. The natural numbers as a structure for the language of arithmetic example member
  56. Herbrand universe concept member
  57. Isomorphism definition
  58. Material implication concept
  59. Conjunction concept
  60. Disjunction concept
  61. Division does not interpret a function symbol on the real numbers example member
  62. Universal quantifier concept
  63. Biconditional concept
  64. Universal quantifier definition
  65. Existential quantifier definition
  66. Union of a family of sets definition
  67. Subset definition
  68. Uniqueness quantifier definition
  69. Logical connective concept
  70. Existential quantifier concept
  71. Binary relation definition
  72. Well-formed formula concept
  73. Propositional formula definition
  74. Propositional formula concept
  75. Function definition
  76. Free and bound variables concept
  77. Satisfaction definition member
  78. Satisfaction concept member
  79. Proof of unique readability by counting brackets proof
  80. Formal system concept
  81. Choice function definition
  82. Substitution concept
  83. Truth in a structure definition member
  84. Truth in a structure concept member
  85. Proof of the coincidence lemma by induction on terms and formulas proof member
  86. Unique readability theorem statement
  87. Satisfaction in a two-element structure, clause by clause example member
  88. Herbrand structure concept member
  89. Game-theoretic semantics concept member
  90. Proof of isomorphism invariance of truth by induction proof member
  91. The integers with their order have no least element example member
  92. A formula with free variables satisfied in the natural numbers example member
  93. Axiom of choice statement
  94. A formula with a free variable is neither true nor false example member
  95. The sentence that there are at least three elements example member
  96. Validity concept member
  97. Model definition member
  98. Coincidence lemma statement member
  99. Model concept member
  100. Truth valuation concept
  101. Isomorphism invariance of truth statement member
  102. An evaluation game with a negation example member
  103. Every number has a larger one, in the natural numbers and in a finite order example member
  104. An evaluation game with imperfect information is not determined example member
  105. Drinker paradox example member
  106. Proof of the semantic substitution lemma by induction proof member
  107. Proof of the equivalence of game and Tarski semantics by truth-preserving strategies proof member
  108. The path graph on three vertices as a model of the theory of graphs example member
  109. Definable relations definition member
  110. Logical consequence definition
  111. Logical consequence concept
  112. The natural numbers with less-or-equal are not a strict linear order example member
  113. The evaluation game for every number has a larger one example member
  114. Substitution lemma (semantic) statement member
  115. Equivalence of game-theoretic and Tarskian semantics statement member
  116. Validity definition member
  117. Rule of inference concept
  118. The even numbers are definable in the natural numbers with addition example member
  119. The order is definable in the field of reals example member
  120. The positive integers are not definable in the integers with addition example member
  121. The successor relation is definable in the integers with order example member
  122. If everything has a property then something has it example member
  123. If something has a property then everything has it is not valid example member
  124. Modus ponens concept
  125. Mathematical proof concept
  126. Mathematical induction concept
  127. Inductive and recursive definitions concept
  128. Herbrand universe definition member
  129. Structural induction concept
  130. Herbrand structure definition member
  131. A signature without constant symbols has no closed terms example member
  132. The Herbrand universe of one constant and one binary function symbol example member
  133. The Herbrand universe of one constant and one unary function symbol example member
  134. The Herbrand universe is an absolutely free algebra example member
  135. The Herbrand models of a recursive pair of clauses example member
  136. Proof that universal sentences have Herbrand models proof member
  137. Universal sentences have Herbrand models statement member
  138. A Herbrand model built from a finite model example member
  139. A satisfiable set without a Herbrand model example member
About this page
TagNJDME6F845
URIm2://NJDME6F845
Kindtopic
WritingW0 stub
MSC03B10
Part ofMathematical logic
Changed17 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.

The changes to this page, the oldest first
DateChangeFieldBy
2026-11-17addthe whole nodetamnd
2026-11-17addthe section Remarkstamnd

What links here

Nodes in this topic