Reference. Cumulative Inductive Types In Coq
Cite
Cited by (1)
Bounded First-Class Universe Levels in Dependent Type Theory chan-2025-bounded
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.
External (17)
- The next 700 syntactical models of type theory (2017)
- The Coq Proof Assistant, version 8.7.1 (2017)
- Consistency of the Predicative Calculus of Cumulative Inductive Constructions (pCuIC) (2017)
- First Steps Towards Cumulative Inductive Types in CIC (2015)
- Universe Polymorphism in Coq (2014)
- Dependently typed lambda calculus with a lifting operator (2014)
- Pure Type System conversion is always typable (2012)
- Semantical Investigation in Intuitionistic Set Theory and Type Theories with Inductive Families (2012)
- Proof-irrelevant model of CC with predicative induction and judgmental equality (2011)
- On Relating Type Theories and Set Theories (1999)
- Définitions Inductives en Théorie des Types d'Ordre Supérieur (1996)
- A simplification of Girard's paradox (1995)
- Inductive sets and families in Martin-Löf's type theory and their set-theoretic semantics (1991)
- Type checking, universe polymorphism, and typical ambiguity in the calculus of constructions (1989)
- An Introduction to Inductive Definitions (1977)
- Set Theory - An Introduction to Large Cardinals (1974)
- Interprétation fonctionelle et élimination des coupures de l'arithmétique d'ordre supérieur (1972)