Repository logo
 

QUOTIENTS, INDUCTIVE TYPES, & QUOTIENT INDUCTIVE TYPES

Published version
Peer-reviewed

Type

Article

Change log

Authors

Fiore, MP 
Pitts, AM 
Steenkamp, SC 

Abstract

This paper introduces an expressive class of indexed quotient-inductive types, called QWI types, within the framework of constructive type theory. They are initial algebras for indexed families of equational theories with possibly infinitary operators and equations. We prove that QWI types can be derived from quotient types and inductive types in the type theory of toposes with natural number object and universes, provided those universes satisfy the Weakly Initial Set of Covers (WISC) axiom. We do so by constructing QWI types as colimits of a family of approximations to them defined by well-founded recursion over a suitable notion of size, whose definition involves the WISC axiom. We developed the proof and checked it using the Agda theorem prover.

Description

Keywords

dependent type theory, higher inductive types, quotient types, well-founded relation, weakly initial set of covers, topos theory

Journal Title

Logical Methods in Computer Science

Conference Name

Journal ISSN

1860-5974
1860-5974

Volume Title

18

Publisher

Centre pour la Communication Scientifique Directe (CCSD)
Sponsorship
EPSRC (2119809)
Relationships
Is supplemented by: