Extended Completeness Theorem

In the proof of Gödel’s Completeness Theorem 3.17 for a countable language $\mathcal{L}$ and a countable set $\mathcal{C}$ of new constant symbols, we listed in a sequence all formulas of ${\mathcal{L}}^{\ast }=\mathcal{L}\cup \mathcal{C}$ with one free variable:

${\phi }_1,{\phi }_2,\dots ,{\phi }_n,\dots$

Beginning with a consistent set of sentences $\Sigma$ we sequentially and consistently added sentences $\exists v{\phi }_n(v)\to {\phi }_n(c)$, where $v$ was the free variable in ${\phi }_n$ (${\phi }_n(v):={\phi }_n$) and $c\in \mathcal{C}$ did not appear so far in the sequence or in ${\phi }_n$.

If the language $\mathcal{L}$ has infinite cardinality $\kappa$ then the new set of constant symbols $\mathcal{C}$ will be chosen to also have cardinality $\kappa$. The sequence (5.1) is then replaced by a transfinite sequence:

\varphi_1, \varphi_2, \dots, \varphi_n, \dots, \varphi_\omega, \dots, \varphi_\alpha \dots \quad (\alpha < \kappa). \tag{5.2}

We can still consistently add sentences $\exists v{\phi }_{\alpha }(v)\to {\phi }_{\alpha }(c)$, but this time it is because less than $\kappa$ constant symbols have been added at each stage. And this time we need to use transfinite induction to define the members of the transfinite sequence (5.2).

Completeness Theorem, General Version

Suppose $\Sigma$ is a consistent set of sentences in the language $\mathcal{L}$ with cardinality $|\mathcal{L}|=\kappa$. Then $\Sigma$ has a model $\mathfrak{A}$ with cardinality $|\mathfrak{A}|\le \kappa$, where $|\mathfrak{A}|$ is the cardinality of the universe of $\mathfrak{A}$.

The proof of the Completeness Theorem in this more general setting is analogous to the proof in the countable case.

The difference is that instead of a sequence of new constants $\mathcal{C}=\{c_n:n<\omega \}$, one takes a transfinite sequence of new constants $\mathcal{C}=\{c_{\alpha }:\alpha <\kappa \}$. Instead of each proper initial segment of $\{n:n<\omega \}$ having (finite) cardinality $<{\aleph }_0$, each proper initial segment of $\{\alpha :\alpha <\kappa \}$ will have cardinality $<\kappa$, by a standard property of ordinals and cardinals.

The treatment in (Chang and Keisler, 2012, pp 61–66) is essentially the same as here.

---

Step 1 Adding a Set $\mathcal{C}$ of New Constant Symbols to $\mathcal{L}$

Introduce a language ${\mathcal{L}}^{\ast }=\mathcal{L}\cup \mathcal{C}$ which extends $\mathcal{L}$, by adding a cardinality $\kappa$ set $\mathcal{C}=\{c_{\alpha }:\alpha <\kappa \}$ of new constant symbols not in $\mathcal{L}$.

Step 2 Extend $\Sigma$ to ${\Sigma }^{\ast }$ with $\mathcal{C}$ a Set of Henkin Witnesses

This key result is as before, but using transfinite sequences rather than countably infinite sequences in its proof.

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$ (for example $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 }.$

Proof. List all formulas of ${\mathcal{L}}^{\ast }$ (not just formulas of $\mathcal{L}$) with one free variable, as a transfinite sequence indexed by the ordinals $\alpha <\kappa$:

$⟨{\phi }_{\alpha }:\alpha <\kappa ⟩.$

Define a transfinite sequence of consistent extensions of $\Sigma$, in the language ${\mathcal{L}}^{\ast }$:

${\Sigma }_{\alpha }^{\ast }=\{\begin{array}{ll}\Sigma & \alpha =0\\ {\Sigma }_{\alpha -1}^{\ast }\cup \{\exists v\phi (\alpha )\to {\phi }_{\alpha }(c)\}& \alpha \text{ a successor ordinal}\\ {\bigcup }_{\xi <\alpha }{\Sigma }_{\xi }^{\ast }& \alpha \text{ a limit ordinal},\end{array}$

where (depending on $\alpha$), $v$ is the free variable appearing in ${\phi }_{\alpha }$ and $c$ is the first constant symbol in $\mathcal{C}$ not already appearing in any ${\Sigma }_{\eta }^{\ast }$ for $\eta <\alpha$. This is possible since less than $\kappa$ symbols from $\mathcal{C}$ have been added prior to stage $\alpha$ in the process.

We claim that ${\Sigma }_{\alpha }^{\ast }$ is consistent for all $\alpha$. The argument is as before for $\alpha =0$ or $\alpha$ a successor ordinal (this was the tricky case). For $\alpha$ a limit ordinal the result is immediate, since any finite subset of ${\Sigma }_{\alpha }^{\ast }$ was constructed at a previous stage, and so is consistent. $\square$

5.1.3 Step 3: Enlarge ${\Sigma }^{\ast }$ to a Complete Theory

Previously, we used Lindenbaum’s Theorem to obtain a complete consistent extension. The argument remains the same here, with the modification that we utilize a transfinite sequence of extensions of length $\kappa$. We will continue to use ${\Sigma }^{\ast }$ to denote this complete extension.

5.1.4 Step 4: An Equivalence Relation on $\mathcal{C}$

We define the relation $\sim$ on the set of constant symbols $\mathcal{C}$ by:

$c\sim c^{\prime }⟺{\Sigma }^{\ast }⊢c=c^{\prime }.$ As in the countable case, $\sim$ is an equivalence relation.

5.1.5 Step 5: Constructing the Universe $\mathcal{C}/\sim$ for a Structure ${\mathfrak{A}}^{\ast }$

The construction mirrors the countable case. The universe of the structure is built from the equivalence classes of the constants. Every constant symbol in the original language $\mathcal{L}$, as well as each new symbol in $\mathcal{C}$, is interpreted as an appropriate equivalence class. Function and constant symbols in $\mathcal{L}$ are interpreted in the natural way.

5.1.6–5.1.8 Steps 6–8: Final Proofs

• Step 6 (Proof that ${\mathfrak{A}}^{\ast }\models {\Sigma }^{\ast }$): This verification remains unchanged from the countable case.

• Step 7 (Definition of $\mathfrak{A}$ & Proof that $\mathfrak{A}\models \Sigma$): This also follows as before.

• Step 8 (Proof that $|\mathfrak{A}|\le \kappa$): This step remains essentially as it was in the countable case, showing that the resulting model does not exceed the cardinality of the language.