On the completeness of order-theoretic models of the λ-calculus

AbstractScott discovered his domain-theoretic models of the λ-calculus, isomorphic to their function space, in 1969. A natural completeness problem then arises: whether any two terms equal in all Scott models are convertible. There is also an analogous consistency problem: whether every equation between two terms, consistent with the λ-calculus, has a Scott model. We consider such questions for wider sets of sentences and wider classes of models, the pointed (completely) partially ordered ones. A negative result for a set of sentences shows the impossibility of finding Scott models for that class; a positive result gives evidence that there might be enough Scott models. We find, for example, that the order-extensional pointed ω-cpo models are complete for Π1-sentences with positive matrices, whereas the consistency question for Σ1-sentences with equational matrices depends on the consistency of certain critical sentences asserting the existence of certain functions analogous to the generalized Mal’cev operators first considered in the context of the λ-calculus by Selinger