1 Introduction
Homotopy type theory [26] provides a new and promising approach to equality in type theory where types are thought of as abstract spaces and equality as paths in these spaces [5]. Iterated equality proofs then correspond to homotopies between paths. This intuition is motivated by homotopy theoretic models, in particular by the Kan simplicial set model [15] due to Voevodsky. This allows one to find new principles in type theory inspired by homotopy theory. Prime examples of this are Voevodsky’s univalence axiom [27], which generalizes the principle of propositional extensionality to dependent type theory, and the stratification of types by the complexity of their equality (i.e., by their homotopy level or “hlevel” [28]).
In the homotopical interpretation of type theory inductive types are represented as discrete spaces with only points in them. Higher inductive types are a natural generalization where types may also be generated by paths (potentially higher dimensional). This notion of types, combined with universes and the univalence axiom, is an important extension of dependent type theory, which allows for an elegant and original synthetic development of algebraic topology, using in a key way typetheoretic ideas (such as the encodedecode method [26]). Impressive examples of this development are, among others, the definition of the Hopf fibration, the Freudenthal suspension theorem and the BlakersMassey theorem [6, 13]. However, and somewhat surprisingly, despite several efforts (e.g., [19]), the consistency of such an extension, which would justify these impressive developments, has not yet been established. The simplicial set model [15] provides (in a classical framework) a model for the univalence axiom, but it only provides a model for some very particular higher inductive types (such as the spheres, and the propositional truncation via an impredicative encoding [28]), and, as explained in [19], it is not clear how to extend this model to a model of parametrized higher inductive types like the suspension or pushouts (expressed as operations on a given universe).
Contributions
The first contribution of the present paper is to provide such a semantics, starting in an essential way not from the simplicial set model, but from a cubical set model [8, 20]. This semantics is furthermore carried out in a constructive metatheory. Our second contribution is to extend cubical type theory with a syntax for higher inductive types, exemplified by: spheres, the torus, suspensions, truncations, and pushouts. These types illustrate many of the difficulties in giving a computational justification for a general class of higher inductive types, in particular: the spheres and torus have higher dimensional constructors, furthermore one version of the torus refers to “fibrancy” structure in its endpoints, the suspension has a parameter type, the truncations are recursive, and the pushouts have function applications in the endpoints of the path constructor. We show how to overcome all of these difficulties in a uniform way which suggests an approach to the problem of defining a schema for higher inductive types in cubical type theory.
Furthermore, all of the higher inductive types we consider have the following good properties justified by our semantics:

judgmental computation rules for all constructors,

strict stability under substitution, and

closure under universe levels (the higher inductive types live in the same universe as their parameters).
We have also implemented a variation of the system presented in this paper and performed multiple experiments with it.^{1}^{1}1See: https://github.com/mortberg/cubicaltt/tree/hcomptrans
Outline
The paper begins by describing the semantics, expressed in a presheaf topos with suitable structure, of the circle (Section 2.1), suspension (Section 2.2), and pushouts (Section 2.3). The next section starts with a short background on cubical type theory (Section 3.1) followed by the extension to the theory with: circle and spheres (Section 3.3.1), the torus (Section 3.3.2), suspensions (Section 3.3.3), propositional truncation (Section 3.3.4), and pushouts (Section 3.3.5). The paper ends with conclusions and discussions on future and related work (Section 4).
2 Semantics of higher inductive types
As shown in [20, 18, 2], the presentation of the semantics of cubical type theory can be both simplified and clarified by using the language of extensional type theory (with universes). This language can be given meaning in any presheaf topos, so long as we assume that the ambient set theory has a hierarchy of Grothendieck universes. In particular, we are going to show that the justification of higher inductive types can be done internally, using the existence of suitable initial algebras as the only extra assumption. We then justify the existence of these initial algebras for our presheaf topos externally. The key idea will be a decomposition of the notion of composition structure [20, 18] into a transport and a homogeneous composition operation.^{2}^{2}2As explained in [2] this decomposition was first introduced in an early version of [8], precisely to address the problem of the semantics of propositional truncation and this decomposition is also present in [4, 3, 7]. This decomposition can be described internally.
We will work here in the presheaf topos over the Lawvere theory of De Morgan algebras [8, 18] (but, following [20], our results are valid in a more general setting). The presentation we use in [8] of this category is the following: we fix a countable set of names/symbols and the objects of the category are finite sets of symbols. A map is then a settheoretic map from to the free De Morgan algebra on . The corresponding presheaf model has then a generic De Morgan algebra , taking to be . (To have such a structure on is not strictly necessary [20], but it simplifies the presentation.)
This type is used as an abstract representation of the unit interval, so that a path in a type is represented by an element of the exponential . The extra data needed to define a cubical set model is a notion of cofibration, which specifies the shape of filling problems that can be solved in a dependent type. We represent this by a type of cofibrant propositions (denoted by in [20]). In [8], this is represented by the face lattice (see Section 3.1), but other choices are possible. (Classically, this type
is a subtype of the subobject classifier of the presheaf topos, but, as stressed in
[18], we can avoid mentioning the impredicative type of propositions altogether, and work in a predicative metatheory.) We write for the type associated to the proposition . So is a subsingleton, and any element of is equal to a fixed element .A partial element of a type is given by an element in and a function . We say that a total element of extends such a partial element if we have , where denotes implication between propositions.
In this extensional type theory, we can think of a dependent type over a given type as a family of types indexed by elements of .
We now recall the notions of composition and filling structures [8, 20]. Let be a dependent type over a type .
Definition 1.
A composition structure on is an operation taking as inputs in , a proposition in , a partial element in , and an element in such that . This operation produces an element in such that .
The type of all such operations is written (see [20, Definition 4.3] for an explicit internal definition).
Definition 2.
A filling structure on is an operation taking the same input as above, but producing an element in such that extends , i.e., , and .
We write for the type of filling structures on .
This notion of filling structure is an internal form of the homotopy extension property, which was recognized very early (see, e.g., [11]) as a key for an abstract development of algebraic topology.
In the particular case where is the unit type, then is a “global” type, and becomes the type expressing that is a fibrant object. Such a fibrancy structure on consists of an operation taking as arguments in and a partial element of such that , and produces an element such that .
In general, if is a family of types over , to give a composition structure for each fiber, that is, an element in , is not enough to get a global composition structure, that is, an element in (see [20] for an explicit counterexample). An element in is called a homogeneous composition structure.
We now describe the notion of transport operation, which allows to define a composition structure from a homogeneous composition structure. This decomposition of the composition operation into a transport and homogeneous composition operation plays a crucial role for interpreting higher inductive types depending on parameters (like suspension, pushouts, or propositional truncation).
Definition 3.
A transport structure on is an operation taking as arguments a path in , a proposition in such that , and an element in . This operation produces an element in such that .
The condition expresses that the path is constant on .
Clearly we obtain a homogeneous composition structure from any composition structure. We also get:
Lemma 4.
If a family of types over has a composition structure , then it has a transport structure .
Proof.
We can take . ∎
Lemma 5.
If a family of types over has a homogeneous composition structure and a transport structure , then it has a composition structure .
Proof.
We can define as
where . ∎
We are now going to develop some universal algebra internally in the presheaf model. The operations will involve the interval object and the type of cofibrant propositions, and can be seen as a generalization of the usual notion of operations in universal algebra.
2.1 Semantics of the circle
The circle, denoted , is represented as a higher inductive type with a path in direction connecting a point to itself:
If (resp. ) has a fibrancy structure (resp. ), then a map is fibrancy preserving if it satisfies
An algebra structure on a type consists of a fibrancy structure together with a base point and a loop in connecting to itself (i.e., ). Given two algebras and a function is a map of algebras if it is fibrancy preserving and satisfies and .
We will show below using external reasoning:
Proposition 6.
There exists an initial algebra, denoted by .
So has a structure of an algebra and the fact that it is initial means that, for any algebra there exists a unique algebra map .
By definition, the type is fibrant since it has a fibrancy structure . Furthermore, we can prove that initiality implies the dependent elimination rule.^{3}^{3}3This is a direct generalization of the usual argument that a natural number object satisfies the dependent elimination rule.
Proposition 7.
satisfies the dependent elimination rule for the circle: given a family of types over with a composition structure, and in and in such that there exists a map such that and .
2.2 Semantics of the suspension operation
The suspension of a type has constructors and (two poles) and a path between them for any element of A. This enables us to give a direct definition of as . Compared to the circle, this higher inductive type presents the extra complexity of having parameters and the decomposition of the composition operation will be the key for providing its semantics.
Given a type , a algebra structure on a type consists of a fibrancy structure together with two points , and a family of paths in connecting to (i.e., and for all in ). Given two algebras and a function is a map of algebras if it is fibrancy preserving and satisfies , , and .
As for the circle we can show using external reasoning:
Proposition 8.
There exists an initial algebra, denoted by .
By definition, the type is fibrant since it has a fibrancy structure . Using this filling structure, we prove as above:
Proposition 9.
satisfies the dependent elimination rule for the suspension: given a family of type over with a composition structure, and in and in and in such that and there exists a map such that and and .
The operation is functorial in . Given a map we get a structure on by taking and hence a map .
Let now be a dependent family of types over a given type , so that is a type for any in . We define a new family of types over by taking . By construction, this new family always has a homogeneous composition structure (without any hypothesis on ).
Proposition 10.
If has a transport structure , then has a transport structure, and hence (since it has a homogeneous composition structure) also a composition structure by Lemma 5.
Proof.
Given in and such that is constant on (i.e., ), we have a map which is the identity on and hence the map is a transport map which is the identity on . ∎
This example motivates the decomposition of the composition operation into a transport and homogeneous composition operations. In a context, we could only build an initial algebra for the homogeneous composition operation (by doing it pointwise) and it does not seem possible to do it for the composition operation directly. The problem does not appear for a type like the circle which has no parameters, for which homogeneous and general compositions coincide. For the suspension however, we have to argue further that we also get a transport operation. (This problem seems connected to the problem of size blowup for parametrized higher inductive types due to fibrant replacement in the simplicial set model discussed in [19].)
The same argument applies to the propositional truncation of a type . We would then instead consider the following notion of algebra: a type with a fibrancy structure, a map and a map such that is a path connecting to .
2.3 Pushouts
Many examples of higher inductive types can be encoded as (homotopy) pushouts of spans of other types. In particular (homotopy) coequalizers, which together with coproducts (which are encoded using types), can be used to compute general colimits of diagrams of types. This has been used to encode many known higher inductive types, including recursive ones like propositional [9, 16] and higher truncations [22].
The semantics of pushouts involves the same problem with parameters as in the previous example, but the definition of the transport function is more complex and we will need to introduce some auxiliary operations definable from transport.
A span consists of two maps and . Given such a span, we define a algebra to be a type with a fibrancy structure and maps and and such that and . As above, there is a canonical notion of algebra maps, and (in suitable presheaf models) we have an initial algebra, which we write .
We can relativize this situation over a type . If are families of types over and (resp. ) is a family of maps (resp. ), we consider to be a span over , with . If the span is given over , we define in a pointwise way as for the suspensions, taking to be .
We want to prove that if have transport structures, then so does . In order to do that, we first show how to define further operations from a given transport structure.
Lemma 11.
Given a family of types over with a transport structure we can define a new operation such that is a path in constant on and connecting to for any in constant on and in . Furthermore given any in we can define an operation which is a path in connecting to , and which is constant on .
Proof.
We define
which connects to and is constant on , and
which connects to and is constant on . ∎
The relationship between these operations can be displayed as: so that can be though of as an operation which “squeezes” the path into the fiber over .
Corollary 12.
Given two families of types and over with transport structures and respectively, and a map over , there exists an operation which is a path in constant over and connecting and , given in constant over and in .
Proof.
We apply the operation and the operation from Lemma 11 to the path ∎
Proposition 13.
Given a family of spans over a type such that , , and have transport structures then the family also has a transport structure, and hence also a composition structure by Lemma 5.
Proof.
We use the previous corollary to provide a structure of algebra on , structure which coincides with the one of on . By initiality we get a map which is the identity on , and is the desired transport function. (For a more detailed explanation see the syntactic presentation in Section 3.3.5.) ∎
2.4 Existence of initial algebras
We now explain the proof of Proposition 6 asserting the existence of a suitable initial algebra. We cannot prove this in an abstract way, but we need to use the fact that we are working with presheaf models over a small base category , in our case the Lawvere theory of the theory of De Morgan algebras. We write for the objects of . We only describe the case of algebra here, but all other cases follow the same pattern. The interested reader may consult Appendix A for the proofs for the other higher inductive types. The argument we give can be seen as a constructive version of the small object argument [25], and it crucially uses the fact that both and have decidable equality. Classically we could use Garner’s small object argument [12] as is for instance done in [19].
We first define inductively a family of sets which is an “upper approximation” of the circle, together with maps , for . An element of is of the form:

, or

with in , or

with in and in and a family of elements in for such that and in .
In this way an element of can be seen as a wellfounded tree. Note that we do not yet require that the sides in match up with the base. In order to express this we first define in for by induction on :
where is the family for .
Note that we may not have in general for in and and . We then inductively define the subsets by taking the elements , , and such that , , for satisfying for and for and in and . This defines a cubical set , such that is a subset of for each .
As defined has a structure of an algebra. Let us sketch that is also the initial algebra in this presheaf model. Note that initiality stated internally is a statement quantifying over all possible types in a universe, which for simplicity we did not make explicit. Unfolding this internal quantification amounts to constructing (suitably unique) natural transformations where is a presheaf over the category of elements of equipped with a homogeneous composition structure and sections in and in connecting to itself; moreover, these natural transformations should be stable under substitutions . This works more generally for being a presheaf over any cubical set , not only representables: in for in and in is defined by induction on the height of the wellfounded tree simultaneously with verifying for . Note that the height of does not increase. Each case in the definition is guided by the uniqueness condition.
2.5 Universes
As shown externally in [8, 20] (and internally in [18]) we can define in the presheaf model a cumulative hierarchy of (univalent and fibrant) universes which classify families of types of a given size with a composition structure. Since the way we build initial algebras preserves the universe level, our definition, e.g., of the suspension can be seen as an operation .
Let us expand this point. Let be a cumulative sequence of Grothendieck universes (or constructive analog of them [1]) in the underlying set theory. If is a presheaf on and a valued presheaf on the category of elements of with a composition structure , the suspension operation builds a valued presheaf with composition structure such that if we have and . An element of is then a pair where is a valued presheaf on the category of elements of and a composition structure on , and can then be seen as a natural transformation .
Thus, we have presented a semantics of a large class of higher inductive types with univalent universes. (As shown in [26], the univalence axiom is essential for any non trivial use of the higherdimensional structure of higher inductive types.)
3 Higher inductive types in cubical type theory
In this section we discuss the extensions to cubical type theory by higher inductive types. We begin by recalling the basic notions of cubical type theory [8].
3.1 Background: cubical type theory
Cubical type theory extends a dependent type theory with a universe closed under  and types with types, composition operations and types.
The types internalize the idea from homotopy type theory that equalities correspond to paths. We write for the type of paths in with endpoints and . These types behave like function types and have both abstraction (written for with abstracted) and application (written using juxtaposition). The path abstraction binds “dimension variables” ranging over an abstract interval specified by the grammar:
The set is a De Morgan algebra with the operation as De Morgan involution. A type in a context with dimension variables should be thought of as an dimensional cube and the substitutions and give the faces of this cube. A substitution renames the dimension variable in into and as there are no injectivity constraints on these renaming substitutions one can perform substitutions which give a “diagonal” of a cube (i.e., if is a square depending on , then is a diagonal). The and operations are called connections and provide convenient ways of building higher dimensional cubes from lower dimensional ones. For instance, if is a line depending on , then is the interior of the square:
The face lattice is a distributive lattice generated by formal symbols and with the relation . The elements of the face lattice can be described by the grammar:
There is a canonical lattice map sending to and to . We write for the image of in and we write for .
The judgment says that is a face formula involving only the dimension variables declared in . Given a formula we can restrict a context and obtain a new context written (assuming that only depends on the dimension variables in ). We call terms and types in such a restricted context partial. These restricted contexts are used for specifying the boundary of higher dimensional cubes, for example, if is a line depending on , the partial type is the two endpoints of . If , we write to denote the two judgments: Γ⊢u : A Γ, φ⊢u = v : A
Using this we can express the typing rule for the composition
operations:
Γ, i : I⊢A
Γ⊢φ: F
Γ, φ, i : I⊢u : A
Γ⊢u_0 : A(i/0)[ φ↦u (i/0) ]
Γ⊢comp^i A [ φ↦u ] u_0 :
A(i/1)[ φ↦u(i/1) ]
This operation takes a line type , a formula , a partial line
term and a term of type (note that may
occur freely in and ). Furthermore we require that . The result is a term in
such that on . The computation rules for the
composition operations are given as judgmental equalities defined by
cases on the type .
The intuition is that specifies the sides of an open box while specifies the bottom of the box and the fact that the sides have to be connected to the bottom is expressed by the equation relating and . The result of the composition operation is then the lid of this open box. For example, given paths , , and as in: the composition is the dashed line at the top of the square.^{4}^{4}4Note that we are using a notation for the "system" . Formally this is given by the formula and a partial element with endpoints and . Here is a line in while and are lines in and , respectively. The resulting composition is then a line in .
The composition operations allows us to define transport from a line
type:
Γ, i : I⊢A
Γ⊢u_0 : A(i/0)
Γ⊢transport^i A u_0 = comp^i A [] u_0 : A(i/1)
Combined with “contractibility of singletons” (which is directly provable using a connection) we get the induction principle for types, which means that they behave like MartinLöf’s identity types (modulo the computation rule for the induction principle which only holds up to a ).
The types allow us to prove both the univalence axiom and that the universe has a composition operation, however as they do not play an important role in this paper we omit them from this introduction to cubical type theory.
3.2 A common pattern for higher inductive types
All of the examples of higher inductive types that we consider in this paper follow a common pattern. In this section we sketch this pattern which can be seen as a first step towards formulating a syntactic schema for higher inductive types in cubical type theory, however the precise formulation of this schema and its semantic counterpart is left as future work.
Each higher inductive type is specified by a telescope^{5}^{5}5A telescope (written as ) over a context is a (possibly empty) list of object variable declarations such that is a wellformed context, so neither contains context restrictions nor dimension variables . of parameters (over an ambient context ) and a list of constructors . Each in is specified by the data:
Here the telescope specifies the types of the arguments to , and in the case of recursive higher inductive types, as in, e.g., propositional truncation, might itself appear in . The length of the list of names specifies the dimension of the cube introduces: we say that is a point, path, or square constructor according to whether the length of is or , respectively. The data specifies the endpoints of the constructor , with an element of the face lattice whose free variables are among , and is a partial element
mentioning only previous constructors in the list and possibly ’s (see below).
For each instance of the telescope we say that
is a type and we will have an introduction rule for a
constructor specified as above
→v: →A(→u)
→r: I c →v →r: D(→u)
and a judgmental equality in case we additionally have (all in an
ambient context). Note that this judgmental equality for
requires us to make sure that whenever we define a function that its semantics preserve this equality, so
that
In particular, this requirement has to be taken care of in the typing rules for the eliminator for . The general formulation of this is left as future work as it would require us to extend cubical type theory with something similar to the "extension types" of [21].
Recall from Section 2 that we
decomposed the composition structure for higher inductive types into a
homogeneous composition structure and a transport structure. The
homogeneous composition structure was introduced as constructors and
the same is reflected in the syntax by adding a rule
Γ⊢→u: →P
Γ⊢φ: F
Γ, i : I, φ⊢v : D(→u)
Γ⊢v_0 : D(→u) [ φ↦v (i/0) ]
Γ⊢hcomp^i_D(→u) [ φ↦v] v_0 : D(→u) [φ↦v (i/1)]
where the key point is that may be free in , but not in
, as opposed to the composition operations where may be
free in both and . In the examples we will not repeat
these homogeneous composition constructors for every higher inductive
type we consider and they are always assumed to be included as part of
the definition of the higher inductive type under consideration.
We could do the same for traditional inductive types like the natural numbers and have a constructor instead of explaining composition by recursion. We can prove that this “weaker” form of natural numbers type is equivalent, and hence equal (by univalence) to the regular one.
To reflect the transport structure in the syntax we specify a
operation for higher inductive types given
by the rule:
Γ⊢φ: F
Γ, i : I, φ⊢A = A (i/0)
Γ⊢u_0 : A (i/0)
Γ⊢trans^i A φ u_0 : A (i/1) [φ↦u_0]
Note that since also
(and hence this
equation also holds in context ).
Similar to how the transport structure is explained in the semantics by recursion on the argument we will add a judgmental equality for each of the possible shapes of : one for each constructor and one for the constructor:
(Note that we can assume that as we can always rename one of them as they are both bound.) As the case is the same for all examples we omit it from the definition of for the higher inductive types considered in Section 3.3.
We can define a derived “” operation analogous to
in the proof of Lemma 11:
Γ⊢φ: F
Γ, i : I,φ⊢A = A (i/0)
Γ, i : I⊢a : A Γ, i : I⊢squeeze^i A φ a := trans^j A(i/i ∨j) (φ∨(i=1)) a : A (i/1)
This operation satisfies
and the induced path is constantly on .
Assuming that we have defined for a higher inductive type
we can define the composition operation:
Γ⊢φ: F
Γ, i : I,φ⊢u : A
Γ⊢u_0 : A (i/0) [φ↦u (i/0) ] Γ⊢comp^i A [φ↦u] u_0 :=
hcomp^i_A (i/1) [ φ↦squeeze^i A 0_F u]
(trans^i A 0_F u_0) : A (i/1)
This satisfies the required judgmental computation rule for
because of the computation rules for and . This
means that in order to define the composition operation for a higher
inductive type we only need to define the operation when
applied to constructors.
Note, that we can always define a operation for any type
that already has a composition operation by:
Γ⊢φ: F
Γ, i : I,φ⊢A = A (i/0)
Γ⊢u_0 : A (i/0) Γ⊢ctrans^i A φ u_0 := comp^i A [ φ↦u_0 ] u_0 : A (i/1) [φ↦u_0]
In line with Lemma 11 a corresponding “filling” operation
which connects the input of to its output can also be
derived:
Γ⊢φ: F
Γ, i : I, φ⊢A = A (i/0)
Γ⊢u_0 : A (i/0)
Γ,i : I⊢transFill^i A φ u_0 := trans^j A (i/i ∧j) (φ∨(i=0)) u_0: A
Note that entails
This operation satisfies
and the induced path is constantly on . We write for the corresponding operation defined using .
3.3 Examples of higher inductive types
In this section we describe how to extend cubical type theory with the circle and spheres, torus, suspensions, propositional truncation, and pushouts. As with all the other type formers we have to explain their formation, introduction, elimination, and computation rules, as well as how composition computes. All of these examples follow the common pattern presented in the previous section.
3.3.1 The circle and spheres
The extension of cubical type theory with the circle and spheres was sketched in [8, Section 9.2] and we elaborate on this here.
Formation
In order to extend the theory with the circle we first add it as a type by: ⊢S^1 S^1 : U
Introduction
The circle is generated by a point and a path constructor: base:S^1 r : I loop r : S^1 with the judgmental equalities so that connects the point to itself.
Elimination
Given a dependent type , a term
and a path we can define by cases:
f base= b
f (loop r) = l r
and for the constructor:
where w.l.o.g. is fresh and:
As the equation for the eliminator applied to an is analogous for all the other higher inductive considered here we will omit it in the sequel.
Using this we can directly define the eliminator:
x : S^1 ⊢P(x)
b : P(base)
l : Path^i P(loop i) b b
u : S^1
S^1elim_x.P b l u : P(u)
where denotes a dependent path type
(see [8, Section 9.2]). The judgmental
computation rules then follow from the definition above. Note that as we have
dependent types (which behave like heterogeneous equalities)
the case of can be expressed directly by an equation
without “apd” and does not involve any as
opposed to [26, Section 6.4].
Composition
As has no parameters we let . This means that the composition computes directly to the constructor .
The higher dimensional spheres, , can directly be defined by generalizing the definition
Comments
There are no comments yet.