Natural numbers from integers
Christian Sattler, David Wärn
Abstract
In homotopy type theory, a natural number type is freely generated by an element and an endomorphism. Similarly, an integer type is freely generated by an element and an automorphism. Using only dependent sums, identity types, extensional dependent products, and a type of two elements with large elimination, we construct a natural number type from an integer type. As a corollary, homotopy type theory with only Σ, Id, Π, and finite colimits with descent (and no universes) admits a natural number type. This improves and simplifies a result by Rose.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 0176c379-91af-4cd9-8626-d2e2ac805d87Related papers
- The Integers as a Higher Inductive TypeThorsten Altenkirch, Luis ScoccolaLICS 2020 · 11 citations
- Set-Theoretic and Type-Theoretic Ordinals CoincideTom de Jong, Nicolai Kraus, Fredrik Nordvall Forsberg, Chuangjie XuLICS 2023 · 4 citations
- Primitive Recursive Dependent Type TheoryUlrik Torben Buchholtz, Johannes Schipp von BranitzLICS 2024
- Constructing Higher Inductive Types as Groupoid QuotientsNiels van der WeideLICS 2020 · 1 citation
- Ordinal Exponentiation in Homotopy Type TheoryTom de Jong, Nicolai Kraus, Fredrik Nordvall Forsberg, Chuangjie XuLICS 2025 · 1 citation
