Math 2.0

Areas Mathematical logic Topic

Completeness, compactness and interpolation

Summary

This topic is a part of mathematical logic. It covers soundness, the completeness theorem and its proofs, the compactness theorem and its first uses, Herbrand's theorem and the interpolation theorems for first-order logic.

Remarks

Reading order

  1. Soundness theorem for first-order logic: every derivable sentence is a logical consequence.
  2. Lindenbaum's lemma: every consistent set extends to a maximal consistent set.
  3. Henkin construction: witness constants and the term model of a maximal consistent set.
  4. Model existence theorem: every consistent set of sentences has a model.
  5. Gödel's completeness theorem: every logical consequence is derivable.
  6. Compactness theorem: a set of sentences has a model if each finite subset has one.
  7. Applications of first-order compactness: nonstandard models, finiteness and transfer between characteristics.
  8. Recursively axiomatizable theory: theories with a computable set of axioms.
  9. Craig's theorem on axiomatizability: a computably enumerable theory has a computable set of axioms.
  10. Herbrand's theorem: first-order validity reduced to propositional validity of instances.
  11. Craig interpolation theorem: an implication explained in the common symbols.
  12. Lyndon interpolation theorem: interpolation that respects positive and negative occurrences.
  13. Robinson's joint consistency theorem: two consistent theories that agree on the common language have a common model.
  14. Completeness versus incompleteness: the two meanings of "complete" and how the theorems of 1929 and 1931 fit together.

Prerequisites

Everything in this topic

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

  1. Absolutely free algebra concept
  2. Arity concept
  3. Boolean function concept
  4. Cartesian product concept
  5. Countable set concept
  6. Countermodel concept
  7. Function concept
  8. Induction on well-formed formulas concept
  9. Proposition concept
  10. Propositional letter concept
  11. Set concept
  12. String concept
  13. Term algebra concept
  14. Tuple concept
  15. Signature concept
  16. Logical connective definition
  17. Conjunction definition
  18. Disjunction definition
  19. Material implication definition
  20. Principle of bivalence concept
  21. Predicate concept
  22. Biconditional definition
  23. Structure concept
  24. Term concept
  25. Negation concept
  26. Negation definition
  27. Atomic formula concept
  28. Proof of the compactness theorem by ultraproducts proof member
  29. Truth table concept
  30. Herbrand universe concept
  31. Material implication concept
  32. Conjunction concept
  33. Disjunction concept
  34. Tautology concept
  35. Biconditional concept
  36. Universal quantifier concept
  37. Logical connective concept
  38. Existential quantifier concept
  39. Well-formed formula concept
  40. Propositional formula definition
  41. Propositional formula concept
  42. Satisfaction concept
  43. Proof of unique readability by counting brackets proof
  44. Proof of the soundness theorem for first-order logic by induction on derivations proof member
  45. Unique readability theorem statement
  46. Herbrand structure concept
  47. Truth valuation concept
  48. Logical consequence concept
  49. Soundness theorem for first-order logic statement member
  50. Satisfiability concept
  51. Outline of Gödel's original proof of the completeness theorem proof member
  52. Proof of Lindenbaum's lemma by enumeration of sentences proof member
  53. Direct proof of propositional compactness for countably many variables proof
  54. Compactness theorem for propositional logic statement
  55. Proof of Lindenbaum's lemma by Zorn's lemma proof member
  56. Proof of Herbrand's theorem by propositional compactness proof member
  57. Lindenbaum's lemma statement member
  58. Henkin construction concept member
  59. A Henkin witness for an existential sentence must be a new constant example member
  60. A maximal consistent set without witnesses has a term model that fails it example member
  61. Proof of the model existence theorem by the Henkin construction proof member
  62. The equality quotient in a Henkin term model example member
  63. Model existence theorem statement member
  64. Proof of Gödel's completeness theorem from the model existence theorem proof member
  65. Gödel's completeness theorem statement member
  66. Outline of a proof of Craig's interpolation theorem by the cut-free sequent calculus proof member
  67. Recursively axiomatizable theory concept member
  68. Proof of the compactness theorem from the completeness theorem proof member
  69. Proof of Herbrand's theorem by cut elimination proof member
  70. Proof of Robinson's joint consistency theorem by a joint Henkin construction proof member
  71. Proof of Craig's theorem by padding conjunctions proof member
  72. The theory of groups is recursively axiomatizable example member
  73. Completeness versus incompleteness concept member
  74. Compactness theorem statement member
  75. Herbrand's theorem statement member
  76. Peano arithmetic is recursively axiomatizable example member
  77. True arithmetic is not recursively axiomatizable example member
  78. Craig's theorem on axiomatizability statement member
  79. Proof of Robinson's joint consistency theorem from Craig's interpolation theorem proof member
  80. Applications of first-order compactness example member
  81. Robinson's joint consistency theorem statement member
  82. Proof of Craig's interpolation theorem from Robinson's joint consistency theorem proof member
  83. Craig interpolation theorem statement member
  84. Proof of Lyndon's interpolation theorem proof member
  85. Lyndon interpolation theorem statement member
About this page
TagFBWW4J1XWG
URIm2://FBWW4J1XWG
Kindtopic
WritingW0 stub
MSC03B10, 03C40
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