Henkin construction

The method of constants was introduced by L. Henkin in 1949 [a1] to establish the strong completeness of first-order logic (cf. Completeness (in logic)). Whilst this method originally involved the deductive apparatus of first-order logic, it can be modified so as to employ only model-theoretic ideas (cf. Model (in logic); Model theory).

Let $L$ be a first-order logical language with equality, and consider a set of sentences in $L$ which is finitely satisfiable in the sense that each of its finite subsets has a model. Since the collection of finitely satisfiable sets is closed under unions of chains, each such set can be extended to one which is maximal in the sense that it is finitely satisfiable and contains every sentence in $L$ or its negation. When $L$ contains constant terms, each maximal set in $L$ induces an equivalence relation on the set of constant terms: $(t,t')$ is in this relation provided that the equation $t=t'$ is a member of the maximal set. Let $[t]$ denote the equivalence class of $t$. An interpretation for $L$ can be constructed on the partition induced by this relation. On this interpretation, each individual constant in the non-logical vocabulary of $L$ denotes its equivalence class; $([t_1],\ldots,[t_n])$ is in the extension of the $n$-ary predicate $P$ if and only if the sentence $P(t_1,\ldots,t_n)$ is a member of the maximal set; and $([t_1],\ldots,[t_n],[t_{n+1}])$ is in the extension of the $n$-ary functional constant $g$ if and only if the equation $g(t_1,\ldots,t_n)=t_{n+1}$ is a member of the maximal set. This interpretation is a model of the maximal set if the set is term-complete in the sense that it contains an instance of each existential sentence it contains. This interpretation is called a Henkin model for the maximal and term-complete set.

Not every first-order language contains constant terms. And even when $L$ contains constant terms, there are finitely satisfiable sets in $L$ which cannot be extended to maximal and term-complete sets in $L$. In such cases the Henkin construction proceeds by adding new constants to the non-logical vocabulary of $L$ in such a way that the finitely satisfiable set in $L$ can be extended to a maximal and term-complete set in the extended language.

H.J. Keisler [a2] modified the Henkin construction at the point where the new constants are introduced. Let $I$ denote the collection of finite subsets of a finitely satisfiable set. For each member of $I$, choose a model of that set. $T$ is the family (indexed by $I$) of such models. Expand the non-logical vocabulary of $L$ by adding the members of the direct product of the domains of the members of $T$ as individual constants. Members of this direct product are functions on $I$ whose value at each $i\in I$ is a member of the domain of the $i$th member of $T$. The $i$th member of $T$ is expanded to interpretations of the extended language by having each function in the direct product denote its value at $i$. Let $T^*$ denote the resulting family of interpretations. The theory of $T^*$ is the set of all sentences in the extended language true on all members of $T^*$. The union of the theory of $T^*$ and the finitely satisfiable set from $L$ is itself finitely satisfiable, and any maximal extension of this union is term complete. The Henkin model for such a maximal extension is called a Henkin–Keisler model.

Generalizing the above, let $I$ be any non-empty set and let $T$ be a family of interpretations for $L$ indexed by $I$. As above, expand the non-logical vocabulary of $L$ by adding the direct product of the domains of the members of $T$ as individual constants, expand the members of $T$ to interpretations of the extended language as above, and let $T^*$ denote the resulting family of interpretations. The theory of $T^*$ is finitely satisfiable and any maximal extension of this set is term complete.

Henkin–Keisler models can be seen as both a specialization of the Henkin construction and as an alternative to the ultraproduct construction (cf. also Ultrafilter). There is a natural correspondence between maximal extensions of the theory of $T^*$ and ultrafilters (cf. Ultrafilter) on $I$. Associate with each sentence in the expanded language the set of indices (from $I$) of those members of $T^*$ on which the sentence is true. Given an ultrafilter on $I$, consider the set of sentences in the extended language whose associated set of indices is a member of the ultrafilter. This set is a maximal extension of the theory of $T^*$. Further, if all members of $T$ are non-trivial in the sense that their domains contain at least two objects, then given any maximal extension of the theory of $T^*$, the collection of sets of indices associated with the members of the maximal extension is an ultrafilter on $I$. Finally, the Henkin–Keisler model of any maximal extension of the theory of $T^*$, when restricted to $L$, is isomorphic to the ultraproduct of the members of $T$ over the corresponding ultrafilter.

References

[a1]	L. Henkin, "The completeness of the first-order functional calculus" J. Symb. Logic , 14 (1949) pp. 159–166
[a2]	H.J. Keisler, "A survey of ultraproducts, logic" Y. Bar-Hillel (ed.) , Logic, Methodology and Philosophy of Science , North-Holland (1965) pp. 112–126
[a3]	G. Weaver, "Henkin–Keisler models" , Kluwer Acad. Publ. (1997)