Dendroidal Sets and Infinity-Operads

February 5, 2009

Dendroidal Sets and Infinity-Operads

Posted by Urs Schreiber

$MathML-enabled post (click for more details).$

This morning I was in Hamburg chatting with David Ben-Zvi about his work (see his recent guest post for a pedagogical introduction) then I jumped on the train and arrived just in time in Göttingen at the workshop Higher Structures II (see this post for the announcement) to hear Ieke Moerdijk’s talk on $\infty$ -Operads and dendroidal sets.

Now after conference dinner it’s already late, but I thought I’d try to produce at least parts of my notes of Ieke Moerdijk’s talk. I am doing this with an eye towards our discussion about hyperstructures over at the $n$ Lab (which started at this blog entry) which is clearly somehow related (inconclusive as it is at this stage) to the idea underlying dendroidal sets.

From one point of view the simple underlying idea is that

- simplicial sets and hence in particular for instance Kan complexes and $(\infty,1)$ -categories are presheaves on the simplex category $\Delta$ , which can be regarded as the full subcategory of $Cat$ on those posets which are “linear” (totally ordered) $\cdots \leftarrow \leftarrow \leftarrow \cdots$

- a dendroidal set is a presheaf on a subcategory of $Cat$ (not a full one, though) on slightly more general posets, namely those which are “tree shaped” $\array{ &&& \swarrow & \leftarrow & \cdots \\ \cdots &\leftarrow &\leftarrow &\leftarrow& \cdots \\ & \nwarrow \\ && \leftarrow & \cdots }$

- while there are some situations which are naturally modeled by presheaves on more general posets, for instance those of the form $\left( \array{ && \top \\ & \nearrow && \nwarrow \\ a &&&& b } \right)^{\times n}$ as considered in Marco Grandis’s work on Cospans in Algebraic Topology for describing extended cobordisms

- or even entirely general ones, possibly, as considered tentatively at $n$ Lab. hyperstructure.

One way to think about this is that every (finite) poset can be regarded as defining one of the geometric shapes for higher structures. For instance the posets $G'\downarrow [n]$ arising as over-categories of the globe category, which locally look like the poset that Tom Leinster recently mentioned here, are the poset incarnation of the $n$ -globe: $c_i$ and $d_i$ represent its two sub- $i$ -globes and the morphisms indicate which subglobe sits inside which higher sub-globe (the poset depicted above is actually that of the boundary of the $(n+1)$ -globe, with the top $(n+1)$ -cell missing). These globe-posets play a crucial role in Michael Batanin’s work (see his comment here).

As Ronnie Brown kindly points out at hyperstructure, the idea of defining higher structures without commiting oneself to a single or to one of the standard shapes (globes, simplices, cubes) is an old one (I am being told that this goes back to Grothendieck’s dérivateurs, but am lacking currently further information on that) which has for instance been studied by D. Jones in A general theory of polyhedral sets and their corresponding T-complexes.

All this may or may not be directly related to the main point of dendroidal sets and $\infty$ -operads, but I felt like mentioning it in any case. More concretely, dendroidal sets are supposed to be precisely the notion that completes the analogy

$\array{ category & (\infty,1)-category & simplicial set & weak Kan complex \\ operad & \infty-operad & dendroidal set & Kan dendroidal set } \,.$

The following is a reproduction of some of the notes that I took in Ieke Moerdijk’s talk today. A closely related survey talk I had recently reproduced here.

$MathML-enabled post (click for more details).$

[some aspects of notes I had taken]

(The following is a description of parts of joint work of Ieke Moerdijk with Ittay Weiss.)

Noticing that every category is a colored operad with only a unary operation, we have a canonical inclusion of the collection of categories into that of operads

$Categories \stackrel{j}{\hookrightarrow} ColoredOperads (= Multicategories)$

A the same time categories are related via the simplicial nerve to simplicial sets. Dendroidal sets are supposed to be the notion that sensibly completes the square

$\array{ Categories &\stackrel{Nerve}{\to}& SimplicialSets \\ \downarrow^j && \downarrow \\ ColoredOperads &\stackrel{}{\to}& DendroidalSets } \,.$

This is realized in terms of the dendroid category $\Omega$ whose objects are planar rooted trees. Every planar rooted tree $T$ defines freely a colored operad $\Omega(T)$ whose colors are the edges of the tree and whose operations are the vertices of the tree, subject to the obvious relations. A morphism $T \to S$ in $\Omega$ is precisely a morphism $\Omega(T) \to \Omega(S)$ of operads.

A dendroidal set is a presheaf on $\Omega$ :

$DendroidalSets := [\Omega^{op}, Sets] \,.$

The full subcategory of the dendroid category $\Omega$ on linear trees is precisely the simplex category $\Delta$

$\Delta \stackrel{i}{\hookrightarrow} \Omega$

and the moprhism $SimplicialSets \to DendroidalSets$ is defined to be the left Kan extension along this inclusion $i^{op}$ :

$Lan(i^{op}) : SimplicialSets \to DendroidalSets \,.$

Given any (colored) operad $P$ (= multicategory) its dendroidal nerve is, as usual, the dendroidal set $N(P)$ whose value on the dendroid $T$ is the Hom-set $N(P) := Operads(\Omega(-), P) : T \mapsto Operads(\Omega(T), P) \,,$

i.e. the collection of all ways to label $T$ by colors and operations of $T$ .

Recalling that every symmetric monoidal category $E$ induces an operad colored by the objects of $E$ with $n$ -ary operations colored by $(c_1, \cdots, c_n)$ incoming colors and $c_0$ outgoing being the Hom-set $E(c_1 \otimes \cdots \otimes c_n, c_0)$ from the tensor product of all these objects, we observe that for $P$ any operad the Hom-set $DendroidalSets(N(P), N(E))$ is the set of $P$ -algebras of $E$ (you can take this as the definition, if you like).

If we are in a homotopy theoretic context such as that of Top we have derived versions of all of this. For instance for $P$ any topological operad let $W(\Omega(T))$ be the Boardman-Vogt resolution of the operad $\Omega(T)$ , then we have the homotopy coherent nerve of $P$ defined by

$D(P) ::= TopologicalColoredOperads(W(\Omega(-)), P) \,.$

Everything goes through analogously as before, for instance $P$ -algebras up to homotopy in a symmetric monoidal category $E$ are the elements of

$TopologicalColoredOperads( D(P), D(E) ) \,.$

Theorem. There exists a model category structure on $DendroidalSets$ such that the homotopy coherent nerve $D : TopologicalColoredOperads \to DendroidalSets$ is a (right) Quillen equivalence.

(This is joint work by Ieke Moerdijk and Denis-Charles Cisinski, involving a contribution by Clemens Berger.)

We want to characterize the image of this functor: those dendroidal sets in which one can “compose up to homotopy”. The idea for that is a more or less straightforward generalization of the Kan condition:

- a face of a dendroid $T$ is a subdendroid $f \hookrightarrow T$ with exactly one vertex less that $T$ obtained from $T$ by contracting precisely one edge. The inner dendroid horn $\Lambda^e(T)$ is the union of dendroidal sets given by all the faces of the dendroid $T$ except the one coming from contracting the inner edge $e$ .

Definition. A dendroidal set $X$ is an weak dendroidal Kan complex if for any dendroid $T$ and any one of its inner edges $e$ and any morphism $\Lambda^e(T) \to X$ there exists the lift $\phi$ in

$\array{ \Lambda^e(T) &\to& X \\ \downarrow & \nearrow_{\exists \phi} \\ \Omega(T) } \,.$

It is clear from this that if $X$ is just a simplicial set in that it is in the image of the inclusion $Lan i : SimplicialSets \to DendroidalSets$ then $X$ is a weak dendroidal Kan complex precisely if it is a weak Kan complex, i.e. an $(\infty,1)$ -category.

So much for today. tomorrow we’ll here in the next part about The homotopy theory of infinity-categories and infinity-operads.

Posted at February 5, 2009 11:18 PM UTC

TrackBack URL for this Entry: https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1908

18 Comments & 1 Trackback

Re: Dendroidal Sets and Infinity-Operads

Ieke Moerdijk gave a very similar talk in January at the fourth “Categories, Logic and Foundations of Physics” workshop at Imperial. A video can be found here.

Posted by: Andreas Döring on February 6, 2009 11:00 AM | Permalink | Reply to this

Re: Dendroidal Sets and Infinity-Operads

$MathML-enabled post (click for more details).$

Over lunch Clemens Berger was so nice to give me a one-sentence description of the idea of dérivateurs (hope I am getting this right now):

the idea is apparently to look for a given triangulated model category $C$ at all the model categories of diagrams in $C$ , i.e. on all the functor categories $[D,C]$ for $D$ a small category.

Apparently the infamouse octahedral axiom in triangulated categories comes from doing this just for the diagram of the form $a \to b \to c$ and hence the idea of dérivateurs is to regard the octahedral axiom as just the simplest in an infinite collection of similar things. Somehow, roughly.

Posted by: Urs Schreiber on February 6, 2009 1:24 PM | Permalink | Reply to this

Re: Dendroidal Sets and Infinity-Operads

Hi Urs,

Sorry if this is offtopic, but I couldn’t do this otherwise.
I am not sure if my emails are reaching you. Did you get any of them?

Posted by: Daniel de França MTd2 on February 6, 2009 2:03 PM | Permalink | Reply to this

Re: Dendroidal Sets and Infinity-Operads

$MathML-enabled post (click for more details).$

We had a very nice talk by Clemens Berger which I am hoping to report on in more detail tonight maybe. One of its central aspects related to the above thing about shapes for higher structures modeled by general posets is the concept of geometric Reedy categories.

These are small categories that roughly behave like the simplex category for the purpose of defining nerves of $n$ -categories. Clemens Berger obtains examples for these from forming iterated wreath products of $\Delta$ with itself or with another geometric Reedy category. The result tends to behave like subcategories of posets.

For instance the $n$ -fold wreath product of $\Delta$ with itsel gives the category whose objects are layered trees of height $n$ .

There is a “Pontryagin-dual” poset for each such tree, which is the poset describing a cell which is a pasting globular diagram. This is closely related to Michael Batanin’s work.

A discussion of these geometric Reedy categories and the layered trees categories is in sectoin 3.13 of Clemens Berger’s article Iterated wreath product of the simplex category and iterated loop sapces.

Posted by: Urs Schreiber on February 6, 2009 2:09 PM | Permalink | Reply to this

Read the post Moerdijk on Infinity-Operads
Weblog: The n-Category Café
Excerpt: Ieke Moerdijk on (infinity,1)-operads.
Tracked: February 6, 2009 4:53 PM

Re: Dendroidal Sets and Infinity-Operads

Urs wrote:

- a dendroidal set is a presheaf on a subcategory of Cat (not a full one, though) on slightly more general posets, namely those which are “tree shaped”

I think Moerdijk realized this Dendroid category NOT as a subcategory of CAT. But rather as a subcategory of Multicategories (also called coloured operads). That was very important in his talk. Then it is a full subcategorie. The multicategory associated to a tree T is this Ω(T) you described. So Dendroidal sets are a combinatorial approach to coloured operads.

Posted by: Thomas Nikolaus on February 6, 2009 9:23 PM | Permalink | Reply to this

Re: Dendroidal Sets and Infinity-Operads

$MathML-enabled post (click for more details).$

Hi Thomas,

I think Moerdijk realized this Dendroid category NOT as a subcategory of CAT. But rather as a subcategory of Multicategories (also called coloured operads).

Yes, he certainly introduced it as a full subcategory of multicategories.

Here I am being prejudiced towards posets. So I wanted to think of this equivalently as a non-full subcategory of that of posets. I think it is. But it is not so important and possibly not the good poin of view.

I wanted to say more, but my trainwill move now and my connection will break down…

Posted by: Urs Schreiber on February 6, 2009 10:00 PM | Permalink | Reply to this

A few remarks on symmetries

It is perhaps worth pointing out that in a sense all the subtleties of the
theory comes from the presence of symmetries: the fact that the trees are
not planar trees and that therefore the category of trees contains the
category of finite sets and bijections as a full subcategory. In other
words, we are working inside the category of coloured operads ( = symmetric
multicategories), not just multicategories.

This becomes clear by contrasting with the planar (non-symmetric) version
of the theory which is much simpler. It involves planar trees and
multicategories, and it leads to a notion of quasi-multicategories. Of
course ‘planar dendroidal sets’ are not as interesting as the true
dendroidal sets, since one of the goals is to get to E_n stuff… However,
the planar case is enough to reproduce the Joyal model structure on sSet,
as every linear tree has an unique planar structure! There is a pair of
adjoint functors, forgetting the symmetry and symmetrisation, and it seems
that many of the constructions and arguments of Moerdijk and Weiss are
formulated in terms of this adjunction, so the planar case serves also an
important purpose in the theory.

In the symmetric case, Moerdijk and Weiss needed the Boardman-Vogt tensor
product, and a quite complicated model structure in which the cofibrations
are certain normal monos, not all monos. This means you cannot apply
Cisinski theory directly, as his basic assumption is that the cofibrations
are exactly the monos. So the Moerdijk-Weiss model structure is
constructed ‘by hand’ (at least originally), using comparison with the
non-symmetric case:

~~In the non-symmetric case the cartesian product is good enough~~, and all
monos are normal, and the model structure is a Cisinski model structure.
(It seems that Cisinski has now refined his big machine to account also
for cases with mild symmetries. I look forward to learn about that.)

A very closely related remark, perhaps just another viewpoint on the same
issue, is that the category of (non-planar) trees is not a Reedy category:
the symmetries mess up the requirement of having a strict factorisation
system. In contrast, the category of planar trees is a Reedy category. In
their recent preprint, Berger and Moerdijk generalise the notion of Reedy
category to allow for certain mild symmetries, covering the case of trees:
the factorisations no longer need to be unique, but the symmetries in the
middle must act faithfully from the right upon the left-hand class of maps.
They show how the nice consequences of the Reedy condition, i.e.
construction of model structures on the presheaf category, generalise to
this case.

Some remarks in another direction:

Planar trees can be seen as M-trees, i.e. trees whose nodes are decorated
with the operations of the free-monoid monad M, corresponding to the fact
that classical multicategories can be seen as the M-multicategories in the
sense of Leinster. For any polynomial endofunctor P there is a notion of
P-tree, where P is interpreted as specifying the branching profile of the
trees; the set of P-trees is a initial algebra for P. If P is finitary,
the P-trees will be finite trees. (For not-necesarily finitary P, the
resulting trees are the wellfounded trees in the sense of Martin-Löf type
theory. The correspondence between initial algebras for polynomial
functors and wellfounded trees is due to Moerdijk and Palmgren (in the
general setting of Heyting pretoposes or something like that).) For any
endofunctor P, P-trees have no symmetries. In particular, the trees used
in dendroidal sets are not P-trees for any P, they are abstract trees! To
realise those abstract trees as a least fixpoint, you need to step up one
categorical dimension from sets to groupoids: you can realise the groupoid
of abstract trees as a sort of pseudo least fixpoint for the
free-symmetric-monoidal-category monad (or perhaps rather some simple
variation of it, like adding the identity monad to it). One may speculate
that all the subtleties of the model structure on dendroidal sets may be
understood one day in terms of some categorified model category theory, who
knows – I certainly don’t.

There is a nice class of coloured operads ‘in between’ the non-symmetric
and the symmetric, namely those whose underlying collection is the
symmetrisation of a non-symmetric one, i.e. the action of the symmetric
groups is free. These are called flat; they are precisely the polynomial
monads. Trees seen as coloured operads are always flat (as every tree
admits a planar structure), so the category of trees can be constructed
entirely within polynomial functors. This has the advantage that
everything is completely combinatorial, and makes very explicit that the
category of trees is a Kleisli category like in Weber’s theory of local
right adjoints (this was first observed by Weber), stressing its formal
similarities with Delta and Joyal’s Theta. The generic/free factorisation
system highlighted by this construction is fundamental to the role trees
play as templates for composing algebraic operations: the generic maps
(which are dual to contracting inner edges) parametrise the composition
laws, while the free part (which is made up of tree inclusions) serves to
do the book-keeping of only combining operations when their types (colours)
match. (The generalised Segal condition, characterising coloured operads
or polynomial monads among presheaves on the category of trees, is
formulated solely in terms of the free maps.) In the uncoloured situation
the free part is not needed, as we see in the seminal work of Ginzburg and
Kapranov: the category of trees they use as foundation for (uncoloured)
operad theory is dual to the category of generic maps in Moerdijk and
Weiss’ category of trees.

(The category of trees ought to be called Psi: Delta is called Delta
because this letter looks like a simplex, in fact the smallest one
illustrating the characteristing features, including composition. Joyal’s
Theta, the cell category, is called Theta because that letter looks like
the vertical composition of two 2-cells, again the smallest illustrative
example. The category of trees should be called Psi since this letter
looks like a tree, and in fact one of the smallest ones having the
characteristic features. (Upsilon is not a serious alternative, I think.)
I don’t know why Moerdijk and Weiss chose Omega. Moerdijk told me they had
previously considered using Psi.)

Cheers,
Joachim.

Posted by: Joachim Kock on February 8, 2009 7:29 PM | Permalink | Reply to this

Re: A few remarks on symmetries

I wrote:

> In the non-symmetric case the cartesian product is good enough

I don’t know what I was thinking about when I wrote that.
I take it back, it doesn’t make sense. Sorry for the polution.

Joachim.

Posted by: Joachim Kock on February 9, 2009 9:50 AM | Permalink | Reply to this

Re: A few remarks on symmetries

$MathML-enabled post (click for more details).$

Dear Joachim,

thanks for all the information! Very useful.

And thanks for the corrections. Yes, I should have said that we are talking about symmetric multicategories. I’ll fix this in the entry above. Right now I need to run again to catch a flight…

Posted by: Urs Schreiber on February 9, 2009 10:36 AM | Permalink | Reply to this

Re: A few remarks on symmetries

> thanks for the corrections. Yes, I should have said
> that we are talking about symmetric multicategories.
> ll fix this in the entry above.

The comments were not meant as a correction. It is clear
from the context throughout that there are symmetries.
The remark was just that symmetries account for many
subtleties.

By the way, how does correction work on such a blog?
Do you have an overstrike feature? If there is such
a feature, I would like to have overstriked the false
statement of mine that I just corrected. It is both
embarrassing and could mislead others.

Cheers,
Joachim.

Posted by: Joachim Kock on February 9, 2009 11:24 AM | Permalink | Reply to this

Re: A few remarks on symmetries

How much do you want removed? From ‘In the non-symmetric case…’ to ?

Posted by: David Corfield on February 9, 2009 12:34 PM | Permalink | Reply to this

Re: A few remarks on symmetries

> How much do you want removed?

I am against actually removing text.
I think the page should also function
as a history, and we don’t want to be
revisionists!

Perhaps I chose the wrong English word,
but by overstrike I meant having a
horizontal line through the text.
The HTML tag is <STRIKE>.

> From ‘In the non-symmetric case…’ to ?

Like this:

<STRIKE>In the non-symmetric case the cartesian product is good
enough</STRIKE>

Unfortunately it doesn’t seem to work,
at least not if I enter it.

But never mind. I have already made too
much fuss about this.

Cheers,
Joachim

Posted by: Joachim Kock on February 9, 2009 1:34 PM | Permalink | Reply to this

Re: A few remarks on symmetries

Hi Joachim, after some Googling it seems the <del>…</del> tag works, like so: ~~don’t use the del tag on the n-category café!~~

Posted by: Bruce Bartlett on February 10, 2009 5:58 AM | Permalink | Reply to this

Re: A few remarks on symmetries

the set of P-trees is an initial algebra for P,

is there any interest in the final coalgebra for such P? Do people look at non-wellfounded trees?

Posted by: David Corfield on February 11, 2009 4:56 PM | Permalink | Reply to this

Re: A few remarks on symmetries

> If the set of P-trees is an initial algebra for P,
> is there any interest in the final coalgebra for such P?
> Do people look at non-wellfounded trees?

Yes. In type theory and computer science these are sometimes
called M-types (just because an M looks dual to W, I suppose),
but I don’t know how well-established that terminology is.

If P is polynomial it always has a terminal coalgebra.

An example of an M-type is ‘stream’, i.e. infinite sequences,
which of course is an important data type. For example it is
the input data type of a web server.

Now since you cannot actually write down an infinite
sequence, what you would do in practice is to write a
program f and define the sequence as {f(n) | n\in N}. This
example illustrates some sort of principle, namely that
algebras are data types and coalgebras are programs. If
anyone can explain me this principle a little bit better,
or explain what is wrong with it, I would be very
interested.

Since this conversation takes place in a café, I cannot
avoid giving this example: consider a coffee machine. It
has a set of states X, an input alphabet I, and an output
alphabet O, and is given altogether by a map I x X -> O x X.
By adjunction, this is equivalent to X -> (O x X)^I.
In other words, it is a coalgebra for the polynomial functor
(O x -)^I. Now we know there exists a terminal coalgebra
for this functor: it is The Universal Coffee Machine! This
machine U can simulate any other coffee machine with the same
interface, in the sense that for any other such machine A,
there is a map from the set of states of A to the set of
states of U, such that for any input the two machines give
the same output and furthermore the new state of A maps to
the new state of U.

Cheers,
Joachim.

Posted by: Joachim Kock on February 11, 2009 5:57 PM | Permalink | Reply to this

Re: A few remarks on symmetries

$MathML-enabled post (click for more details).$

I don’t know why Moerdijk and Weiss chose Omega.

I suppose because $\Omega \simeq \omega \sim w$ , which stands for ‘well-founded’ (as in ‘W-type’).

And then ‘M-type’ for a co-W-type? Yikes!

Posted by: Toby Bartels on February 12, 2009 12:22 AM | Permalink | Reply to this

Re: A few remarks on symmetries

cf. why JHCW named it the J-homomorphism and then came K-theory

Posted by: jim stasheff on February 12, 2009 2:06 PM | Permalink | Reply to this

Dendroidal sets and opetopic sets

$MathML-enabled post (click for more details).$

While writing notes on dendroidal sets I began to feel that a discussion of their relation to opetopic sets would be desireable.

To my shame, I never learned much about opetopic sets and will have to sit down and read the literature.

But maybe while I am doing this, somebody here has already a quick answer for me: what story is there to be told about their relation?

Posted by: Urs Schreiber on November 17, 2009 10:53 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

February 5, 2009