Reference. Cumulative Inductive Types In Coq

In order to avoid well-known paradoxes associated with self-referential definitions, higher-order dependent type theories stratify the theory using a countably infinite hierarchy of universes (also known as sorts), Type0:Type1:…. Such type systems are called cumulative if for any type A we have that 𝐴:Type𝑖 implies 𝐴:Type𝑖+1. The Predicative Calculus of Inductive Constructions (pCIC) which forms the basis of the Coq proof assistant, is one such system. In this paper we present the Predicative Calculus of Cumulative Inductive Constructions (pCuIC) which extends the cumulativity relation to inductive types. We discuss cumulative inductive types as present in Coq 8.7 and their application to formalization and definitional translations.

Cite

Cite as @timany-2018-cumulative (helia, typst) · \cite{timany-2018-cumulative} (LaTeX)
BibTeX
bibtex · 14 lines
@inproceedings{timany-2018-cumulative,
  doi = {10.4230/LIPICS.FSCD.2018.29},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2018.29},
  author = {Timany, Amin and Sozeau, Matthieu},
  keywords = {Coq, Proof Assistants, Inductive Types, Universes, Cumulativity},
  language = {en},
  title = {Cumulative Inductive Types In Coq},
  volume = {108},
  pages = {29:1-29:16},
  publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
  year = {2018},
  copyright = {Creative Commons Attribution 3.0 Unported license},
  booktitle = {3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)}
}
hayagriva YAML (typst)
yaml · 16 lines
timany-2018-cumulative:
  type: article
  title: Cumulative Inductive Types In Coq
  author:
  - Timany, Amin
  - Sozeau, Matthieu
  date: 2018
  page-range: 29:1-29:16
  url: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2018.29
  serial-number:
    doi: 10.4230/LIPICS.FSCD.2018.29
  parent:
    type: proceedings
    title: 3rd International Conference on Formal Structures for Computation and Deduction (FSCD 2018)
    publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    volume: 108
Cited by (1)

Bounded First-Class Universe Levels in Dependent Type Theory chan-2025-bounded

In dependent type theory, being able to refer to a type universe as a term itself increases its expressive power, but requires mechanisms in place to prevent Girard’s paradox from introducing logical inconsistency in the presence of type-in-type. The simplest mechanism is a hierarchy of universes indexed by a sequence of levels, typically the naturals. To improve reusability of definitions, they can be made level polymorphic, abstracting over level variables and adding a notion of level expressions. For even more expressive power, level expressions can be made first-class as terms themselves, and level polymorphism is subsumed by dependent functions quantifying over levels. Furthermore, bounded level polymorphism provides more expressivity by being able to explicitly state constraints on level variables. While semantics for first-class levels with constraints are known, syntax and typing rules have not been explicitly written down. Yet pinning down a well-behaved syntax is not trivial; there exist prior type theories with bounded level polymorphism that fail to satisfy subject reduction. In this work, we design an explicit syntax for a type theory with bounded first-class levels, parametrized over arbitrary well-founded sets of levels. We prove the metatheoretic properties of subject reduction, type safety, consistency, and canonicity, entirely mechanized from syntax to semantics in Lean.
arXiv
Cites 18 works (1 here)
With notes (1)

Category Theory in Coq 8.5 timany-2016-category

We report on our experience implementing category theory in Coq 8.5. Our work formalizes most of basic category theory, including concepts not covered by existing formalizations, in a library that is fit to be used as a general-purpose category-theoretical foundation.

Our development particularly takes advantage of two features new to Coq 8.5: primitive projections for records and universe polymorphism. Primitive projections allow for well-behaved dualities while universe polymorphism provides a relative notion of largeness and smallness. The latter is one of the main contributions of this paper. It pushes the limits of the new universe polymorphism and constraint inference algorithm of Coq 8.5.

In this paper we present in detail smallness and largeness in categories and the foundation they are built on top of. We furthermore explain how we have used the universe polymorphism of Coq 8.5 to represent smallness and largeness arguments by simply ignoring them and entrusting them to the universe inference algorithm of Coq 8.5. We also briefly discuss our experience throughout this implementation, discuss concepts formalized in this development and give a comparison with a few other developments of similar extent.

DOI
External (17)
timany-2018-cumulative reference entries/refs/timany-2018-cumulative/timany-2018-cumulative.hel