Completeness Theorem

Completeness Theorem (Version 1)

Suppose $\Sigma$ is a set of sentences in the language $\mathcal{L}$, $\phi$ is a sentence in $\mathcal{L}$, and $\Sigma \models \phi$. Then $\Sigma ⊢\phi$.

Completeness Theorem (Version 2)

Suppose $\Sigma$ is a set of sentences in language $\mathcal{L}$, and $\Sigma /⊢\perp$. Then $\Sigma$ has a model $\mathfrak{A}$.(i.e. satisfiable) Assuming the cardinality $|\mathcal{L}|={\aleph }_0$ (as we do at this stage), then $|\mathfrak{A}|\le {\aleph }_0$ where $|\mathfrak{A}|$ is the cardinality of the universe of $\mathfrak{A}$.

Step 1 Let $\mathcal{C}=\{c_1,c_2,c_3\dots \}$ a countably infinite set of constant symbols not in $\mathcal{L}$. Introduce a language ${\mathcal{L}}^{\ast }=\mathcal{L}\cup \mathcal{C}$ which extends $\mathcal{L}$.

Step 2 Extend $\Sigma$ to ${\Sigma }^{\ast }$ with $\mathcal{C}$ a Set of Henkin Witnesses Henkin Witnesses: There is a consistent extension ${\Sigma }^{\ast }$ of $\Sigma$ in the extended language ${\mathcal{L}}^{\ast }$ , with the following property:

For every formula $\phi =\phi (v)$ of ${\mathcal{L}}^{\ast }$ (not just of $\mathcal{L}$) with at most one free variable depending on $\phi$ (here it is $v$), there is a constant $c\in \mathcal{C}$ ($c$ depending on $\phi$) such that $\exists v\phi (v)\to \phi (c)\in {\Sigma }^{\ast }.$

This step we want to extend $\Sigma$ to a larger ${\Sigma }^{\ast }$ that any sentence can be represented by a constant in $\mathcal{C}$.

Step 3 Enlarge ${\Sigma }^{\ast }$ to a Complete Theory By Lindenbaum’s Theorem, the theory ${\Sigma }^{\ast }$ in the language ${\mathcal{L}}^{\ast }=\mathcal{L}\cup \mathcal{C}$ has a complete consistent extension in the same language ${\mathcal{L}}^{\ast }$ . Henceforth, we will use the same notation ${\Sigma }^{\ast }$ to denote this complete extension. As in Lindenbaum’s Theorem in general, the extension is neither unique nor canonical.

Step 4 An equivalence relation on $\mathcal{C}$ by $c\sim c^{\prime }⟺(c=c^{\prime })\in {\Sigma }^{\ast }⟺{\Sigma }^{\ast }⊢c=c^{\prime }⟺{\Sigma }^{\ast }/⊢c\ne c^{\prime }$

The extension ${\Sigma }^{\ast }$ of $\Sigma$ is not canonical or uniquely determined. But once we have some such extension ${\Sigma }^{\ast }$ , a structure ${\mathfrak{A}}^{\ast }$ for which ${\mathfrak{A}}^{\ast }\models {\Sigma }^{\ast }$ is uniquely determined from ${\Sigma }^{\ast }$, as we will see in step 5 and step 6

Step 5 Build ${\mathfrak{A}}^{\ast }$ that would satisfies ${\Sigma }^{\ast }$ The problem to be addressed in this Step is that the axioms for equality only ensure that the equality relation symbol ”$=$” in an ${\mathcal{L}}^{\ast }$-structure will be interpreted as an equivalence relation, and not as the identity relation. So it is perhaps not so surprising that we will build the desired ${\mathcal{L}}^{\ast }$-structure by taking equivalence classes. But what will be critical is the use of the Henkin Witnesses.

The universe $A$ of ${\mathfrak{A}}^{\ast }$ is defined by $A:=\mathcal{C}/\sim :=\{[c]:c\in \mathcal{C}\},$

1. Constant Symbols in $\mathcal{L}$ Let $d\in \mathcal{L}$ be a constant symbol. We define $d^{{\mathfrak{A}}^{\ast }}=[c]⟺{\Sigma }^{\ast }⊢d=c$

We have $⊢d=d$ because $⊢u=u⟹⊢\forall u(u=u)⟹d=d⟹\exists v(v=d)$ But Henkin Witeness implies $⊢\exists v(v=d)\to c=d$ for some $c$. ${\Sigma }^{\ast }⊢c=d$ by Modus Ponens. Define $d^{{\mathfrak{A}}^{\ast }}=[c]$ where $c$ (iff ${\Sigma }^{\ast }⊢d=c$) 2. Function Symbols in $\mathcal{L}$. Suppose $f$ is a function symbol in $\mathcal{L}$. How to interpret $f^{{\mathfrak{A}}^{\ast }}([c_1],\dots ,[c_n])=[c]$ Suppose $c_1\dots c_n\in \mathcal{C}$ We want to show ${\Sigma }^{\ast }⊢f(c_1,\dots c_n)=c$ for some $c\in \mathcal{C}$. We claim ${\Sigma }^{\ast }⊢\exists v(f(c_1,\dots ,c_n)=v)$ We have $⊢f(c_1,\dots ,c_n)=f(c_1,\dots ,c_n)$ This gives $⊢\exists v(f(c_1,\dots c_n)=v)$ by generalization rule. ${\Sigma }^{\ast }⊢\exists v(f(c_1\dots ,c_n)=v)\to f(c_1,\dots ,c_n)=c$ for some $c$ by Henkin.

3. Relation Symbols in $\mathcal{L}$. Let $r\in \mathcal{L}$ be an n-ary relation symbol. Define the interpretation $r^{{\mathfrak{A}}^{\ast }}\subset A^n$ of $r$ in ${\mathfrak{A}}^{\ast }$ by $([c_1],\cdots ,[c_n])\in r^{{\mathfrak{A}}^{\ast }}⟺{\Sigma }^{\ast }⊢r(c_1,\cdots ,c_n),$ where $c_1\cdots c_n\in \mathcal{C}$. Step 6 Proof that ${\mathfrak{A}}^{\ast }\models {\Sigma }^{\ast }$ Recall the definition of satisfaction: Suppose $t$ is a term in the language ${\mathcal{L}}^{\ast }$ (with no free variables). Then the interpretation $t^{{\mathfrak{A}}^{\ast }}$ ($\in A$) of $t$ is defined by induction on the complexity of $t$ as follows: (i) If $t$ is a constant symbol $c\in \mathcal{C}$ or $d\in \mathcal{L}$, then $c^{{\mathfrak{A}}^{\ast }}$ and $d^{{\mathfrak{A}}^{\ast }}$ have already been defined in (3.18) and (3.19). In particular $t^{{\mathfrak{A}}^{\ast }}=[c]⟺{\Sigma }^{\ast }⊢t=c.$ (ii) If $t$ is $f(t_1,\dots ,t_n)$ then $t^{{\mathfrak{A}}^{\ast }}:=f^{{\mathfrak{A}}^{\ast }}(t_1^{{\mathfrak{A}}^{\ast }},\dots ,t_n^{{\mathfrak{A}}^{\ast }}).$Lemma 3.28. If $t$ is a term in ${\mathcal{L}}^{\ast }$ and $c\in \mathcal{C}$, then$t^{{\mathfrak{A}}^{\ast }}=[c]⟺{\Sigma }^{\ast }⊢t=c.$ Step 7

We now define the structure $\mathfrak{A}$ to be the same as ${\mathfrak{A}}^{\ast }$ , except that it is a structure just for the symbols in $\mathcal{L}$ and not for the new symbols in $\mathcal{C}$.

Proposition

Version 1 & 2 of Completeness Theorem are Equivalent.

Proof Version 1 of Completeness Theorem $⟹$ Version 2 of Completeness Theorem. Suppose $\Sigma$ has no model, then there is no structure $\mathcal{M}$ that $\mathcal{M}\models \Sigma$, then since $\Sigma \models \perp$ if and only if for every $\mathcal{M}\models \Sigma$, then $\mathcal{M}\models \perp$. With no structure $\mathcal{M}$ that $\mathcal{M}\models \Sigma$, it is always true $\mathcal{M}\models \perp$, so $\Sigma \models \perp$. Through version 1 of Completeness Theorem, $\Sigma ⊢\perp$, which means $\Sigma$ is inconsistent, that is version 2 of Completeness theorem proved. Version 2 of Completeness Theorem $⟹$Version 1 of Completeness Theorem Next assume Version 2. To prove Version 1, suppose $\Sigma$ is a set of sentences, $\phi$ is a sentence, and $\Sigma \models \phi$.

\therefore \quad & \Sigma \cup \{\neg \varphi\} \quad \text{has no model.} \\ \therefore \quad & \Sigma \cup \{\neg \varphi\} \quad \text{is not consistent by version 2.} \\ \therefore \quad & \Sigma \vdash \varphi \quad \qquad \text{by properties of consistency.} \end{align*}$$