betaFeedback

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 U0∈U1∈⋯∈Uℓ∈⋯U_0 \in U_1 \in\cdots\in U_\ell\in\cdots and use universe polymorphism to quantify over its levels ℓ\ell. 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 U∞U_\infty, 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 CC is a closed type or term of the cwf CC, 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 CC is an ordinary cwf structure [1 Section 2] on CopC^{\mathrm{op}}, as in [2 Definition 14].1 Thus CC has a chosen initial empty context 0C0_C, sets Ty⁡C(Γ)\operatorname{Ty}_C(\Gamma) of types, and sets Tm⁡C(Γ,σ)\operatorname{Tm}_C(\Gamma,\sigma) of terms. We write substitution as function application: for f:Γ→Δf:\Gamma\to\Delta, the substituted type and term are f(σ)∈Ty⁡C(Δ)f(\sigma) \in\operatorname{Ty}_C(\Delta) and f(a)∈Tm⁡C(Δ,f(σ))f(a) \in\operatorname{Tm}_C(\Delta,f(\sigma)). Functoriality of substitution means that g(f(σ))=(gf)(σ)g(f(\sigma))=(gf)(\sigma) and id⁡Γ(σ)=σ\operatorname{id}_{\Gamma}(\sigma)=\sigma, 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 σ∈Ty⁡C(Γ)\sigma\in\operatorname{Ty}_C(\Gamma), a term classifier consists of a context Γ.σ\Gamma.\sigma, a morphism and a generic term

p:Γ⟶Γ.σ,v∈Tm⁡C(Γ.σ,p(σ)).p:\Gamma\longrightarrow\Gamma.\sigma,\qquad v \in\operatorname{Tm}_C(\Gamma.\sigma,p(\sigma)).

Its universal property is that, for f:Γ→Δf:\Gamma\to\Delta and a∈Tm⁡C(Δ,f(σ))a \in\operatorname{Tm}_C(\Delta,f(\sigma)), there is a unique morphism ⟨f,a⟩:Γ.σ→Δ\langle f,a\rangle:\Gamma.\sigma\to\Delta such that ⟨f,a⟩/p=f\langle f,a\rangle/p=f and ⟨f,a⟩(v)=a\langle f,a\rangle(v)=a.

Let T\mathbb{T} 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 CwfT\mathbf{Cwf}_{\mathbb{T}} 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 Γ\Gamma is a finite list of successive types, with evaluation Γ.T\Gamma.T and composite classifier map pT:Γ→Γ.Tp_T:\Gamma\to\Gamma.T. A cwf is contextual if each context has a unique telescope presentation over 0C0_C. Write CxlT\mathbf{Cxl}_{\mathbb{T}} 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 CC and context Γ\Gamma of CC, the contextual coslice Γ//C\Gamma// C is the contextual cwf whose contexts are telescopes over Γ\Gamma and whose morphisms T→ST \to S are maps h:Γ.T→Γ.Sh : \Gamma.T \to\Gamma.S satisfying hpT=pSh p_T = p_S. Types and terms at TT, together with their formers, are those of CC at Γ.T\Gamma.T. The empty telescope is initial, and a term classifier is obtained by appending the given type to the telescope.

For f:Γ→Δf : \Gamma\to\Delta, transport f∗:Γ//C→Δ//Cf_* : \Gamma// C \to\Delta// C is defined by iterating the pushout squares determined by term classifiers along a telescope. The comparison map at TT is denoted by fT:Γ.T→Δ.f∗(T)f_T : \Gamma.T \to\Delta.f_*(T). 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 fTf_T in CC. A strict morphism F:C→DF : C \to D induces a strict morphism FΓ:Γ//C→F(Γ)//DF_\Gamma: \Gamma// C \to F(\Gamma) // D. The assignment f↦f∗f \mapsto f_* is functorial [3 after Definition 22]:

(gf)∗=g∗f∗,(id⁡)∗=Id⁡.(gf)_* = g_*f_*, \qquad(\operatorname{id})_* = \operatorname{Id}.

Transport is compatible with strict morphisms:

Γ//C→f∗Δ//CFΓ↓↓FΔF(Γ)//D→(F(f))∗F(Δ)//D\begin{CD} \Gamma// C @>{f_*}>> \Delta// C \\ @V{F_\Gamma}VV @VV{F_\Delta}V \\ F(\Gamma) // D @>{(F(f))_*}>> F(\Delta) // D \end{CD}

Evaluation eC:0C//C→Ce_C : 0_C // C \to C is strict, and every strict morphism from a contextual model into CC factors uniquely through it. If CC is contextual, eCe_C is a strict isomorphism [3 Section 2.3 and Corollary 24]. The coslice of Γ//C\Gamma// C at TT is strictly isomorphic to Γ.T//C\Gamma.T // C by concatenation of telescopes [3 proof of Lemma 26].

For a contextual CC and a closed type σ\sigma, define

C.σ=(0C.σ)//C.C.\sigma= (0_C.\sigma) // C.

The map p:C→C.σp : C \to C.\sigma is given by transport along the term-classifier map 0C→0C.σ0_C \to0_C.\sigma, composed with eC−1e_C^{-1}. The generic term vv is a closed term of type p(σ)p(\sigma) in C.σC.\sigma. The following is the universal property proved in [3 Lemma 25], expressed for covariant cwfs.

Proposition 1. For every D∈CwfTD \in\mathbf{Cwf}_{\mathsf{T}} there is a natural bijection

CwfT(C.σ,D)≅∐F:C→DTm⁡D(0D,F(σ)),H↦(Hp,H(v)).(1)\mathbf{Cwf}_{\mathsf{T}}(C.\sigma,D) \cong\coprod_{F:C\to D} \operatorname{Tm}_{D}(0_D,F(\sigma)), \qquad H \mapsto(Hp,H(v)). \tag*{(1)}

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:

⊢Γ ctx⊢Γ,X type ctx⊢Γ ctxΓ,X type⊢X type\frac{\vdash\Gamma\ \mathrm{ctx}}{\vdash\Gamma,X\ \mathrm{type\ ctx}} \qquad \frac{\vdash\Gamma\ \mathrm{ctx}}{\Gamma,X\ \mathrm{type}\vdash X\ \mathrm{type}}
Γ⊢JΓ,X type⊢JΓ,X type,Δ(X)⊢J(X)Γ⊢σ typeΓ,Δ(σ)⊢J(σ)\frac{\Gamma\vdash\mathcal{J}}{\Gamma,X\ \mathrm{type}\vdash\mathcal{J}} \qquad \frac{\Gamma,X\ \mathrm{type},\Delta(X)\vdash\mathcal{J}(X)\qquad\Gamma\vdash\sigma\ \mathrm{type}}{\Gamma,\Delta(\sigma)\vdash\mathcal{J}(\sigma)}

Here J\mathcal{J} ranges over type and term judgments and their judgmental equalities. The expressions Δ(σ)\Delta(\sigma) and J(σ)\mathcal{J}(\sigma) denote replacement of XX by σ\sigma, 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 Γ\Gamma of a covariant cwf consists of a context Γ[X]\Gamma[X], a morphism pΓ:Γ→Γ[X]p_{\Gamma} : \Gamma\to\Gamma[X], and a type X∈Ty⁡(Γ[X])X \in\operatorname{Ty}(\Gamma[X]), with the following universal property: for every f:Γ→Δf : \Gamma\to\Delta and σ∈Ty⁡(Δ)\sigma\in\operatorname{Ty}(\Delta) there is a unique morphism ⟨f,σ⟩:Γ[X]→Δ\langle f, \sigma\rangle: \Gamma[X] \to\Delta such that

⟨f,σ⟩pΓ=f,⟨f,σ⟩(X)=σ.(2)\langle f,\sigma\rangle p_{\Gamma} = f,\qquad\langle f,\sigma\rangle(X) = \sigma. \tag*{(2)}

The following is our main result.

Theorem 3. The category CxlT\mathrm{Cxl}_{\mathbb{T}} has a covariant cwf structure with

Ty⁡CxlT(C)=Ty⁡C(0C),Tm⁡CxlT(C,σ)=Tm⁡C(0C,σ).\operatorname{Ty}_{\mathrm{Cxl}_{\mathbb{T}}}(C) = \operatorname{Ty}_{C}(0_C),\qquad\operatorname{Tm}_{\mathrm{Cxl}_{\mathbb{T}}}(C,\sigma) = \operatorname{Tm}_{C}(0_C,\sigma).

It supports the type and term formers of T\mathbb{T} and type classifiers at all contexts.

Proof. The empty context is the initial contextual model. For the term classifier at σ\sigma, take C.σC.\sigma with the structure map pp and generic term vv of Proposition 1.

By definition of the contextual coslice, we have the literal equalities

Ty⁡C.σ(0)=Ty⁡C(0C.σ),Tm⁡C.σ(0,τ)=Tm⁡C(0C.σ,τ).(3)\operatorname{Ty}_{C.\sigma}(0) = \operatorname{Ty}_{C}(0_{C.\sigma}),\qquad\operatorname{Tm}_{C.\sigma}(0,\tau) = \operatorname{Tm}_{C}(0_{C.\sigma},\tau). \tag*{(3)}

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 CC. The type and term formers can thus be defined using those of CC, 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 UU be the free contextual T\mathbb{T}-cwf on a single closed type. Such a free model and coproducts exist because contextual T\mathbb{T}-cwfs admit an essentially algebraic presentation [1 Section 5.7]. Put C[X]=C⨿UC[X] = C \amalg U, with pCp_C the coproduct inclusion and XX the image of the generating type of UU. By the coproduct universal property, this is a type classifier at CC.

Now consider isomorphic types σ≅τ\sigma\cong\tau in a context Γ\Gamma of the big model and the induced functors σˉ,τˉ:Γ[X]→Γ\bar{\sigma},\bar{\tau} : \Gamma[X] \to\Gamma, where σˉ=⟨Id⁡Γ,σ⟩\bar{\sigma} = \langle\operatorname{Id}_{\Gamma},\sigma\rangle and τˉ=⟨Id⁡Γ,τ⟩\bar{\tau} = \langle\operatorname{Id}_{\Gamma},\tau\rangle. Does the isomorphism σˉ(X)≅τˉ(X)\bar{\sigma}(X) \cong\bar{\tau}(X) extend to isomorphisms σˉ(κ)≅τˉ(κ)\bar{\sigma}(\kappa) \cong\bar{\tau}(\kappa) for every type Γ[X]⊢κ type\Gamma[X] \vdash\kappa\ \text{type}? If the type formers of T\mathbb{T} are well-behaved, the answer is yes, by the following theorem.

Theorem 4. Suppose the type and term formers of T\mathbb{T} are functorial with respect to invertible maps between types. Then for every strict F:C→DF : C \to D between contextual models and closed types σ,τ\sigma,\tau of DD, there is a natural bijection

Iso⁡F(⟨F,σ⟩,⟨F,τ⟩)≅Iso⁡(σ,τ).\operatorname{Iso}_{F}(\langle F,\sigma\rangle,\langle F,\tau\rangle) \cong\operatorname{Iso}(\sigma,\tau).

If the type and term formers are functorial with respect to arbitrary maps between types, there is also a natural bijection

Hom⁡F(⟨F,τ⟩,⟨F,σ⟩)≅Hom⁡(σ,τ).\operatorname{Hom}_{F}(\langle F,\tau\rangle,\langle F,\sigma\rangle) \cong\operatorname{Hom}(\sigma,\tau).

On the left, Iso⁡F\operatorname{Iso}_{F} denotes T\mathbb{T}-natural isomorphisms between the indicated functors whose restriction along pCp_C is the identity on FF. Here T\mathbb{T}-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, Iso⁡(σ,τ)\operatorname{Iso}(\sigma,\tau) denotes invertible maps between types in DD, identified with isomorphisms 0D.σ≅0D.τ0_D.\sigma\cong0_D.\tau of their term classifiers. Likewise, Hom⁡F\operatorname{Hom}_{F} denotes T\mathbb{T}-natural transformations restricting to the identity on FF, and Hom⁡(σ,τ)\operatorname{Hom}(\sigma,\tau) denotes context morphisms 0D.τ→0D.σ0_D.\tau\to0_D.\sigma, or equivalently open terms x:σ⊢s(x):τx : \sigma\vdash s(x) : \tau. 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 T\mathsf{T} 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 ap⁡\operatorname{ap} defined by identity elimination, even ap⁡id(p)≡p\operatorname{ap}_{\mathsf{id}}(p) \equiv p need not hold judgmentally for a variable pp. 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 T\mathsf{T}-natural transformations as 2-cells, CxlT\mathrm{Cxl}_{\mathsf{T}} is a 2-category in the arbitrary-map case, and with T\mathsf{T}-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 D→D^{\to} and D≅D^{\cong} for these cotensors. Their universal property identifies strict morphisms C→D→C \to D^{\to} with T\mathsf{T}-natural transformations of strict morphisms C→DC \to D, and similarly for D≅D^{\cong} and T\mathsf{T}-natural isomorphisms.

Contexts of D≅D^{\cong} are pairs of telescopes of the same length, equipped with isomorphisms between corresponding prefixes that commute with the term-classifier maps.

\begin{CD} 0_D @>{p}>> 0_D.\sigma_1 @>>> \cdots@>{p}>> 0_D.\sigma_1.\cdots.\sigma_n \\ @V{\Vert}VV @V{u_1\cong}VV @. @V{u_n\cong}VV \\ 0_D @>{p}>> 0_D.\tau_1 @>>> \cdots@>{p}>> 0_D.\tau_1.\cdots.\tau_n \end{CD}

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 D→D^{\to}, the same construction uses maps in place of isomorphisms.

A map u:σ→τu:\sigma\to\tau of closed types in DD defines a closed type in D→D^{\to}. This type and the composite C→FD→D→C \xrightarrow{F} D \to D^{\to} given by the diagonal determine a strict morphism C[X]→D→C[X] \to D^{\to}, hence a T\mathsf{T}-natural transformation from ⟨F,τ⟩\langle F,\tau\rangle to ⟨F,σ⟩\langle F,\sigma\rangle. Conversely, a map σ→τ\sigma\to\tau can be obtained by evaluation at the generic type XX. For invertible maps, use D≅D^{\cong} in place of D→D^{\to}. □\square

Naturality of type classifiers can be internalized with an operator ap⁡X,x\operatorname{ap}_{X,x} corresponding to the components of T\mathsf{T}-natural transformations between type-substitution functors. Its introduction rule is given by

Γ⊢σ typeΓ⊢τ typeΓ,X type⊢P(X) typeΓ,x:σ⊢s(x):τΓ,z:P(σ)⊢ap⁡X,x(P,s,z):P(τ)(4)\frac{\Gamma\vdash\sigma\ \text{type}\qquad\Gamma\vdash\tau\ \text{type}\qquad\Gamma, X\ \text{type} \vdash P(X)\ \text{type}\qquad\Gamma, x:\sigma\vdash s(x):\tau}{\Gamma, z:P(\sigma) \vdash\operatorname{ap}_{X,x}(P,s,z):P(\tau)} \tag*{(4)}

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:

Γ,y:τ⊢t(y):σΓ,x:σ⊢t(s(x))≡x:σΓ,y:τ⊢s(t(y))≡y:τ\Gamma, y:\tau\vdash t(y):\sigma\qquad\Gamma, x:\sigma\vdash t(s(x)) \equiv x:\sigma\qquad\Gamma, y:\tau\vdash s(t(y)) \equiv y:\tau

Here XX is the type variable in P(X)P(X), and xx is the term variable in s(x)s(x). In ap⁡X,x(P,s,z)\operatorname{ap}_{X,x}(P,s,z), XX is bound in PP and xx is bound in ss. Parenthesized arguments indicate substitution. The intended interpretations of terms ap⁡X,x(P,s,z)\operatorname{ap}_{X,x}(P,s,z) in the big model are the components of T-natural transformations ⟨Id⁡,τ⟩⇒⟨Id⁡,σ⟩:C[X]→C\langle\operatorname{Id},\tau\rangle\Rightarrow\langle\operatorname{Id},\sigma\rangle: \mathcal{C}[X] \to\mathcal{C} 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

Γ⊢σ typeΓ⊢τ typeΓ,X type⊢P(X)≡X typeΓ,x:σ⊢s(x):τΓ,z:σ⊢ap⁡X,x(P,s,z)≡s(z):τ\frac{\Gamma\vdash\sigma\ \text{type}\qquad\Gamma\vdash\tau\ \text{type}\qquad\Gamma,X\ \text{type} \vdash P(X) \equiv X\ \text{type}\qquad\Gamma,x:\sigma\vdash s(x):\tau}{\Gamma,z:\sigma\vdash\operatorname{ap}_{X,x}(P,s,z) \equiv s(z):\tau}

for identity and

Γ⊢σ typeΓ⊢τ typeΓ,X type⊢P(X) typeΓ,Y type⊢Q(Y) typeΓ,x:σ⊢s(x):τΓ,z:Q(P(σ))⊢ap⁡X,x(Q(P(X)),s,z)≡ap⁡Y,u(Q,ap⁡X,x(P,s,u),z):Q(P(τ))\frac{\Gamma\vdash\sigma\ \text{type}\qquad\Gamma\vdash\tau\ \text{type}\qquad\Gamma,X\ \text{type} \vdash P(X)\ \text{type}\qquad\Gamma,Y\ \text{type} \vdash Q(Y)\ \text{type}\qquad\Gamma,x:\sigma\vdash s(x):\tau}{\Gamma,z:Q(P(\sigma)) \vdash\operatorname{ap}_{X,x}(Q(P(X)),s,z) \equiv\operatorname{ap}_{Y,u}(Q,\operatorname{ap}_{X,x}(P,s,u),z):Q(P(\tau))}

for composition. The operator ap⁡X,x\operatorname{ap}_{X,x} is expected to commute with identity and composition in ss, corresponding to preservation of identities and composition of 2-cells in Theorem 4:

Γ,X type⊢P(X) typeΓ⊢σ typeΓ,x:σ⊢s(x)≡x:σΓ,z:P(σ)⊢ap⁡X,x(P,s,z)≡z:P(σ)\frac{\Gamma,X\ \text{type} \vdash P(X)\ \text{type}\qquad\Gamma\vdash\sigma\ \text{type}\qquad\Gamma,x:\sigma\vdash s(x)\equiv x:\sigma}{\Gamma,z:P(\sigma)\vdash\operatorname{ap}_{X,x}(P,s,z)\equiv z:P(\sigma)}
Γ⊢σ typeΓ⊢τ typeΓ⊢κ typeΓ,X type⊢P(X) typeΓ,x:σ⊢s(x):τΓ,y:τ⊢t(y):κΓ,z:P(σ)⊢ap⁡X,x(P,t(s(x)),z)≡ap⁡X,y(P,t,ap⁡X,x(P,s,z)):P(κ)\frac{\Gamma\vdash\sigma\ \text{type}\qquad\Gamma\vdash\tau\ \text{type}\qquad\Gamma\vdash\kappa\ \text{type}\qquad\Gamma,X\ \text{type}\vdash P(X)\ \text{type}\qquad\Gamma,x:\sigma\vdash s(x):\tau\qquad\Gamma,y:\tau\vdash t(y):\kappa}{\Gamma,z:P(\sigma)\vdash\operatorname{ap}_{X,x}(P,t(s(x)),z)\equiv\operatorname{ap}_{X,y}(P,t,\operatorname{ap}_{X,x}(P,s,z)):P(\kappa)}

Naturality with respect to terms is expressed by the following rule:

Γ⊢σ typeΓ⊢τ typeΓ,X type⊢P(X) typeΓ,X type⊢r(X):P(X)Γ,x:σ⊢s(x):τΓ⊢ap⁡X,x(P,s,r(σ))≡r(τ):P(τ)\frac{\Gamma\vdash\sigma\ \text{type}\qquad\Gamma\vdash\tau\ \text{type}\qquad\Gamma,X\ \text{type}\vdash P(X)\ \text{type}\qquad\Gamma,X\ \text{type}\vdash r(X):P(X)\qquad\Gamma,x:\sigma\vdash s(x):\tau}{\Gamma\vdash\operatorname{ap}_{X,x}(P,s,r(\sigma))\equiv r(\tau):P(\tau)}

As usual, the operator is required to respect α\alpha-conversion of the bound variables XX and xx and to be congruent with respect to definitional equality in its arguments.

References

  1. [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. [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. [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. [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. [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

Paper details

vlnc:W_fhrc7ugg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents