Homotopy Type Theory

Impredicative Encodings of Inductive Types in HoTT

I recently completed my master’s thesis under the supervision of Steve Awodey and Jonas Frey. A copy can be found here.

Known impredicative encodings of various inductive types in System F, such as the type

of natural numbers do not satisfy the relevant -computation rules. The aim of this work is to refine the System F encodings by moving to a system of HoTT with an impredicative universe, so that the relevant -rules are satisfied (along with all the other rules). As a result, the so-determined types have their expected universal properties. The main result is the construction of a type of natural numbers which is the initial algebra for the expected endofunctor .

For the inductive types treated in the thesis, we do not use the full power of HoTT; we need only postulate -types, identity types, “large” -types over an impredicative universe and function extensionality. Having large -types over an impredicative universe means that given a type and a type family , we may form the dependent function type

Note that this type is in even if is not.

We obtain a translation of System F types into type theory by replacing second order quantification by dependent products over (or alternatively over the subtype of given by some h-level).

For brevity, we will focus on the construction of the natural numbers (though in the thesis, the coproduct of sets and the unit type is first treated with special cases of this method). We consider categories of algebras for endofunctors:

where the type of objects of is given by

(the type of sets (in )) and morphisms are simply functions between sets.

We can write down the type of -algebras:

and homomorphisms between algebras and :

which together form the category .

We seek the initial object in . Denote this by and moreover let be the forgetful functor to and be the covariant Yoneda embedding. We reason as follows:

using the fact that the diagonal functor is left adjoint to the limit functor for the last step. With this, we have a proposal for the definition of the underlying set of the initial -algebra as the limit of the forgetful functor.  Using the fact that is defined as a limit, we obtain an algebra structure . As creates limits, is guaranteed to be initial in .

But we want to define in type theory. We do this using products and equalizers as is well known from category theory. Explicitly, we take the equalizer of the following two maps between products:

given by:

The equalizer is, of course:

which inhabits . Impredicativity is crucial for this: it guarantees that the product over lands in .

This method can be used to construct an initial algebra, and therefore a fixed-point, for any endofunctor !  We won’t pursue this remarkable fact here, but only consider the case at hand, where the functor is .  Then the equalizer becomes our definition of the type of natural numbers (so let us rename to for the remainder). Observe that this encoding can be seen as a subtype of (a translation of) the System F encoding given at the start.  Indeed, the indexing object of is equivalent to , by

With this, we can define a successor function and zero element, for instance:

(the successor function takes a little more work). We can also define a recursor , given any and . In other words, the introduction rules hold, and we can eliminate into other sets. Further, the -rules hold definitionally – as expected, since they hold for the System F encodings.

Finally we come to the desired result, the -rule for :

Theorem. Let  and . Moreover, let such that:

for any . Then

Note that the -rule holds propositionally. By Awodey, Gambino, and Sojakova we therefore also have, equivalently, the induction principle for , aka the dependent elimination rule. As a corollary, we can prove the universal property that any -algebra homomorphism is propositionally equal to the appropriate recursor (as a -algebra homomorphism). Again we emphasise the need for impredicativity: in the proof of , we have to be able to plug into quantifiers over .

A semantic rendering of the above is that we have built a type that always determines a natural numbers object—whereas the System F encoding need not always do so (see Rummelhoff). In an appendix, we discuss a realizability semantics for the system we work in. Building more exotic types (that need not be sets) becomes more complicated; we leave this to future work.