A filter lambda model and the completeness of type assignment

Abstract

In [6, p. 317] Curry described a formal system assigning types to terms of the type-free λ -calculus. In [11] Scott gave a natural semantics for this type assignment and asked whether a completeness result holds. Inspired by [4] and [5] we extend the syntax and semantics of the Curry types in such a way that filters in the resulting type structure form a domain in the sense of Scott [12]. We will show that it is possible to turn the domain of types into a λ -model, among other reasons because all λ -terms possess a type. This model gives the completeness result for the extended system. By a conservativity result the completeness for Curry's system follows. Independently Hindley [8], [9] has proved both completeness results using term models. His method of proof is in some sense dual to ours. For λ -calculus notation see [1].