Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
1 to 18 of 18
Eric gave a very cool talk today.
E. Finster, “Towards Higher Universal Algebra in Type Theory”
He says that he might have a definition of a cartesian polynomial monad in HoTT.
Special cases of this definition give:
all in HoTT!
This may be a solution to the infinite cohereance problem in HoTT.
Now Eric hasn’t actually written up any details however there is a work in progress formalisation in agda.
It would be good to go through the video, and the agda formalisation and see if we can play with the definitions here on the nlab.
I have created a page on the HoTT wiki: Eric Finster, Towards Higher Universal Algebra in Type Theory (homotopytypetheory)
My first comments would be that these trees are simply just abstract syntax trees, for example as in Harper?
Well, I think ASTs are generally restricted to be finitary, and to have a set (indeed, usually a finite set) of sorts and operations. Polynomial monads can have operations of infinite arity, and when defined in HoTT as in Eric’s approach the types of sorts and operations can have unbounded h-level. Moreover I think the treatment of variables may be somewhat different, haven’t thought about it carefully. However, in principle, yes, ASTs are a syntactic way of talking about free things of this sort.
I’m very excited about Eric’s definition; he shared a few of the details with me before his talk, so I’ve had a little longer to think about it, and I still find it the most believable proposal for solving the infinite coherence problem that I’ve ever heard. Time will tell whether it actually works.
From the talk it looks like Eric succeeded in formalizing his opetopic type theory within dependent type theory.
For what it’s worth, others are working on other approaches to opetopes: opetopy, written in Python.
Do you have a pointer to something that tries to be more like a message than the git-hub pages? (Being sent to git-hub always feels like somebody is pointing me to their root directory without further comment.)
@Urs In the doc folder there is a file called index.rst which has some documentation.
I don’t think it’s quite opetopic type theory (although maybe Eric can comment). The pictures look similar, and the slice construction on multicategories is also what was used by Baez-Dolan to formalize opetopes, but the “relations” that arise are all essentially “graphs of functions” and so all the higher structure here is actually algebraic.
Perhaps an -(pre)category in Eric’s new sense could be described as an opetopic space in which every horn has a contractible space of fillers?
Yes, opetopic type theory was an attempt to implement directly the theory of opetopic -categories. This proposal is certainly inspired by many of the same ideas, but is really just the “fragment”.
On the other hand, I think that starting from this fragment, we should fairly easily be able to import Baez and Dolan’s notion of n-coherent algebra, and hence have a definition of -category.
@Mike: Yes, this was actually the approach that I took first: an infinite sequence of what I called “polynomial relations” (serving as a notion of opetopic type) such that every horn had a contractible space of fillers. So I think your intuition is right on. There turn out to be some subtleties with this approach which are a bit annoying, though it is probably possible to give a reasonable definition along these lines. It occurred to me, however, that after finishing such a definition, one would be able to prove that the filling spaces were equivalent to identity types for a multiplication definable from the fact that the spaces of fillers were contractible.
So it seems much more natural (and it ends up avoiding the subtleties I mentioned) to just use the identity types directly.
Hi Eric, glad you could join the conversation. Yes, I agree that the way you’ve phrased the definition now is simpler and better for HoTT purposes. But the other description is also nice to have; in particular I am wondering whether it would be a helpful route to a semantic comparison with existing notions of -category. For instance, the opetope category is a direct category, so there is a Reedy model structure on , which one might hope to localize in order to make the fibrant objects be the ones for which every horn has a contractible space of fillers. Then one could try to build a Quillen equivalence relating this model category to some other model structure for -categories.
By the way, I missed this during the talk or I would have commented on it at the time, but now looking at the slides and formalization I see that you are actually using Agda’s primitive notion of “coinductive definition”, which is an extension of MLTT/Book-HoTT. However, it seems that most or all coinductive definitions of this sort can also be written in an equivalent (though perhaps slightly less convenient) form as an internal limit of a tower indexed by the natural numbers type. In your case I think the way this would go is to first define recursively an “-coherence structure” for to consist of a witness that is subdivision-invariant together with an -coherence structure on the slice (while a -coherence structure is trivial). Then prove by induction that every -coherence structure has an underlying -coherence structure on the same magma, and finally define an (-)coherence structure to consist of an -coherence structure for every together with equalities .
Yes, so the approach of trying to link this definition with some kind of “opetopic spaces” seems natural. I agree. Since I do not think I have seen this concept studied in the literature, I guess the theory would need to be developed from scratch. Not that I think it’s at all impossible, just that it will probably take a bit of work. Christian Sattler and I at one point had started to think about some comparisons between opetopic-sets and semi-simplicial sets. He had some nice ideas, so maybe it would be useful to revisit some of this.
With regard to coinduction: yes, I meant to mention this during my talk but I guess it slipped my mind. I agree that I don’t at all think it is fundamentally necessary, but just really convenient. Indeed, I was planning to introduce the notion of n-coherence structure anyway: one clearly wants a theorem along the lines of “if the space of operations is n-truncated then any (n+1)-coherence structure is -coherent.”
Certainly, however we slice it (no pun intended) there’s work to be done.
Another idea would be to try to somehow mimic the slice construction semantically. Can we say for instance that for any polynomial and relations there is some kind of equivalence of homotopy theories between something over and something over the slice ? This is very vague, but I have some vision of starting with a “classical” presentation of -categories (or operads or whatever) and slicing it over and over again to get a tower of equivalent homotopy theories, then taking the limit to get a presentation using something like your definition. If this can be made sense of, it might be easier than trying to deal with the rather-complicated opetope category all at once.
I’ve started writing a coq version of Eric’s library. I have it on a branch on my fork here. I have managed to define slicing, but I need to spend some more time understanding the Substritution.agda file. I started with annotating the universes, but it seems coq is okay doing that by itself so I removed them later.
Great! If you’re open to experimenting with alternatives, I would suggest trying out the style of polynomials where the sorts of parameters are assigned by a function rather than given by an index. That is, instead of
Param {i : I} : Op i -> I -> Type;
there would be something like
Param {i : I} : Op i -> Type;
SortOf {i : I} {f : Op i} : Param f -> I;
I suspect that this would make some things in the development simpler (though there are a couple that it would make more complicated), and it would be nice to have it written down to compare with Eric’s version.
@Mike I have tried your definition. I now have a file called Polynomial2.v, it seems to want less parameters which can help but I won’t see its true utility until I prove some things about my definitions (or even see if they are really correct yet). For this I will need the notions of substitution but I haven’t really understood how this works yet. There is a small corollary in Eric’s Polynomial.agda file called corolla-frm which I am trying to write in coq but I haven’t been able to power through it yet.
I have tried a third attempt. I am getting stuck at formalising flatten however. It will require some more brainpower. I think I agree with Mike that SortOf helps the formalisation however.
1 to 18 of 18