National and Kapodistrian University of Athens
A logic for intersection and union types
Abstract
dc:descriptionWe investigate the logical foundation of the type system with intersection and union types IUT in the perspective of the Curry-Howard isomorphism. In particular, we seek a logical system corresponding to IUT through a ''decoration'' with untyped terms that simulate the terms in IUT. The thesis consists of the following chapters. Chapter 1: A chapter that refers to the already established results in the field in question up until the strart of the thesis. We historically present the issue of defining a logic corresponding to the type system with intersection types IT by citing the basic points of the articles "Intersection Logic'' (by S. Ronchi Della Rocca and L. Roversi) and “Intersection Types from a Proof-theoretic Perspective” (by E. Pimentel, S. Ronchi Della Rocca and L. Roversi). Chapter 2: A chapter that presents the type system with intersection and union types IUT in natural deduction style and also in sequent calculus style. We describe and prove properties of the system, like subject reduction (under a notion of ''parallel'' reduction) and cut elimination. Furthermore, we prove four theorems that characterize λ-terms according to their typings in the type system. Chapter 3: A chapter that records the early research results on the logical foundation of the type system IUT in natural deduction style. We present the logical systems IULk and IULm (with implication, intersection, and union connectives) and prove theorems corresponding each of them to IUT through a decoration with λ-terms that simulate the terms in IUT. We explain how the substitution term in the union elimination rule hinders the proof of inverse theorems from IUT to the logical systems. We prove the equivalence of the two logical systems and discuss the advantages of the fornalism of IULm over the formalism of IULk. Chapter 4: A chapter that introduces a modified version of the logical system IULm (with respect to its structural chatacteristics and its rules) in natural deduction style and also presents anew the type system IUT in natural deduction style. We state and prove basic properties of the two systems and examine their relation through decoration. Chapter 5: A chapter that investigates the correspondence between IULm and IUT in natural deduction style. We define the notion ''tree of implications and union eliminations with terms'' for both the decorated logic and the type system, and prove theorems of correspondence through this notion. We show that non-compatible derivations in IUT (ie. derivations that do not share the same tree of implications and union eliminations with terms) cannot always be transformed, leaving the roots unaltered, to compatible derivations in IUT, which accounts for the fact that we cannot have theorems of correspondence without the notion of trees, solely on transformation grounds. Chapter 6: A chapter that examines the correspondence between the restricted-to-intersection systems ILm and IT in natural deduction style. We adjust the notion of tree, introduced in the previous chapter, to the restricted systems and prove theorems of correspondence through the adjusted notion. We also compare and contrast the correspondences IULm-IUT and ILm-IT. Chapter 7: A chapter that presents the (modified) logical system IULm and the type system IUT in sequent calculus style. The basic properties of the two systems are transferred and proved in the sequent calculus context. We also prove the equivalence of the two presentations (ie. in natural deduction and sequent calculus styles) for both systems. Finally, we relate the logic to the type system (through decoration) in the new context and state the correspondence between the two systems by adjusting the method of trees to the new context.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2015
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Veneti, Anastasia
- Βενέτη, Αναστασία
Subjects
dc:subject × 16- Συστήματα τύπων
- Τύποι τομής και ένωσης
- Ισομορφισμος Curry-Howard
- Λ-λογισμός
- Θεωρία αποδείξεων
- Type systems
- Intersection and union types
- Curry-Howard isomorphism
- L-calculus
- Proof theory
- Φυσικές Επιστήμες
- Μαθηματικά
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Mathematics
- Computer and Information Sciences
Rights
dc:rights- Statement dc:rights
-
- BY_ND
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/36745