Un Résultat de Complétude pour les Types ∀ +

• Main Author: Du Système F
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Subjects: sami
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.251.490; http://arxiv.org/pdf/0905.0592v1.pdf

Résumé. Nous présentons dans cette note un résultat de complétude pour les types à quantificateurs positifs du système F de J.-Y. Girard. Ce résultat généralise un théorème de R. Labib-Sami (voir [3]). A Completeness Result for the ∀ + Types of System F Abstract. We presente in this note a completeness result for the types with positive quantifiers of the J.-Y. Girard type system F. This result generalizes a theorem of R. Labib-Sami (see [3]). Abridged English Version. The F type system have been introduced by J.-Y. Girard (see [1]). This system is based on the second order intuitionistic propositional calculus, and thus it gives the possibility to quantify on types. In addition to strong normalisation theorem which certifies the termination of programs, the system F has two more properties: It allows to write programs for all the fonctions whose termination can be proved in the Peano’s second order arithmetics.- It allows to define all the usual data types: booleans, integers, lists, etc.