[Agda] Universes à la Tarski and induction-recursion

Dan Licata drl at cs.cmu.edu
Wed Mar 16 04:25:11 CET 2011


> > Is this necessary? In my view we have both: open universes (e.g. Set_i) and
> > closed universes (like the U,T given by Dan using induction-recursion).
> >
> > ...
> >
> > Actually, Voevodsky's univalence axiom (weakly equivlalence of sets is
> > weakly equivalent to set equality) is related: It only works for an open
> > universe, since it implies that we can exchange isomorphic sets. In this
> > sense this axiom is a rather strong extensionality principle.
> 
> Yes. I've been thinking about this some recently (who hasn't). And the 
> difference crystalized a bit yesterday. Induction-recursion (and every other 
> inductive formation, and probably others) lets us define new _sets_ (in the 
> univalent sense). The inhabitants of a set are unique up to equality.
> 
> There is no way, however, to define (ex-nihilo) a new geinuine _category_ in 
> Agda. The built-in Set (n) is all there is. Sets can be promoted to 
> categories, by taking an existing set as the collection of objects and 
> equipping that with arrows. But the rigorous category theorist will tell you 
> that in general we shouldn't think about the _set_ of objects of a category, 
> and as a consequence, we should only be able to talk about the objects of a 
> category up to isomorphism. We can choose to work that way for any set, but it 
> is only enforced (to any degree) for Set (and I suppose types that contain one 
> or more Sets).
> 
> So perhaps in a language of the future, it will be possible to define both new 
> sets and new (n-)categories, in which case closed universes would be defined 
> as sets, and open universes would be categories (or something along those 
> lines).

I agree that you want this ability.  It's kind of a shame that, while
Martin-Loef type theory is compatible with groupoids and
higher-dimensional categories, there's no way to actually introduce
them!  I think what you would want is a "higher-dimensional quotient
type", where you define a type by writing down a category internally to
the type theory, and then can hook this into the type-generic operations
for identity types, like subst and J.  

I speculated on this a little in Chapter 8 of my thesis:
http://www.cs.cmu.edu/~drl/pubs/thesis/thesis.pdf
though things are little different there, because in my context I was
thinking about types as general categories, not groupoids.  

-Dan


More information about the Agda mailing list