# Henkin-style completeness proofs for intuitionistic logic

Henkin-style completeness proofs are founded on a few basic presuppositions, such as the assumptions that the language of a logical theory must be enumerable, and that it must contain a (not necessarily primitive) logical connective for negation.

One could fairly describe its general method as follows:

1. By (reverse) contraposition, assume that $$\Gamma \nvdash p$$;
2. Show that $$\Gamma \cup \{\neg p\}$$ is consistent;
3. Extend $$\Gamma \cup \{\neg p\}$$ to a maximal consistent set $$\Delta$$ as follows: \begin{align} \Delta_0 :=& \Gamma \cup \{\neg p\} \\ \Delta_{n+1} :=& \begin{cases} \Delta_n \cup \{\varphi_{n+1}\} & \text{if } \Delta_n \cup \{\varphi_{n+1}\} \text{ is consistent} \\ \Delta_n \cup \{\neg \varphi_{n+1}\} & \text{otherwise} \end{cases} \\ \Delta :=& \bigcup_{n \in \mathbb{N}} \Delta_{n}. \end{align}
4. Prove that $$\Delta$$ is consistent, maximal and that $$\Gamma \cup \{\neg p\} \subseteq \Delta$$;
5. Construct a model $$\mathcal{M}$$ s.t. $$\left[\!\!\left[ \varphi \right]\!\!\right]_\mathcal{M}=1$$ iff $$\varphi \in \Delta$$;
6. Derive a contradiction by showing that $$\left[\!\!\left[ \Gamma \right]\!\!\right]_\mathcal{M}=1$$ but $$\left[\!\!\left[ p \right]\!\!\right]_\mathcal{M}=0$$.

However, a moment's reflection shows that the inference from (1) to (2) fails for constructive logics, or, more precisely, logics without the inference rule of double negation elimination. In such logics, a context that does not prove $$p$$ may prove $$\neg\neg p$$ (thus being consistent with $$p$$). Constructively, we can only obtain a weakened form of (1)$$-$$(2), that is, $$\Gamma \nvdash \neg \neg p \quad \Longrightarrow \quad \Gamma, \neg p \nvdash \bot.$$ This reveals that, as they are commonly formulated, Henkin-style proofs can only be obtained for logical theories that allow for classical (as opposed to constructive) reasoning. In other words, the logic must be able to prove the law of the excluded middle, double negation elimination etc.

I wonder if a slight modified form of Henkin-style completeness proof is still possible for intuitionistic logic? Is there any reference on the subject? It is known to be complete with respect to topological models, Kripke semantics, and Heyting algebras. Are the proofs given using another method?

• Completeness in this case is: if $p$ is valid in every model then it is provable. Henkin-style poof of completeness takes the contra-positive form: assume that $p$ is not provable and construct a model in which $p$ is not valid. Thus even if you could overcome the problem you are describing, you still would not get completeness, but rather its contrapositive form. Nevertheless, completeness of intuitionistic propositional calculus is of course established (for the cases you mention). The method is different. – Andrej Bauer Jan 6 at 0:17

By arguments of Gödel and Kreisel, a constructive proof of (first-order) intuitionistic completeness without further modifications is not possible since such a completeness result would entail non constructive principles. However, Veldman (1976) found a workaround to this, by introducing Kripke models with so called exploding nodes, which are nodes which are allowed to force $$\bot$$. Classically, one could always discard the exploding nodes without changing the forcing at the other nodes, but constructively, the change is crucial: the fact that a node is exploding or not might not be decidable. Veldman sacrificed the decidability of a node being exploding in favour of a constructive proof of completeness for intuitionistic logic with respect to the semantics of these modified Kripke models. The result is described in "An Intuitionistic Completeness Theorem for Intuitionistic Predicate Logic" (The Journal of Symbolic Logic, Vol. 41, No. 1, 1976, pp. 159-166).