Constructing (Co)inductive Types via Large Sizes

Benno van den Berg, Bastiaan Laarakker, Daniël Otten · 2026

Read Constructing (Co)inductive Types via Large Sizes by Benno van den Berg, Bastiaan Laarakker, Daniël Otten (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-18921.txt.

Description

Proof assistants need a way to admit only programs that stop, and corecursive programs that keep producing. Bastiaan Laarakker, with two co-authors, investigates sized types in 2026 as a type-based alternative to the usual syntactic rules, which can be restrictive and hard to combine. With sized types, inductive and coinductive types carry extra size data, and well-founded induction on sizes proves termination and productivity.

Agda already has sized types, but adding a largest size broke its consistency. The authors instead extend intensional type theory by adding a large type of sizes, plus parametric quantifiers over sizes, and in that theory both kinds of types can be built. That goes past earlier work, which managed only finitely-branching inductive types. Consistency rests on an impredicative realisability model that treats the size type as an uncountable ordinal.

Catalog record

CREATORBenno van den Berg, Bastiaan Laarakker, Daniël Otten
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-18921

Browse the full library · About the Tower of Babel