TL;DR
This paper provides a direct proof of Morita equivalence between extensional type theory (ETT) and intensional type theory with uniqueness of identity proofs (ITT+UIP). This result generalizes a classic theorem by Hofmann, showing that not just the initial models, but all "cofibrant extensions" of these theories are equivalent, simplifying future work on type theory extensions.
What Problem Does This Paper Address?
Type theory is a foundational framework for formalizing mathematics and computer science. It comes in two main flavors: intensional and extensional. Intensional type theory (ITT) distinguishes between proofs that are definitionally equal, while extensional type theory (ETT) considers them equal if they are propositionally equal. A key result by Martin Hofmann showed that ETT is a conservative extension of ITT, meaning that any theorem provable in ETT is also provable in ITT. This was demonstrated by constructing an interpretation of ETT within ITT.
However, Hofmann's proof was quite specific to the initial models of these theories. As new variants and extensions of ITT are constantly proposed, proving their equivalence to ETT for each new extension becomes a burden. This paper addresses the need for a more general result that covers not just initial models but also all "cofibrant extensions" (extensions that don't impose new definitional equalities). The authors aim to provide a direct proof of Morita equivalence, a notion of equivalence between type theories that generalizes Hofmann's result and applies to categories of models.
Methods
The paper's core contribution is a direct proof of Morita equivalence between ETT and ITT+UIP. The authors build upon Hofmann's original approach but introduce a key innovation to handle general cofibrant extensions.
- Extensional Kernel: They define a subcategory called the "extensional kernel" (WETT) within the category of models of ITT+UIP. This subcategory consists of specific maps that are identified as "weak equivalences" in a homotopical sense.
- Quotient Construction: They then construct a model of ETT by "collapsing" all maps in WETT to identities. This is achieved through a quotient construction, effectively identifying all proofs that are propositionally equal.
- Morita Equivalence: The authors then demonstrate that this construction yields a Morita equivalence between ETT and ITT+UIP. This involves showing that the resulting category of models of ETT is equivalent to the category of models of ITT+UIP in a specific homotopical sense (a Quillen adjunction).
A significant aspect of their method is the reliance on the "cofibrancy" of models. Cofibrant models, which are freely generated by types and terms without new definitional equalities, allow them to recover certain syntactic properties that are crucial for their proof, even when working with general models rather than just syntactic ones.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Generalizing Hofmann: The paper successfully generalizes Hofmann's conservativity result from initial models to all cofibrant extensions of type theories. This means the equivalence holds more broadly than previously shown.
- Morita Equivalence as a Tool: The authors leverage the concept of Morita equivalence to provide a unified framework for proving equivalences between type theories. This is a powerful abstraction that simplifies reasoning about different type-theoretic systems.
- The Role of Cofibrancy: Cofibrancy plays a crucial role in bridging the gap between syntactic constructions and general models. It allows the authors to exploit structural properties that are reminiscent of syntax, even in more abstract settings.
- UIP as a Unifying Principle: The uniqueness of identity proofs (UIP) in ITT+UIP is shown to be instrumental in collapsing homotopic maps to identities, which is central to the construction of the extensional model.
Key Results
- Morita Equivalence Proven: The paper provides a direct proof that extensional type theory (ETT) and intensional type theory with uniqueness of identity proofs (ITT+UIP) are Morita equivalent.
- Generalization of Hofmann's Theorem: This result extends Hofmann's theorem from initial models to all cofibrant extensions of these type theories.
- Construction of Extensional Models: The paper details a method for constructing models of ETT from models of ITT+UIP by collapsing certain weak equivalences to identities.
- Adjunction Established: The paper establishes a free-forgetful adjunction between the categories of models of ITT+UIP and ETT, which satisfies the conditions for a Morita equivalence.
Limitations and Future Work
- Constructive Proof: The authors acknowledge that their proof relies on the axiom of choice, similar to Hofmann's and Bocquet's work. They suggest that investigating a constructive proof of Morita equivalence is a worthwhile direction for future research.
- Modular Approach: The current proof relies on the left semi-model structure on contextual categories. The authors propose exploring a more modular approach that depends solely on the homotopical structure of models, potentially leading to a deeper understanding of the "extensional collapse."
- Generalizations: The paper suggests exploring other examples of Morita equivalences between dependent type theories and generalizing the notion of Morita equivalence to other type theories, potentially serving as a framework for comparing different cubical type theories and their relation to homotopy type theory.
Summary updated