• DocumentCode
    2597025
  • Title

    Non trivial power types can´t be subtypes of polymorphic types

  • Author

    Pitt, A.M.

  • Author_Institution
    Comput. Lab., Cambridge Univ.
  • fYear
    1989
  • fDate
    5-8 Jun 1989
  • Firstpage
    6
  • Lastpage
    13
  • Abstract
    A new, limitative relation between the polymorphic lambda calculus and the kind of higher-order type theory embodied in the logic of topoi is established. It is shown that any embedding in a topos of the Cartesian closed category of (closed) types of a model of the polymorphic lambda calculus must place the polymorphic types well away from the power types σ→Ω of the topos, in the sense that σ→Ω is a subtype of a polymorphic type only in the case that σ is empty (and hence σ→Ω is terminal). As corollaries, strengthening of the Reynolds result on the nonexistence of set-theoretic models of polymorphism are obtained
  • Keywords
    algebra; formal logic; set theory; Cartesian closed category; Reynolds result; embedding; empty; higher-order type theory; limitative relation; logic of topoi; nontrivial power types; polymorphic lambda calculus; polymorphic types; set-theoretic models; subtypes; terminal; Algebra; Calculus; Integrated circuit modeling; Laboratories; Logic; Terminology;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 1989. LICS '89, Proceedings., Fourth Annual Symposium on
  • Conference_Location
    Pacific Grove, CA
  • Print_ISBN
    0-8186-1954-6
  • Type

    conf

  • DOI
    10.1109/LICS.1989.39154
  • Filename
    39154