Scott 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.

On the Completeness of order-Theoretic Models of the lambda-calculus

HONSELL, Furio;
2009-01-01

Abstract

Scott 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.
File in questo prodotto:
File Dimensione Formato  
plotkin09.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Non pubblico
Dimensione 179.71 kB
Formato Adobe PDF
179.71 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/694038
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact