loading...
Remarks on Isomorphisms in Typed Lambda Calculi with Empty and Sum Types
Copenhagen, Denmark July 22-July 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2002.102982417th Annual IEEE Symposium on Logic i ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Marcelo Fiore, University of Cambridge
Roberto Di Cosmo, Université Paris 7 and INRIA-Roquencourt
Vincent Balat, Université Paris 7
Tarski asked whether the arithmetic identities taught in high school are complete for showing all arithmetic equations valid for the natural numbers. The answer to this question for the language of arithmetic expressions using a constant for the number one and the operations of product and exponentiation is affirmative, and the complete equational theory also characterises isomorphism in the typed lambda calculus, where the constant for one and the operations of product and exponentiation respectively correspond to the unit type and the product and arrow type constructors. This paper studies isomorphisms in typed lambda calculi with empty and sum types from this viewpoint. We close an open problem by establishing that the theory of type isomorphisms in the presence of product, arrow, and sum types (with or without the unit type) is not finitely axiomatisable. Further, we observe that for type theories with arrow, empty and sum types the correspondence between isomorphism and arithmetic equality generally breaks down, but that it still holds in some particular cases including that of type isomorphism with the empty type and equality with zero.
Citation:
Marcelo Fiore, Roberto Di Cosmo, Vincent Balat, "Remarks on Isomorphisms in Typed Lambda Calculi with Empty and Sum Types," lics, pp.147, 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.