Constructing Infinitary Quotient-Inductive Types
Accepted version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Fiore, MP https://orcid.org/0000-0001-8558-3492
Pitts, AM https://orcid.org/0000-0001-7775-3471
Steenkamp, SC https://orcid.org/0000-0003-3105-4098
Abstract
This paper introduces an expressive class of quotient-inductive types, called QW-types. We show that in dependent type theory with uniqueness of identity proofs, even the infinitary case of QW-types can be encoded using the combination of inductive-inductive definitions involving strictly positive occurrences of Hofmann-style quotient types, and Abel's size types. The latter, which provide a convenient constructive abstraction of what classically would be accomplished with transfinite ordinals, are used to prove termination of the recursive definitions of the elimination and computation properties of our encoding of QW-types. The development is formalized using the Agda theorem prover.
Description
Keywords
dependent type theory, higher inductive types, inductive-inductive definitions, quotient types, sized types, category theory
Journal Title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Conference Name
23rd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2020)
Journal ISSN
0302-9743
1611-3349
1611-3349
Volume Title
12077 LNCS
Publisher
Springer International Publishing
Publisher DOI
Rights
All rights reserved
Sponsorship
EPSRC (2119809)