Semi-Simplicial Types, Part II: The Main Results
Posted by Mike Shulman
(Jointly written by Astra Kolomatskaia and Mike Shulman)
This is part two of a three part series of expository posts on our paper Displayed Type Theory and Semi-Simplicial Types. In this part, we cover the main results of the paper.
The Geometric Intuition
The central motivating definition of our paper is the following:
A semi-simplicial type consists of a type together with, for every , a displayed semi-simplicial type over .
The purpose of the 100+ pages is to formulate a type theory in which we can make sense of this as a kind of “coinductive definition”. The key is to figure out what “displayed semi-simplicial type over ” should mean. Intuitively, it should be an “indexed” reformulation of a morphism of semi-simplicial types , but how do we do that?
The idea behind our new type theory, Displayed Type Theory (dTT), is that if is any notion of mathematical object (such as a group, category, or semi-simplicial type), then there should exist a notion of displayed elements of living over the elements of . Thus, for example, if is a category, then there should be a type of categories displayed over , or alternatively dependent categories over . The particular case of displayed categories was introduced by Ahrens and Lumsdaine in an eponymous 2019 paper, and the idea has since been generalized to bicategories by Ahrens, Frumin, Maggesi, Veltri, and van der Weide; dTT posits that such displayed structures exist for any kind of mathematical object, with a definition that can be derived algorithmically from the definition of the object.
We will return to this below; but first, as suggested above, we explain how such a notion enables a coinductive definition of semi-simplicial types. Indeed, we say that a semi-simplicial type consists of the following: First, defines a type , called the -simplices of . Second, each -simplex defines a semi-simplicial type displayed over , called the slice of over .
We can phrase this in Agda
-esque syntax for dTT as follows:
codata SST : Type where Z : SST → Type S : (X : SST) → Z X → SSTᵈ X
To see why this definition is correct, we have to understand what, in general, a semi-simplicial type displayed over consists of. The first part of this answer is that defines a type of -simplices of displayed over -simplices of , i.e. a family . Then, every displayed -simplex over a -simplex should define , a doubly displayed semi-simplicial type, for whatever this means.
Now, instead of working out the definition of a doubly dependent semi-simplicial type, let’s circle back and think geometrically. Semi-simplicial types should have families of -simplex types. If , then we write that
is the type of -simplices in . Similarly, if is semi-simplicial type displayed over , then for , we write
for the type of -simplices of displayed over the -simplex of . Putting this together, if we have two -simplices of , then we may form
which is the type of -simplices in joining to .
It therefore stands to reason that should have a type of dependent -simplices living over the -simplices of . Thus if , then given dependent endpoints and , we should get a type . The formula for this happens to take the following form:
which mirrors the formula for .
Then, putting all of this together again, if we have a -simplex , then we take . For , we have that . We thus get that:
In general, this pattern continues in higher dimensions and the process described lets us extract -simplex types.
We can visualise what’s going on in two different ways. The first visualisation shows how the -simplices of the slice of over live dependently over simplices of .
For example, if is a -simplex of the slice of over displayed over the zero simplex of , then is a -simplex of joining to . Similarly, suppose and are -simplices of the slice of over displayed over and , respectively, and is a -simplex of joining to . Then if is a -simplex of the slice of over displayed over and joining to , then is a -simplex of with the specified boundary.
Geometrically, we are using the fact that the -simplex is the cone of the -simplex. Thus, with the above definition, assuming we know inductively that every semi-simplicial type has a type of -simplices, then for every 0-simplex , the displayed semi-simplicial type has a type of “displayed -simplices” over this. Such a displayed -simplex depends in (the cone vertex) as well as on an -simplex of (the base face, opposite the cone vertex) and thus can be viewed geometrically as an -simplex.
The second visualisation explains our formulas in terms of iterated slicing.
Note that, to form each successive slice, you have to provide simplex data points. The true dependent -simplices of a slice may then be viewed as matching objects.
The Homotopical Problem of Constructing a Semi-Simplicial Classifier
Now, to motivate the construction of “display”, let us return to classical homotopy theory. Suppose that we are working in , some setting for homotopy theory. This could be a model category or a fibration category, which we usually think of as representing a Grothendick -topos. In our paper (section 4.1) we refer to the objects of as contexts, denoted , the fibrations over a context as types, denoted , and sections of a type as terms, denoted by .
We assume that this setting has an object classifier. This means that in any context , there is , as well as . This has the property that any “small” fibration gives rise to a code in the universe , such that the pullback of the fibration along that section exactly yields the type , that is:
We then consider the problem of constructing a classifier for semi-simplicial diagrams. Specifically, we are interested in Reedy fibrant semi-simplicial diagrams, which are the homotopical counterpart of the indexed formulation in syntax. Thus, such a classifier would consist of a generic fibration in the empty context , along with a simplicial diagram tower of the form:
such that for any “small” simplicial diagram data over a context , this data arises uniquely as the appropriate series of pullbacks constructed from some term .
Note that, stated in this way, this is an infinitary or non-elementary universal property: it refers to infinite diagrams indexed by the external set of natural numbers (as opposed to any internal natural-numbers object that may exist in ). The problem of defining semi-simplicial types can roughly be thought of as one of giving a finitary universal property for such an object, so that it could be characterized and even constructed in a finitary syntactic type theory.
A Finitary Universal Property for the Classifier
We have not, strictly speaking, solved this problem as originally stated. Indeed, we suspect that the classifier does not, on its own, have a finitary universal characterisation. However, we discovered that there is an enhancement of it that does have a finitary universal property, if we change the setting in which we were working to the augmented semi-simplicial diagram model . Then, there is a universally characterised diagram in , of which the desired classifier in was the discrete part, denoted .
If we playfully refer to the problem of categorically constructing a classifier for semi-simplicial objects as answering the question “what is a triangle?”. then we discovered that is naturally characterised in the model , which is the setting for homotopy theory in which “everything is an augmented triangle.” In a sense, then, is the “augmented triangle of triangles.”
Intuitively, by working in the setting of infinitely coherent diagrams, the desired augmented diagram of diagrams can be assembled in a way that accounts for all the coherences. This at first may appear as a convenient but inessential strengthening of the inductive hypothesis. However, passing to the world of augmented diagrams seems to play a much more essential role than this because the finitary universal characterisation of uses properties of augmented diagrams in an essential way.
Specifically, the world of augmented diagrams is the place where we can make sense of the general notion of a “displayed element” of a type. This happens through the existence of an operation known as décalage, which is a kind of backwards shift operation. It’s very classical in homotopy theory — you can read much more about it starting on the nLab — but the basic idea is just that if you take a (fibred) semi-simplicial diagram and throw away the bottom object and the last face operators in each dimension, and relabel, you get another semi-simplicial diagram. In other words, on objects we have . The face operators that we threw away now assemble into a map of semi-simplicial diagrams .
If we convert this fibred formulation to an indexed one, this means that any object comes with an object over itself, such that . In practice, we keep the fibred formulation for contexts, but use the indexed version for types, and call it display. This gives the following rule:
The fact that display alters the context is the source of much technical difficulty, which we deal with in the paper using a modal type theory. We have two modes, the simplicial one corresponding to , and the discrete one corresponding to itself. Then we have three basic modalities. The first, denoted , picks out the -simplices of an augmented semi-simplicial diagram, mapping the simplicial mode to the discrete mode. The second, denoted , builds a constant augmented semi-simplicial diagram, mapping the discrete mode to the simplicial mode. And the third, denoted , takes the limit of a semi-simplicial diagram, mapping the simplicial mode to the discrete mode. Then décalage and display act only on types at the simplicial mode, but we can avoid décalaging the context if it comes from the discrete mode, giving a rule something like:
To be more precise, here refers to a “modal context lock”, and we actually allow part of the context to be simplicial and get décalaged. However, for the present we can ignore these modal issues and just work in the empty context , for which we have . Ignoring this and other subtleties involving telescopes, we can now state more formally the universal property of . Suppose that is a type in the empty context (at the simplicial mode), a.k.a. a “closed type”. We define an endofunctor on closed types (at the simplicial mode) by:
This endofunctor comes with an evident copointing by way of projection. Our proposed characterization of is that it is a terminal (copointed) coalgebra of the copointed endofunctor . Thus, it is the universal object equipped with a map
whose first component is the identity. What remains, therefore, is two components and , exactly as proposed above. Once again, this corresponds to the following Agda
-esque dTT code:
codata SST : Type where Z : SST → Type S : (X : SST) → Z X → SSTᵈ X
Parametricity
The model structure on is well known in the literature as the Reedy model structure. However, in the dTT paper, we present an explicit construction in the case of the augmented semi-simplex category. This presentation defines the relevant concepts mutually with décalage and display, and allows for definitionally strict commutation laws for display without the use of coherence theorems. These computation laws, for example, say that:
These laws provide the promised algorithmic computation of displayed structures in terms of ordinary ones. If X denotes a kind of mathematical structure, the first law above says that for any type appearing in an X, a displayed X has a type dependent on that type, and the second says that similarly any function appearing in an X is tracked in a displayed X by a function lying above it. Thus, for instance, if is a category with object set and homs , a displayed category has a dependent family of objects and dependent hom-types lying over those of , with composition and identity operations lying over those of and so on, exactly as in the original definition of displayed category.
However, these are also the classical observational computation laws for “unary parametricity”! These say that in a unary relational model, computability witnesses for a type are predicates on the type, and computability witnesses for a function are constructions that transform computability witnesses of an input into computability witnesses of the corresponding output . This basic structure is what underlies, for example, the normalisation proof for STLC in Pierce’s Types and Programming Languages.
Consider the type of polymorphic identity functions. We have that:
Hence a computability witness of a polymorphic identity function is a proof that preserves arbitrary predicates. In displayed type theory, then, we have (with some abuse of notation for the modalities that we are ignoring):
id-thm : (f : △□ ((A : Type) → A → A)) (A : Type) (a : A) → f A a ≡ a id-thm (△ (□ f)) A a = fᵈ A (λ x → x ≡ a) a refl
Thus any closed term of polymorphic identity function type is indeed an identity function at all types.
Parametricity means that, for example, the simplicial mode of dTT is incompatible with the existence of features such as universal decidable equality. Indeed, suppose that we had decidable equality on the universe. Then one could construct a bad polymorphic identity function which is everywhere the identity function, except at the type , at which it is the constant at function. Such a construction would violate the theorem above. Indeed, the spirit of most parametricity violating results is either classical or non-constructive. This is because, morally, if you do everything constructively, then any definition that you write down should be natural and respect all relations.
Using the Universal Property
Note that our definition/construction of yields a type at the simplicial mode, i.e. an object of . But the classical homotopy theorist is interested in our original homotopy theory . Thus, recalling that picks out the -simplices of an augmented semi-simplicial diagram, from the classical perspective the question of interest in working with semi-simplicial types is:
Given a context in the model being studied (i.e. the discrete mode), construct a term representing the desired semi-simplicial type.
But in order to solve this problem, we have to work in the simplicial mode, where the universal property is stated. This means that we have to find a context at the simplicial mode such that , i.e. to extend to a diagram of which it is the discrete part. Doing so is always possible as we may consider , which extends coskeletally. However, the issue is that any categorical universal properties that held of in the discrete mode will not necessarily continue to hold of as a diagram; in particularly, any properties of that are expressed in the syntax of type theory vanish. It is thus necessary to extend to a diagram in a bespoke way such that the relevant properties that discretely hold of continue to simplicially hold of .
Fortunately, every construction of constructive intensional type theory (e.g. -types, universes, and inductive types) make sense of diagrams. Thus, metatheoretically, one can construct of a purely syntactic entity by structural recursion on the definition of via replacing all discrete syntax with its simplicial counterpart. However, from the perspective of the homotopy theorist, the model category can have many semantic entities not captured by the syntax of type theory. For example, the semantics of dTT are compatible with the model for the discrete mode having universal decidable equality. If were to use such a parametricity violating construction in an essential way in its definition, then the obstacle would be that could not be lifted to in a way that reflected all of the same categorical properties.
Parametricity thus serves as a kind of filter regarding what categorical universal properties of can be invoked when applying the universal property of semi-simplicial types. The categorical meaning of parametricity is then the question of what universal constructions in an arbitrary model category exist in the diagram model .
Simplices, cubes, and symmetry
It is a curious fact that to give a universal property to the type of semi-simplicial types, we find ourselves needing to work in the model whose objects are augmented semi-simplicial types in — curious that the two are closely related and yet not identical. It’s possible there is something deeper going on here, but one explanation is that this is a coincidence arising from another coincidence: the fact that the augmented semi-simplex category coincides with the unary semi-cube category.
Normally when we think of a cubical set we think of cubes as powers of an interval object that has two endpoints. Thus, an -dimensional cube has faces of dimension , arising by choosing one of the dimensions and then an endpoint in that dimension. However, essentially the same formal construction works for an “interval” having endpoints for any natural number . We can visualize the case , for instance, as consisting of powers of an interval with its midpoint also distinguished along with its endpoints, so that a 2-cube looks like a window subdivided into four panes.
In the case , it turns out that the faces of a “unary” -cube have exactly the same combinatorial structure as those of an augmented -simplex. We can even see this geometrically: the unary cubes can be thought of as powers of a half-open interval or ray with only one endpoint, and there is a face-respecting embedding of the -simplex in the first -orthant as . Thus, we can equivalently think of dTT as having semantics in the model of unary semi-cubical diagrams.
This point of view is also suggested by the connection to parametricity, where one can consider also -ary parametricity for any . Indeed, binary parametricity seems to be more useful than unary parametricity: many of the “free theorems” arising from parametricity require the binary version. (Nullary parametricity is also possible, and is closely related to nominal sets.) Ordinary internal -ary parametricity has semantics in -ary cubical diagrams (having degeneracies as well as faces), and one might expect that there is an analogous sort of “-ary dTT” with semantics in -ary semi-cubical diagrams.
For those having experience with cubical type theories, we should emphasize that unlike the cubes often used there, these cubes do not have diagonals or connections. This is essential to get the correct behavior of -types, for instance. (However, cubes without diagonals and connections were used in the first BCH cubical model of homotopy type theory, and also in the more recent Higher Observational Type Theory.)
Another question this perspective emphasizes is the presence or absence of symmetries. Here the simplest sort of symmetry in dTT would be an isomorphism . Our current theory does not admit such operations, in contrast to internal parametricity and cubical type theories where they have been found essential. The modal guards on the display operation allow us to omit them. This makes certain things easier, such as our explicit construction of the diagram model , but may ultimately be a limitation: in particular, it seems that we cannot give a useful universal property to without symmetries.
Conclusion and Vistas
In conclusion, therefore, what we achieve is to specify a new type theory, displayed type theory (dTT), which contains a unary parametricity operator that behaves “observationally” (computes on type-formers), and which is “modally guarded” so that it can only be applied to types in the empty context or more generally in a modal context. Inside this type theory, we specify a general notion of “displayed coinductive type”, of which our proposed definition of is an instance.
We then construct, from any model of type theory having limits of countable towers of fibrations, a model of dTT, and show that in this model displayed coinductive types are modeled by terminal coalgebras of copointed endofunctors, which can be constructed as countable inverse limits. Moreover, we identify the corresponding tower for as consisting of the classifiers for -truncated semi-simplicial types, so that the limit object is, indeed, a classifier of semi-simplicial types.
Intriguingly, this leaves open the question of models of dTT and without countable limits. We conjecture that there are models of dTT, perhaps obtained from realizability, in which an object satisfying our universal property for exists, but is not an external classifier of semi-simplicial types. Instead, we expect it should be a classifier of “internal” or “uniform” semi-simplicial types, which is exactly what one would hope to be able to talk about in a realizability model. If this were true, then our universal property for semi-simplicial types would be more general than the classical external infinitary one, with possible implications for the notion of “elementary -topos”.
Re: Semi-Simplicial Types, Part II: The Main Results
Nice reading! Can I ask to elaborate on the connection between nullary parametricity and nominal sets?