Back to search

National and Kapodistrian University of Athens

A logic for intersection and union types

Abstract

dc:description

We 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

Rights

dc:rights
Statement dc:rights
  • BY_ND
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/36745

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Veneti, Anastasia; Βενέτη, Αναστασία. A logic for intersection and union types. National and Kapodistrian University of Athens, 2015. http://hdl.handle.net/10442/hedi/36745