Prototype proofs in type theory

被引:0
作者
Longo, G [1 ]
机构
[1] Ecole Normale Super, Dept Math & Informat, F-75005 Paris, France
关键词
universal quantification; impredicative definitions; type theory; lambda-calculus;
D O I
10.1002/(SICI)1521-3870(200005)46:2<257::AID-MALQ257>3.0.CO;2-V
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The proofs of universally quantified statements, in mathematics, are given as "schemata" or as "prototypes" which may be applied to each specific instance of the quantified variable. Type Theory allows to turn into a rigorous notion this informal intuition described by many, including Herbrand. In this constructive approach where propositions are types, proofs are viewed as terms of lambda-calculus and act as "proof-schemata", as for universally quantified types. We examine here the critical case of Impredicative Type Theory, i.e. Girard's system F, where type-quantification ranges over all types. Coherence and decidability properties are proved for prototype proofs in this impredicative context.
引用
收藏
页码:257 / 266
页数:10
相关论文
共 18 条
  • [1] Asperti Andrea, 1991, Categories, Types, and Structures
  • [2] BARDENDREGT H, 1990, HDB THEORETICAL COMP, VB, P165
  • [3] BELLE G, 1997, SYNTACTICAL PROPERTI
  • [4] CARDELLI L, 1994, INFORMATION COMPUTAT, V94, P4
  • [5] CARNAP R, 1964, PHILOS MATH SELECTED
  • [6] A CALCULUS FOR OVERLOADED FUNCTIONS WITH SUBTYPING
    CASTAGNA, G
    GHELLI, G
    LONGO, G
    [J]. INFORMATION AND COMPUTATION, 1995, 117 (01) : 115 - 135
  • [7] FRUCHART T, 1999, LOGIC METHODOLOGY PH
  • [8] Girard Jean-Yves, 1989, Cambridge Tracts in Theoretical Computer Science
  • [9] Girard Jean-Yves., 1971, SCANDINAVIAN LOGIC S, P63
  • [10] THE SYSTEM-F OF VARIABLE TYPES, 15 YEARS LATER
    GIRARD, JY
    [J]. THEORETICAL COMPUTER SCIENCE, 1986, 45 (02) : 159 - 192