2.6: The Completeness Theorem
- Page ID
- 121609
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
- 2.6.1: Introduction
- The completeness theorem is one of the most fundamental results about logic.
- 2.6.2: Outline of the Proof
- The proof of the completeness theorem is a bit complex, and upon first reading it, it is easy to get lost. So let us outline the proof.
- 2.6.3: Complete Consistent Sets of Sentences
- Complete sets of sentences leave no questions unanswered. For any sentence \(A\), \(\Gamma\) “says” if \(A\) is true or false.
- 2.6.4: Henkin Expansion
- Part of the challenge in proving the completeness theorem is that the model we construct from a complete consistent set \(\Gamma\) must make all the quantified formulas in \(\Gamma\) true. In order to guarantee this, we use a trick due to Leon Henkin.
- 2.6.5: Lindenbaum’s Lemma
- We now prove a lemma that shows that any consistent set of sentences is contained in some set of sentences which is not just consistent, but also complete.
- 2.6.6: Construction of a Model
- Right now we are not concerned about \(=\), i.e., we only want to show that a consistent set \(\Gamma\) of sentences not containing \(=\) is satisfiable. We first extend \(\Gamma\) to a consistent, complete, and saturated set \(\Gamma^*\). In this case, the definition of a model \(M(\Gamma^*)\) is simple.
- 2.6.7: Identity
- The construction of the term model given in the preceding section is enough to establish completeness for first-order logic for sets \(\Gamma\) that do not contain \(=\). It does not work, however, if \(=\) is present. We can fix this using a construction known as “factoring.”
- 2.6.8: The Completeness Theorem
- Let’s combine our results: we arrive at the completeness theorem. Let \(\Gamma\) be a set of sentences. If \(\Gamma\) is consistent, it is satisfiable.
- 2.6.9: The Compactness Theorem
- One important consequence of the completeness theorem is the compactness theorem. The compactness theorem states that if each finite subset of a set of sentences is satisfiable, the entire set is satisfiable—even if the set itself is infinite.
- 2.6.10: A Direct Proof of the Compactness Theorem
- We can prove the Compactness Theorem directly, without appealing to the Completeness Theorem, using the same ideas as in the proof of the completeness theorem.
- 2.6.11: The Löwenheim-Skolem Theorem
- The Löwenheim-Skolem Theorem says that if a theory has an infinite model, then it also has a model that is at most countably infinite.