First Steps Towards Cumulative Inductive Types in CIC


Amin Timany and Bart Jacobs: First Steps Towards Cumulative Inductive Types in CIC. In Proceedings of Theoretical Aspects of Computing - ICTAC 2015 - 12th International Colloquium, October 2015. https://doi.org/10.1007/978-3-319-25150-9_36
Conference Paper
Abstract.

Having the type of all types in a type system results in paradoxes like Russel's paradox. Therefore type theories like predicative calculus of inductive constructions (pCIC) — the logic of the Coq proof assistant — have a hierarchy of types Type0, Type1, Type2, ···, where Type0 : Type1, Type1 : Type2, ···. In a cumulative type system, e.g., pCIC, for a term t such that t: Typei we also have that t: Typei+1. The system pCIC has recently been extended to support universe polymorphism, i.e., definitions can be parametrized by universe levels. This extension does not support cumulativity for inductive types. For example, we do not have that a pair of types at levels i and j is also considered a pair of types at levels i + 1 and j + 1.

In this paper, we discuss our on-going research on making inductive types cumulative in the pCIC. Having inductive types be cumulative alleviates some problems that occur while working with large inductive types, e.g., the category of small categories, in pCIC.

We present the pCuIC system which adds cumulativity for inductive types to pCIC and briefly discuss some of its properties and possible extensions. We, in addition, give a justification for the introduced cumulativity relation for inductive types.

The bibtex source for this publication:
@inproceedings{DBLP:conf/ictac/Timany015,
  author    = {Amin Timany and,
 Bart Jacobs},
  title     = {First Steps Towards Cumulative Inductive Types in {CIC}},
  booktitle = {Theoretical Aspects of Computing - {ICTAC} 2015 - 12th International
               Colloquium Cali, Colombia, October 29-31, 2015, Proceedings},
  pages     = {608--617},
  year      = {2015},
  url       = {https://doi.org/10.1007/978-3-319-25150-9_36},
  doi       = {10.1007/978-3-319-25150-9_36},
  timestamp = {Tue, 23 May 2017 01:11:58 +0200},
  biburl    = {http://dblp.org/rec/bib/conf/ictac/Timany015},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}