Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T01:10:51.556Z Has data issue: false hasContentIssue false

βη-complete models for System F

Published online by Cambridge University Press:  17 January 2003

STEFANO BERARDI
Affiliation:
Dipartimento di Informatica, Università degli Studi di Torino, Corso Svizzera 185, 10149 Torino, Italia Email: stefano@di.unito.it URL: www.di.unito.it/~stefano
CHANTAL BERLINE
Affiliation:
Equipe PPS (CNRS), UFR de Mathématiques (case 7012), Université Paris 7, 2 place Jussieu, 75251 Paris Cedex 05, France E-mail: berline@pps.jussieu.fr URL: www.logique.jussieu.fr/www.berline
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that Friedman's proof of the existence of non-trivial βη-complete models of λ→ can be extended to system F. We isolate a set of conditions that are sufficient to ensure βη-completeness for a model of F (and α-completeness at the level of types), and we discuss which class of models we get. In particular, the model introduced in Barbanera and Berardi (1997), having as polymorphic maps exactly all possible Scott continuous maps, is βη-complete, and is hence the first known complete non-syntactic model of F. In order to have a suitable framework in which to express the conditions and develop the proof, we also introduce the very natural notion of ‘polymax models’ of System F.

Information

Type
Research Article
Copyright
2002 Cambridge University Press