Bootstrapping extensionality
Intuitionistic type theory is a formal system designed by Per Martin-Loef to be a full-fledged foundation in which to develop constructive mathematics. One particular variant, intensional type theory (ITT), features nice computational properties like decidable type-checking, making it especially sui...
| Main Author: | |
|---|---|
| Format: | Thesis (University of Nottingham only) |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/74363/ |
| _version_ | 1848800860896755712 |
|---|---|
| author | Sestini, Filippo |
| author_facet | Sestini, Filippo |
| author_sort | Sestini, Filippo |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | Intuitionistic type theory is a formal system designed by Per Martin-Loef to be a full-fledged foundation in which to develop constructive mathematics. One particular variant, intensional type theory (ITT), features nice computational properties like decidable type-checking, making it especially suitable for computer implementation. However, as traditionally defined, ITT lacks many vital extensionality principles, such as function extensionality. We would like to extend ITT with the desired extensionality principles while retaining its convenient computational behaviour. To do so, we must first understand the extent of its expressive power, from its strengths to its limitations.
The contents of this thesis are an investigation into intensional type theory, and in particular into its power to express extensional concepts. We begin, in the first part, by developing an extension to the strict setoid model of type theory with a universe of setoids. The model construction is carried out in a minimal intensional type theoretic metatheory, thus providing a way to bootstrap extensionality by ``compiling'' it down to a few building blocks such as inductive families and proof-irrelevance.
In the second part of the thesis we explore inductive-inductive types (ITTs) and their relation to simpler forms of induction in an intensional setting. We develop a general method to reduce a subclass of infinitary IITs to inductive families, via an encoding that can be expressed in ITT without any extensionality besides proof-irrelevance. Our results contribute to further understand IITs and the expressive power of intensional type theory, and can be of practical use when formalizing mathematics in proof assistants that do not natively support induction-induction. |
| first_indexed | 2025-11-14T20:58:17Z |
| format | Thesis (University of Nottingham only) |
| id | nottingham-74363 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:58:17Z |
| publishDate | 2023 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-743632024-02-14T12:42:12Z https://eprints.nottingham.ac.uk/74363/ Bootstrapping extensionality Sestini, Filippo Intuitionistic type theory is a formal system designed by Per Martin-Loef to be a full-fledged foundation in which to develop constructive mathematics. One particular variant, intensional type theory (ITT), features nice computational properties like decidable type-checking, making it especially suitable for computer implementation. However, as traditionally defined, ITT lacks many vital extensionality principles, such as function extensionality. We would like to extend ITT with the desired extensionality principles while retaining its convenient computational behaviour. To do so, we must first understand the extent of its expressive power, from its strengths to its limitations. The contents of this thesis are an investigation into intensional type theory, and in particular into its power to express extensional concepts. We begin, in the first part, by developing an extension to the strict setoid model of type theory with a universe of setoids. The model construction is carried out in a minimal intensional type theoretic metatheory, thus providing a way to bootstrap extensionality by ``compiling'' it down to a few building blocks such as inductive families and proof-irrelevance. In the second part of the thesis we explore inductive-inductive types (ITTs) and their relation to simpler forms of induction in an intensional setting. We develop a general method to reduce a subclass of infinitary IITs to inductive families, via an encoding that can be expressed in ITT without any extensionality besides proof-irrelevance. Our results contribute to further understand IITs and the expressive power of intensional type theory, and can be of practical use when formalizing mathematics in proof assistants that do not natively support induction-induction. 2023-12-12 Thesis (University of Nottingham only) NonPeerReviewed application/pdf en cc_by https://eprints.nottingham.ac.uk/74363/1/main.pdf Sestini, Filippo (2023) Bootstrapping extensionality. PhD thesis, University of Nottingham. type theory agda iits extensionality setoids |
| spellingShingle | type theory agda iits extensionality setoids Sestini, Filippo Bootstrapping extensionality |
| title | Bootstrapping extensionality |
| title_full | Bootstrapping extensionality |
| title_fullStr | Bootstrapping extensionality |
| title_full_unstemmed | Bootstrapping extensionality |
| title_short | Bootstrapping extensionality |
| title_sort | bootstrapping extensionality |
| topic | type theory agda iits extensionality setoids |
| url | https://eprints.nottingham.ac.uk/74363/ |