WorksComputer Science
Type classifiers
Abstract
We extend dependent type theory by type classifiers and construct an interpretation in the category of contextual categories with families. Type classifiers extend contexts by type variables, complementing the usual context extensions by term variables of specified types. This allows statements with arbitrary type parameters to be formulated without assuming a universe. We show that substituting isomorphic types induces isomorphisms between the resulting types even in extensional type theory, giving an analogue of the invariance supplied by the univalence axiom in homotopy type theory. Omitting function types from the theory, so that all type formers are covariant, extends this naturality to arbitrary, possibly noninvertible maps.
Introduction
Many mathematical assertions involve a free type parameter. A theorem about all groups, for example, must quantify over all possible carrier types. In dependent type theory, such quantification is usually expressed using universe types, whose elements encode types. This approach works well in practice, but it has limitations.
Girard’s paradox rules out a universe that contains itself. We can thus either restrict the theorem to small types, those classified by a chosen universe, or introduce an infinite hierarchy and use universe polymorphism to quantify over its levels . But universe polymorphism only shifts the quantification problem, since types quantifying over the whole indexed hierarchy need not belong to any of its universes. Such types can be interpreted in a larger universe , but this universe then lies outside the hierarchy over which we quantified. The quantification still fails to cover all types of the enlarged theory.
A further drawback is that universe closure axioms increase the proof-theoretic strength of the theory [5 Section 4], often unnecessarily. For example, when elementary results about groups are formulated using universes, the existence of those universes must be assumed even though they are not needed for the proofs. The resulting formalization cannot be interpreted directly in small models without those universes, even when the arguments could be carried out there.
We introduce type classifiers for extending contexts by free type parameters, alongside the usual extensions by term parameters. Their universal property permits substitution by any closed type. We thus obtain a context classifying all types, rather than a type classifying all types. A theorem about all groups, for example, is represented by a type in a context containing a free type variable for the carrier type and parameters for the group structure. It can be specialized by substitution to any particular group. The theorem is formulated in this extended context, rather than as a dependent product over a universe in the empty context.
The notion of a type classifier is analogous to that of a relative object classifier in topos theory. Such a classifier exists over every Grothendieck topos, with the universal property that geometric morphisms into it over the base correspond to objects of the domain topos. In particular, sections correspond to objects of the base topos. This similarly permits reasoning about arbitrary objects without requiring an internal universe object classifying them.
The main contribution of this article is a model of dependent type theory interpreting type classifiers. Standard models are typically democratic, meaning that every context is represented by a closed type. A context classifying all types would then yield a universe classifying all types, including itself, which is ruled out by Girard’s paradox. We use a simplified version of the big model construction for locally cartesian closed (lcc) categories introduced in [2]. Contexts in big models are themselves small models of type theory, in our case contextual categories with families (cwfs). A type or term at a context is a closed type or term of the cwf , and covariant substitutions are functors that preserve the cwf structure and type and term formers.
In the big model construction based on lcc categories, considerable effort is needed to obtain well-behaved context extensions by term variables. Working with contextual cwfs simplifies this step: By a result of Bocquet, Kaposi, and Sattler [3 Lemma 25], freely adjoining a term of a given closed type yields the contextual coslice, with a universal property for strict morphisms of cwfs. Type classifiers are then obtained as coproducts with the free contextual cwf on one closed type.
As a category of categories, the big model also has 2-categorical structure: its substitutions are functors, and we can therefore consider natural transformations between substitutions. We show that substituting isomorphic types into a type classifier gives naturally isomorphic substitutions, inducing isomorphisms between the resulting types.
This naturality can itself be expressed in the type theory by additional operators and equations. The resulting extension gives an analogue of the invariance supplied by the univalence axiom in homotopy type theory, even for extensional type theory. Omitting function types from the theory, so that all type formers are covariant, extends the naturality to arbitrary, possibly noninvertible maps.
Preliminaries
A covariant cwf on a category is an ordinary cwf structure [1 Section 2] on , as in [2 Definition 14].1 Thus has a chosen initial empty context , sets of types, and sets of terms. We write substitution as function application: for , the substituted type and term are and . Functoriality of substitution means that and , and similarly for terms.
We call ordinary context extensions term classifiers to distinguish them from extensions by type parameters, as provided by the type classifiers introduced in § 3. For , a term classifier consists of a context , a morphism and a generic term
Its universal property is that, for and , there is a unique morphism such that and .
Let be a dependent type theory presented as an essentially algebraic extension of cwfs by substitution-stable type and term formers. Examples include theories with intensional or extensional identity types, dependent sums and products, unit types, and natural numbers. Write for the category of small covariant cwfs with this structure and strict morphisms: Functors equipped with compatible actions on types and terms, preserving the chosen empty context, term classifiers, and type and term formers up to equality.
A telescope over is a finite list of successive types, with evaluation and composite classifier map . A cwf is contextual if each context has a unique telescope presentation over . Write for the full subcategory of contextual models.
We recall the contextual slice construction of Bocquet, Kaposi, and Sattler [3 Appendix A.2], reversing all context arrows to follow our convention. For any cwf and context of , the contextual coslice is the contextual cwf whose contexts are telescopes over and whose morphisms are maps satisfying . Types and terms at , together with their formers, are those of at . The empty telescope is initial, and a term classifier is obtained by appending the given type to the telescope.
For , transport is defined by iterating the pushout squares determined by term classifiers along a telescope. The comparison map at is denoted by . The image of a telescope morphism is the induced map between these pushouts, while transport of types and terms is given by the action of in . A strict morphism induces a strict morphism . The assignment is functorial [3 after Definition 22]:
Transport is compatible with strict morphisms:
Evaluation is strict, and every strict morphism from a contextual model into factors uniquely through it. If is contextual, is a strict isomorphism [3 Section 2.3 and Corollary 24]. The coslice of at is strictly isomorphic to by concatenation of telescopes [3 proof of Lemma 26].
For a contextual and a closed type , define
The map is given by transport along the term-classifier map , composed with . The generic term is a closed term of type in . The following is the universal property proved in [3 Lemma 25], expressed for covariant cwfs.
Proposition 1. For every there is a natural bijection
Type classifiers and the big model
Our goal is to give an interpretation of a type theory in which contexts can be extended by free type variables. The precise presentation depends on the other rules of the type theory, but one possible presentation is by the following rule set:
Here ranges over type and term judgments and their judgmental equalities. The expressions and denote replacement of by , avoiding variable capture.
Regardless of the precise syntactic presentation, we expect such context extensions to be interpreted in covariant cwfs as type classifiers:
Definition 2. A type classifier at a context of a covariant cwf consists of a context , a morphism , and a type , with the following universal property: for every and there is a unique morphism such that
The following is our main result.
Theorem 3. The category has a covariant cwf structure with
It supports the type and term formers of and type classifiers at all contexts.
Proof. The empty context is the initial contextual model. For the term classifier at , take with the structure map and generic term of Proposition 1.
By definition of the contextual coslice, we have the literal equalities
By iterating (3), types and terms over successive term classifiers in the big model can be identified with types and terms in the corresponding telescopes of . The type and term formers can thus be defined using those of , with the same equations. Compatibility with substitution in the big cwf follows from compatibility of transport with strict morphisms and their preservation of the type and term formers.
For type classifiers, let be the free contextual -cwf on a single closed type. Such a free model and coproducts exist because contextual -cwfs admit an essentially algebraic presentation [1 Section 5.7]. Put , with the coproduct inclusion and the image of the generating type of . By the coproduct universal property, this is a type classifier at .
Now consider isomorphic types in a context of the big model and the induced functors , where and . Does the isomorphism extend to isomorphisms for every type ? If the type formers of are well-behaved, the answer is yes, by the following theorem.
Theorem 4. Suppose the type and term formers of are functorial with respect to invertible maps between types. Then for every strict between contextual models and closed types of , there is a natural bijection
If the type and term formers are functorial with respect to arbitrary maps between types, there is also a natural bijection
On the left, denotes -natural isomorphisms between the indicated functors whose restriction along is the identity on . Here -naturality means that the comparison for each type former is the one induced by the comparisons of its arguments. For type formers characterized by universal diagrams of context morphisms, this condition follows from naturality. On the right, denotes invertible maps between types in , identified with isomorphisms of their term classifiers. Likewise, denotes -natural transformations restricting to the identity on , and denotes context morphisms , or equivalently open terms . The
reversed order in the second bijection is thus due to our use of covariant rather than contravariant cwfs.
We leave the notion of functoriality of type and term formers informal so as to avoid having to define a general notion of dependent type theory or type former. Informally, given compatible (invertible) maps between the arguments of a type former, we expect an (invertible) map between the resulting types, and the corresponding term formers should respect these maps. These actions are assumed to respect the equations of and to commute with substitution and strict morphisms. In extensional type theory, unit types, finite sums, dependent sums, identity types, and natural numbers are functorial even with respect to noninvertible maps. Dependent products require invertible maps owing to the mixed variance of their arguments.
Intensional identity types require care because the functoriality laws must hold judgmentally. For the usual action defined by identity elimination, even need not hold judgmentally for a variable . Strictly inverse maps between the underlying types therefore do not by themselves give judgmentally inverse maps on identity types by this construction. For cubical path types, by contrast, the induced maps typically satisfy the identity and composition laws judgmentally; see, for example, [4 Sections 3.1–3.2]. A similar issue occurs for intensional W-types, whose usual computation rules do not imply judgmental uniqueness of recursion.
Proof of Theorem 4. With -natural transformations as 2-cells, is a 2-category in the arbitrary-map case, and with -natural isomorphisms it is a (2, 1)-category in the invertible case. The assertion of the theorem is that the coproduct defining a type classifier also has the corresponding 2-categorical universal property. For this, it suffices to construct cotensors by the walking (invertible) arrow, as we will see below. Write and for these cotensors. Their universal property identifies strict morphisms with -natural transformations of strict morphisms , and similarly for and -natural isomorphisms.
Contexts of are pairs of telescopes of the same length, equipped with isomorphisms between corresponding prefixes that commute with the term-classifier maps.
Morphisms are commuting squares between the isomorphisms of the full contexts. A type consists of a type over each endpoint together with an isomorphism of their term classifiers over the given context isomorphism, and a term consists of a compatible pair of terms. Context extension is defined by appending these data to the two telescopes. The type and term formers are defined at the endpoints, with the comparison isomorphisms supplied by their functoriality. For , the same construction uses maps in place of isomorphisms.
A map of closed types in defines a closed type in . This type and the composite given by the diagonal determine a strict morphism , hence a -natural transformation from to . Conversely, a map can be obtained by evaluation at the generic type . For invertible maps, use in place of .
Naturality of type classifiers can be internalized with an operator corresponding to the components of -natural transformations between type-substitution functors. Its introduction rule is given by
in case the type formers of the theory are functorial with respect to all maps, with additional hypotheses corresponding to the existence of a definitional inverse in the invertible case:
Here is the type variable in , and is the term variable in . In , is bound in and is bound in . Parenthesized arguments indicate substitution. The intended interpretations of terms in the big model are the components of T-natural transformations between type-substitution functors given by Theorem 4.
Evaluation at the generic type and uniqueness in Theorem 4 give identity and composition laws for type families. These laws are
for identity and
for composition. The operator is expected to commute with identity and composition in , corresponding to preservation of identities and composition of 2-cells in Theorem 4:
Naturality with respect to terms is expressed by the following rule:
As usual, the operator is required to respect -conversion of the bound variables and and to be congruent with respect to definitional equality in its arguments.
References
- [1]Marc Bezem, Thierry Coquand, Peter Dybjer, and Martín Escardó. On generalized algebraic theories and categories with families. Mathematical Structures in Computer Science, 31(9): 1006–1023, 2021. doi:10.1017/S0960129521000268.DOI
- [2]Martin E. Bidlingmaier. An interpretation of dependent type theory in a model category of locally cartesian closed categories. Mathematical Structures in Computer Science, 31(5):469–494, 2021. doi:10.1017/S0960129521000098.DOI
- [3]Rafaël Bocquet, Ambrus Kaposi, and Christian Sattler. For the metatheory of type theory, internal sconing is enough. In Marco Gaboardi and Femke van Raamsdonk, editors, 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023), volume 260 of Leibniz International Proceedings in Informatics, pages 18:1–18:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.FSCD.2023.18. Full version: arXiv:2302.05190v2.DOI
- [4]Cyril Cohen, Thierry Coquand, Simon Huber, and Anders Mörtberg. Cubical type theory: A constructive interpretation of the univalence axiom. In Tarmo Uustalu, editor, 21st International Conference on Types for Proofs and Programs (TYPES 2015), volume 69 of Leibniz International Proceedings in Informatics, pages 5:1–5:34. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.TYPES.2015.5.DOI
- [5]Erik Palmgren. On universes in type theory. In Giovanni Sambin and Jan M. Smith, editors, Twenty-Five Years of Constructive Type Theory, volume 36 of Oxford Logic Guides, pages 191–204. Oxford University Press, 1998. doi:10.1093/oso/9780198501275.003.0012. URL https://www2.math.uu.se/~palmgren/universe.pdf.DOI