Variations on inductive-recursive definitions

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

1 Citation (Scopus)
53 Downloads (Pure)


Dybjer and Setzer introduced the definitional principle of inductive-recursively defined families — i.e. of families ( U : Set , T : U → D ) such that the inductive definition of U may depend on the recursively defined T — by defining a type DS D E of codes. Each c : DS D E defines a functor J c K : Fam D → Fam E , and ( U , T ) = μ J c K : Fam D is exhibited as the initial algebra of J c K . This paper considers the composition of DS -definable functors: Given F : Fam C → Fam D and G : Fam D → Fam E , is G ◦ F : Fam C → Fam E DS -definable, if F and G are? We show that this is the case if and only if powers of families are DS -definable, which seems unlikely. To construct composition, we present two new systems UF and PN of codes for inductive-recursive definitions, with UF ↪ → DS ↪ → PN . Both UF and PN are closed under composition. Since PN defines a potentially larger class of functors, we show that there is a model where initial algebras of PN -functors exist by adapting Dybjer-Setzer’s proof for DS .
Original languageEnglish
Title of host publicationProceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science
Place of PublicationGermany
Number of pages13
Publication statusPublished - 30 Nov 2017
Event42nd International Symposium on Mathematical Foundations of Computer Science - Aalborg, Denmark
Duration: 21 Aug 201725 Aug 2017

Publication series

NameLeibniz International Proceedings in Informatics
Publisher Schloss Dagstuhl – Leibniz Center for Informatics


Conference42nd International Symposium on Mathematical Foundations of Computer Science
Abbreviated titleMFCS 2017
Internet address


  • type theory
  • induction recursion
  • initial algebra semantics


Dive into the research topics of 'Variations on inductive-recursive definitions'. Together they form a unique fingerprint.

Cite this