Generalizing Henkin proof

Question

When one looks at the proof of completeness theorem for first order logic one meets the very beautiful idea of the model of terms, the original idea of Henkin.

Today, my statement for completeness theorem is the following:

A consistent first order theory $T$ has a model.

The proof goes as follows.

• Consider a theory $T$.
• Complete $T$ to an Henkin complete theory $T^*$.
• Build a model of terms for $T^*$.
• Be happy.

Can you point out where precisely we are using the first order logic? I.e. Why the same construction does not work for infinitary logic?

Can you produce concrete examples?

Answer 1

The problem is when we try to argue that the term model for the maximal consistent witness-property-having $\Sigma'\supseteq\Sigma$ is a model of $\Sigma'$; specifically, when we try to handle infinite disjunctions (which aren't an issue for first-order logic).

For simplicity, let's work with the following "silly" proof notion for infinitary logic: $\Gamma\vdash_{fin}\varphi$ iff $\Gamma_0\models\varphi$ for some finite $\Gamma_0\subseteq\Gamma$. (Actually, this isn't that silly: e.g. if we run the Henkin argument with this notion of proof in first-order logic, we get a proof of the compactness theorem, which is really a streamining of the usual compactness-via-completeness argument by cutting out the middleman.) Now given $\Sigma$ which is $\vdash_{fin}$-consistent, it's easy via Zorn's lemma to build a maximal consistent witness-property-having $\Sigma'\supseteq\Sigma$. Now we get a term structure $\mathcal{T}(\Sigma')$ as usual, and want to argue $\mathcal{T}(\Sigma')\models \Sigma'$.

Note that already this should be a point of suspicion: remember that the whole point of going from $\Sigma$ to $\Sigma'$ is that in general $\mathcal{T}(\Sigma)$ is not a model of $\Sigma$! So this is the natural place to expect difficulty.

Now there's a natural choice of $\Sigma$ for which we know this breaks down: the usual counterexample to compactness for infinitary logic, namely the set $$\Sigma=\{c>SSSS...(0) \quad\mbox{($n$ $S$s)}: n\in\mathbb{N}\}\cup\{\forall x\bigvee_{n\in \mathbb{N}}[x=SSSSS...(0)\quad\mbox{($n$ Ss)]})\}$$ which is obviously finitely consistent but has no model. So (fixing a maximal $\vdash_{fin}$-consistent witness-property-having $\Sigma'\supseteq\Sigma$) if we try to analyze the argument that $\mathcal{T}(\Sigma')\models\Sigma'$, we'll run into a problem somewhere.

I'll point out where the issue is now; it's a good idea to examine the argument yourself to see precisely what the issue is at this point. The problem comes when we try to argue that the sentence $$\forall x\bigvee_{n\in \mathbb{N}}[x=SSSSS...(0)\quad\mbox{($n$ Ss)}]$$ is satisfied in $\mathcal{T}(\Sigma')$ - no single one of its conjuncts will be satisfied. In first-order logic this problem is handled by the fact that there are only finitely many conjuncts in any sentence, and the relation $\vdash_{fin}$ is "big enough" to see them all; but here since we have more-than-finitely-many conjuncts, $\vdash_{fin}$ isn't a "big enough" relation.

---

Incidentally, Henkin arguments do go through for infinitary logic if we use the right notion of proof system - namely, we now need to look at infinitary proof systems. So you're quite right that the general idea is useful beyond first-order logic; but the specific context of finitary proof systems is quite narrow.

Answer 2

I think(?) the problem with the infinitary case is that you can have a nested sequence of consistent theories, but their union is not consistent. For an example let $$ \phi = \forall x( x =0 \lor x = 1 \lor x = 2 \lor \cdots),$$$$\psi = \bigwedge_{n\neq m} (n \neq m),$$$$\chi = \exists x P(x),$$ $$ \alpha_n = \neg P(n).$$ and consider the sets $S_n = \{\phi, \psi, \chi, \alpha_0,\ldots,\alpha_n\}$. We have $S_n \subseteq S_{n+1}$ for each $n$. We also have that each $S_n$ is satisfiable. However $S_\infty = \bigcup_{n} S_n$ is not consistent, because we have named everything in the model (because of $\phi$), we have said that something must have property $P$, but also said that every individual does not have property $P$.

Consequently, you can't apply Zorn's lemma to show that every consistent set of sentences is contained in a maximally consistent set.