Reference. Impredicative Encodings of Inductive and Coinductive Types

In impredicative type theory (System F, also known as λ2), it is possible to define inductive data types, such as natural numbers and lists. It is also possible to define coinductive data types such as streams. They work well in the sense that their (co)recursion principles obey the expected computation rules (the β-rules). Unfortunately, they do not yield a (co)induction principle [Herman Geuvers, 2001; Ivar Rummelhoff, 2004], because the necessary uniqueness principles are missing (the η-rules). Awodey, Frey, and Speight [Steve Awodey et al., 2018] used an extension of the Calculus of Constructions [Thierry Coquand and Gérard P. Huet, 1988] (λ C) with Σ-types, identity-types, and functional extensionality to define System F style inductive types with an induction principle, by encoding them as a well-chosen subtype, making them initial algebras. In this paper, we extend their results to coinductive data types, and we detail the example of the stream data type with the desired coinduction principle (also called bisimulation). To do that, we first define quotient types (with the desired η-rules) and we also need a stronger form of the definable existential types. We also show that we can use the original method by Awodey, Frey and Speight for general inductive types by defining W-types with an induction principle. The dual approach for streams can be extended to M-types, the generic notion of coinductive types, and the dual of W-types.

Cite

Cite as @bronsveld-2025-impredicative (helia, typst) · \cite{bronsveld-2025-impredicative} (LaTeX)
BibTeX
bibtex · 14 lines
@inproceedings{bronsveld-2025-impredicative,
  doi = {10.4230/LIPICS.FSCD.2025.11},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2025.11},
  author = {Bronsveld, Steven and Geuvers, Herman and van der Weide, Niels},
  keywords = {Formulas-as-types, impredicativity, inductive types, coinductive types, Theory of computation → Type theory},
  language = {en},
  title = {Impredicative Encodings of Inductive and Coinductive Types},
  volume = {337},
  pages = {11:1-11:22},
  publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
  year = {2025},
  copyright = {Creative Commons Attribution 4.0 International license},
  booktitle = {10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)}
}
hayagriva YAML (typst)
yaml · 19 lines
bronsveld-2025-impredicative:
  type: article
  title: Impredicative Encodings of Inductive and Coinductive Types
  author:
  - Bronsveld, Steven
  - Geuvers, Herman
  - name: Weide
    given-name: Niels
    prefix: van der
  date: 2025
  page-range: 11:1-11:22
  url: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2025.11
  serial-number:
    doi: 10.4230/LIPICS.FSCD.2025.11
  parent:
    type: proceedings
    title: 10th International Conference on Formal Structures for Computation and Deduction (FSCD 2025)
    publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    volume: 337
Cited by (1)

Impredicativity in Linear Dependent Type Theory speight-2026-impredicativity

We construct a realizability model of linear dependent type theory from a linear combinatory algebra. Our model motivates a number of additions to the type theory. In particular, we add a universe with two decoding operations: one takes codes to cartesian types and the other takes codes to linear types. The universe is impredicative in the sense that it is closed under both large cartesian dependent products and large linear dependent products. We also add a rule for injectivity of the modality turning linear terms into cartesian terms. With all of the additions, we are able to encode (linear) inductive types. As a case study, we consider the type of lists over a linear type, and demonstrate that our encoding has the relevant uniqueness principle. The construction of the realizability model is fully formalized in the proof assistant Rocq.
arXiv
Cites 38 works (2 here)
With notes (2)

Internal Parametricity, without an Interval altenkirch-2024-internal

Parametricity is a property of the syntax of type theory implying, e.g., that there is only one function having the type of the polymorphic identity function. Parametricity is usually proven externally, and does not hold internally. Internalising it is difficult because once there is a term witnessing parametricity, it also has to be parametric itself and this results in the appearance of higher dimensional cubes. In previous theories with internal parametricity, either an explicit syntax for higher cubes is present or the theory is extended with a new sort for the interval. In this paper we present a type theory with internal parametricity which is a simple extension of Martin-Löf type theory: there are a few new type formers, term formers and equations. Geometry is not explicit in this syntax, but emergent: the new operations and equations only refer to objects up to dimension 3. We show that this theory is modelled by presheaves over the BCH cube category. Fibrancy conditions are not needed because we use span-based rather than relational parametricity. We define a gluing model for this theory implying that external parametricity and canonicity hold. The theory can be seen as a special case of a new kind of modal type theory, and it is the simplest setting in which the computational properties of higher observational type theory can be demonstrated.
PDF · DOI · arXiv · pldb

Homotopy Type Theory: Univalent Foundations of Mathematics hottbook

Web · arXiv
External (36)
bronsveld-2025-impredicative reference entries/refs/bronsveld-2025-impredicative/bronsveld-2025-impredicative.hel