On the completeness of order-theoretic models of the lambda-calculus
Scott discovered his domain-theoretic models of the lambda-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 lambda-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 omega-cpo models are complete for Pi(1)-sentences with positive matrices, whereas the consistency question for Sigma(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 X-calculus by Selinger. (C) 2009 Elsevier Inc. All rights reserved.
completeness lambda-calculus consistency mal'cev operators domain theory