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
- Soundness theorem for first-order logic: every derivable sentence is a logical consequence.
- Lindenbaum's lemma: every consistent set extends to a maximal consistent set.
- Henkin construction: witness constants and the term model of a maximal consistent set.
- Model existence theorem: every consistent set of sentences has a model.
- Gödel's completeness theorem: every logical consequence is derivable.
- Compactness theorem: a set of sentences has a model if each finite subset has one.
- Applications of first-order compactness: nonstandard models, finiteness and transfer between characteristics.
- Recursively axiomatizable theory: theories with a computable set of axioms.
- Craig's theorem on axiomatizability: a computably enumerable theory has a computable set of axioms.
- Herbrand's theorem: first-order validity reduced to propositional validity of instances.
- Craig interpolation theorem: an implication explained in the common symbols.
- Lyndon interpolation theorem: interpolation that respects positive and negative occurrences.
- Robinson's joint consistency theorem: two consistent theories that agree on the common language have a common model.
- Completeness versus incompleteness: the two meanings of "complete" and how the theorems of 1929 and 1931 fit together.
Prerequisites
- First-order languages, terms, formulas and sentences, from the topic first-order languages and syntax.
- Structures, satisfaction, models and logical consequence, from the topic structures, satisfaction and truth.
- The Hilbert system and the other proof systems, from the topic proof systems for first-order logic.
- The propositional versions of soundness, completeness, compactness and interpolation, from the topic the propositional calculus.
- Consistency and soundness as general notions, from the topic logic, formal systems and foundations.
- For uncountable languages: Zorn's lemma and cardinal arithmetic.
Everything in this topic
The members of this topic and each page that they need, 85 pages in all.
- Absolutely free algebra concept
- Arity concept
- Boolean function concept
- Cartesian product concept
- Countable set concept
- Countermodel concept
- Function concept
- Induction on well-formed formulas concept
- Proposition concept
- Propositional letter concept
- Set concept
- String concept
- Term algebra concept
- Tuple concept
- Signature concept
- Logical connective definition
- Conjunction definition
- Disjunction definition
- Material implication definition
- Principle of bivalence concept
- Predicate concept
- Biconditional definition
- Structure concept
- Term concept
- Negation concept
- Negation definition
- Atomic formula concept
- Proof of the compactness theorem by ultraproducts proof member
- Truth table concept
- Herbrand universe concept
- Material implication concept
- Conjunction concept
- Disjunction concept
- Tautology concept
- Biconditional concept
- Universal quantifier concept
- Logical connective concept
- Existential quantifier concept
- Well-formed formula concept
- Propositional formula definition
- Propositional formula concept
- Satisfaction concept
- Proof of unique readability by counting brackets proof
- Proof of the soundness theorem for first-order logic by induction on derivations proof member
- Unique readability theorem statement
- Herbrand structure concept
- Truth valuation concept
- Logical consequence concept
- Soundness theorem for first-order logic statement member
- Satisfiability concept
- Outline of Gödel's original proof of the completeness theorem proof member
- Proof of Lindenbaum's lemma by enumeration of sentences proof member
- Direct proof of propositional compactness for countably many variables proof
- Compactness theorem for propositional logic statement
- Proof of Lindenbaum's lemma by Zorn's lemma proof member
- Proof of Herbrand's theorem by propositional compactness proof member
- Lindenbaum's lemma statement member
- Henkin construction concept member
- A Henkin witness for an existential sentence must be a new constant example member
- A maximal consistent set without witnesses has a term model that fails it example member
- Proof of the model existence theorem by the Henkin construction proof member
- The equality quotient in a Henkin term model example member
- Model existence theorem statement member
- Proof of Gödel's completeness theorem from the model existence theorem proof member
- Gödel's completeness theorem statement member
- Outline of a proof of Craig's interpolation theorem by the cut-free sequent calculus proof member
- Recursively axiomatizable theory concept member
- Proof of the compactness theorem from the completeness theorem proof member
- Proof of Herbrand's theorem by cut elimination proof member
- Proof of Robinson's joint consistency theorem by a joint Henkin construction proof member
- Proof of Craig's theorem by padding conjunctions proof member
- The theory of groups is recursively axiomatizable example member
- Completeness versus incompleteness concept member
- Compactness theorem statement member
- Herbrand's theorem statement member
- Peano arithmetic is recursively axiomatizable example member
- True arithmetic is not recursively axiomatizable example member
- Craig's theorem on axiomatizability statement member
- Proof of Robinson's joint consistency theorem from Craig's interpolation theorem proof member
- Applications of first-order compactness example member
- Robinson's joint consistency theorem statement member
- Proof of Craig's interpolation theorem from Robinson's joint consistency theorem proof member
- Craig interpolation theorem statement member
- Proof of Lyndon's interpolation theorem proof member
- Lyndon interpolation theorem statement member
About this page
| Tag | FBWW4J1XWG |
|---|---|
| URI | m2://FBWW4J1XWG |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03B10, 03C40 |
| 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
- Compactness theorem
- Proof of the compactness theorem by ultraproducts
- Completeness versus incompleteness
- Recursively axiomatizable theory
- Proof of Gödel's completeness theorem from the model existence theorem
- Peano arithmetic is recursively axiomatizable
- Craig's theorem on axiomatizability
- Proof of Lindenbaum's lemma by Zorn's lemma
- Proof of Herbrand's theorem by propositional compactness
- A Henkin witness for an existential sentence must be a new constant
- Proof of Craig's theorem by padding conjunctions
- Soundness theorem for first-order logic
- A maximal consistent set without witnesses has a term model that fails it
- Lyndon interpolation theorem
- Outline of Gödel's original proof of the completeness theorem
- Proof of Lindenbaum's lemma by enumeration of sentences
- Proof of the compactness theorem from the completeness theorem
- Craig interpolation theorem
- Proof of Lyndon's interpolation theorem
- Proof of the model existence theorem by the Henkin construction
- Model existence theorem
- The equality quotient in a Henkin term model
- Proof of Craig's interpolation theorem from Robinson's joint consistency theorem
- Outline of a proof of Craig's interpolation theorem by the cut-free sequent calculus
- Applications of first-order compactness
- Proof of the soundness theorem for first-order logic by induction on derivations
- Robinson's joint consistency theorem
- Henkin construction
- Lindenbaum's lemma
- Proof of Robinson's joint consistency theorem from Craig's interpolation theorem
- Proof of Robinson's joint consistency theorem by a joint Henkin construction
- Herbrand's theorem
- The theory of groups is recursively axiomatizable
- Gödel's completeness theorem
- Proof of Herbrand's theorem by cut elimination
- True arithmetic is not recursively axiomatizable