## April 20, 2014

### Finite Products Theories

#### Posted by John Baez

Here’s a classic theorem about finite products theories, also known as algebraic theories or Lawvere theories. You can find it in Toposes, Triples and Theories, but it must go way back to Lawvere’s thesis. In my work with Nina Otter on phylogenetic trees, we need a slight generalization of it… and if true, this generalization must already be known. So I really just want a suitable reference!

Theorem. Suppose $C$ is a category with finite products that is single-sorted: every object is a finite product of copies of a single object $x \in C$. Let $Mod(C)$ be the category of models of $C$: that is, product-preserving functors

$\phi : C \to Set$

and natural transformations between these. Let

$U : Mod(C) \to Set$

be the functor sending any model to its underlying set:

$U(\phi) = \phi(x)$

Then $U$ has a left adjoint

$F : Set \to Mod(C)$

and $Mod(C)$ is equivalent to the category of algebras of the monad

$U F : Set \to Set$

As a result, any model $\phi$ can be written as a coequalizer

$F U F U(\phi) \stackrel{\longrightarrow}{\longrightarrow} F U(\phi) \longrightarrow \phi$

where the arrows are built from the counit of the adjunction

$\epsilon : F U \to 1_{Mod(C)}$

in the obvious ways: $F U (\epsilon_{F U (\phi)})$, $\epsilon_{F U F U(\phi)}$ and $\epsilon_\phi$.

The generalization we need is quite mild, I hope. First, we need to consider multi-typed theories. Second, we need to consider models in $Top$ rather than $Set$. So, this is what we want:

Conjecture. Suppose $C$ is a category with finite products that is $\Lambda$-sorted: every object is a finite product of copies of certain objects $x_\lambda$, where $\lambda$ ranges over some index set $\Lambda$. Let $Mod(C)$ be the category of topological models of $C$: that is, product-preserving functors

$\phi : C \to Top$

and natural transformations between these. Let

$U : Mod(C) \to Top^\Lambda$

be the functor sending any model to its underlying spaces:

$U(\phi) = (\phi(x_\lambda))_{\lambda \in \Lambda}$

Then $U$ has a left adjoint

$F : Top^\Lambda \to Mod(C)$

and $Mod(C)$ is equivalent to the category of algebras of the monad

$U F : Top^\Lambda \to Top^\Lambda$

As a result, any model $\phi$ can be written as a coequalizer

$F U F U(\phi) \stackrel{\longrightarrow}{\longrightarrow} F U(\phi) \longrightarrow \phi$

where the arrows are built from the counit of the adjunction in the obvious ways.

1) There shouldn’t be anything terribly special about $Top$ here: any sufficiently nice category should work… but all I need is $Top$. What counts as ‘sufficiently nice’? If we need to replace $Top$ ‘convenient category of topological spaces’, to make it cartesian closed, that’s fine with me—just let me know!

2) I’m sure this conjecture, if true, follows from some super-duper-generalization. I don’t mind hearing about such generalizations, and I suspect some of you will be unable to resist mentioning them… so okay, go ahead, impress me…

… but remember: all I need is this puny little result!

In fact, all I really need is a puny special case of this puny result. If it works, it will be a small, cute application of algebraic theories to biology.

Posted at April 20, 2014 4:58 PM UTC

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

### Re: Finite Products Theories

I am certainly not an expert on this stuff, and I look forward to hearing what the experts have to say.

After having a bit of a non-expert nose about, I suspect it’s possible to extract what you need from Chapter 6 of Kelly’s Basic Concepts of Enriched Category Theory.

Obviously that goes much more general than you need, and specialising it to your situation would be a non-trivial amount of work. I hope someone will find a more suitable reference.

Posted by: Robin Houston on April 20, 2014 7:55 PM | Permalink | Reply to this

### Re: Finite Products Theories

This type of thing can be, at least in my own experience, surprisingly hard to track down “in the literature”. But intuitively I feel pretty sure that you basically want a cocomplete category over which finite products distribute as a working hypothesis. If so, then $Top$ won’t do since finite products do not distribute over general coequalizers, but a cocomplete cartesian closed variant of $Top$ would work fine.

I had begun writing up some notes on this type of thing here, since some fellow over at MathOverflow seemed disinclined to believe me without either (1) a literature citation, or (2) a lot of detailed proof. It’s still not quite what you want since I was working just with one-sorted Lawvere theories, but meh, the generalization to multi-sorted won’t pose a problem. If no one produces a citation, I might be induced to rewrite it a little to get the multisorted case.

Wonder if Tom Leinster or some Australian knows where to find this?

Posted by: Todd Trimble on April 20, 2014 8:23 PM | Permalink | Reply to this

### Re: Finite Products Theories

I haven’t digested your notes, Todd, so I don’t have a grasp of why products need to distribute over coequalizers. But it occurs to me that the particular coequalizer John mentions is a reflexive coequalizer: if I’m not mistaken, $F \eta_{UFU(\phi)}$ is a common section. Is it possible that reflexive coequalizers suffice for the theory? (And do reflexive coequalizers commute with products in $\mathbf{Top}$?)

Posted by: Tim Campion on April 20, 2014 10:46 PM | Permalink | Reply to this

### Re: Finite Products Theories

Products don’t distribute over reflexive coequalizers either, in $Top$. There’s a cute easy result that you can construct general coequalizers from binary coproducts and reflexive coequalizers (see here, just before the corollary), and if products distribute over coproducts (as they do in $Top$), then they distribute over reflexive coequalizers iff they distribute over general coequlizers.

But this reminds me that one way of dealing with John’s question is to invoke the crude monadicity theorem – which crucially requires in this case that finite products distribute over reflexive coequlizers. I think the main hypothesis to check for invoking crude monadicity in this case is the existence of a left adjoint to the forgetful functor, and I believe this is rather easy, but maybe I should write this down when I get a chance. Better yet, someone will supply a good reference.

Posted by: Todd Trimble on April 20, 2014 11:05 PM | Permalink | Reply to this

### Re: Finite Products Theories

It is indeed surprisingly hard to find a theory of generalized operads/multicategories that includes the cartesian case. Geoff Cruttwell and I did include it in our “unified framework”, where the basic idea (not original to us) is to extend the “free category with finite products” 2-monad to the bicategory of profunctors and consider monads in the resulting Kleisli bicategory. Our contribution was to generalize from bicategories to “virtual double categories” to deal with the case when the extension of the monad is only lax, but in this case the extension is in fact an ordinary monad, and so we do get an honest Kleisli bicategory. And of course one-sided modules over a monad in any bicategory with local coproducts are monadic, by the “obvious” construction. We mentioned the case of cartesian operads (progressively adding more structure as we developed it abstractly) in Examples 3.15, 4.17, 4.18, 5.12, and A.13, although we left all the proofs to the reader. (-:

Todd’s context of 2-monads that distribute over the presheaf monad is of course closely related to ours, since Prof is the Kleisli bicategory of the presheaf monad. We remarked on this in 4.21.

Posted by: Mike Shulman on April 21, 2014 6:37 AM | Permalink | Reply to this

### Re: Finite Products Theories

Todd wrote:

I had begun writing up some notes on this type of thing here

Thanks, that’s helpful! It’s good to know that the category $C$ (in my example, some version of $Top$) just needs to be cocomplete and cartesian closed.

It’s still not quite what you want since I was working just with one-sorted Lawvere theories…

… but meh, the generalization to multi-sorted won’t pose a problem.

It would be great if I could induce you to include that. Or maybe I can do it myself.

I see your notes are focused on the relation between algebraic theories and operads. This is amusing, because — laying my cards on the table — the multi-sorted algebraic theory I really wanted to apply my result to is the algebraic theory of operads! So there’s a funny level shift going on.

Of course Jim Dolan and I noted a while back that there’s a multi-sorted operad whose algebras are operads, but I thought algebraic theories had been worked out in more detail.

So, I’d optimistically written something like this:

Let $Op$ be the category of symmetric topological operads and let $Top^{\mathbb{N}}$ be the category of collections. Every operad $O$ has an underlying collection $(O_n)_{n \in \mathbb{N}}$ so there is a functor

$U : Op \to Top^{\mathbb{N}}$

A quick way to see that $U$ has a left adjoint, and to understand some properties of this adjunction, is to note that operads are models of a certain algebraic theory: that is, a category with finite products. Let us call this algebraic theory $Operad$. This theory can be presented by a sketch with one object $o_n$ for each $n \ge 0$, one morphism

$\circ : o_n \times o_{k_1} \times \cdots \times o_{k_n} \to o_{k_1 + \cdots + k_n}$

for each $n \in \mathbb{N}$ and $n$-tuple $k_1, \dots k_n \in \N$, one morphism

$\sigma : o_n \to o_n$

for each $\sigma \in S_n$, and a morphism

$i : 1 \to o_1 ,$

where these morphisms obey the usual laws for the compositions, permutation actions and unit of an operad. $\Top$ is also a category with finite products, and a model of $Operad$ in $Top$, that is a product-preserving functor $\phi : Operad \to Top$, is nothing but an operad.

By general facts about algebraic theories [], this means that $U$ has a left adjoint

$F : Top^{\mathbb{N}} \to Op$

and $Op$ is equivalent to the category of algebras of the monad $U F$.

Of course we could construct and study this left adjoint $F$ ‘by hand’ using trees, and this is eventually what we do, but it would be easier and nicer if we had the above infrastructure already at our disposal.

Posted by: John Baez on April 21, 2014 12:06 PM | Permalink | Reply to this

### Re: Finite Products Theories

I think multi-sorted operads (aka “colored operads” or “multicategories”) actually have been worked out in more detail than multi-sorted algebraic theories (aka “cartesian operads”).

Posted by: Mike Shulman on April 21, 2014 5:26 PM | Permalink | Reply to this

### Re: Finite Products Theories

Mike wrote:

I think multi-sorted operads (aka “colored operads” or “multicategories”) actually have been worked out in more detail than multi-sorted algebraic theories (aka “cartesian operads”).

Okay, I’m not fussy—I just want to get the job done.

Can you point me to a general theorem implying that given a set $\Lambda$ of ‘colors’ or ‘sorts’ and an $\Lambda$-colored topological operad $O$,

1) the forgetful functor from the category of $O$-algebras to $Top^\Lambda$ has a left adjoint, and

2) this forgetful functor is monadic?

(Here as mentioned before I’m perfectly happy to replace the old-fashioned category $Top$ with one of the standard ‘convenient categories of topological spaces’. Also, I need my operads to be symmetric.)

Since all I really care about is the special case where $\Lambda = \mathbb{N}$ and $O$ is the colored operad whose algebras are operads, I’d be equally happy to get straight to the point and find a reference proving this:

1) the forgetful functor from the category of topological operads to $Top^{\mathbb{N}}$ has a left adjoint, and

2) this forgetful functor is monadic.

And if necessary, instead of using collections (objects $O \in Top^{\mathbb{N}}$) I could probably get away with using symmetric collections (objects $O \in Top^{\mathbb{N}}$ where $O(n)$ has an action of $S_n$). So I’d also be content, in a grudging sort of way, to learn that someone has shown:

1) the forgetful functor from topological operads to symmetric collections has a left adjoint, and

2) this forgetful functor is monadic.

My collaborator just pointed out that this result is almost proved:

If $C$ is any symmetric monoidal category in which the tensor product preserves colimits on both sides, then the free-forgetful adjunction between the category of symmetric operads in $C$ and the category of symmetric collections in $C$ is monadic. Benoit Fresse proved this for what he calls connected operads (which are operads with no term of arity zero and such that the term of arity one is the unit of the monoidal category) in Theorem B.4.3 of Appendix B of his book Homotopy of Operads and Grothendieck-Teichmüller Groups. He also mentions at the beginning of Appendix B that the same is true for not necessarily connected operads.

This may be good enough. However, it would be a bit odd if nobody had ever really written up a proof of any of my desired results.

Posted by: John Baez on April 21, 2014 8:02 PM | Permalink | Reply to this

### Re: Finite Products Theories

My guess is that this is one of those facts that everyone can basically see how to prove, but doesn’t want to bother (or take the space) to write out in detail. (-:

Posted by: Mike Shulman on April 22, 2014 6:55 PM | Permalink | Reply to this

### Re: Finite Products Theories

Since I’m not a trained category theorist I can see this fact is true, but not how to prove it — I don’t have lots of monadicity theorems and tricks like that up my sleeve. So, ironically, this makes me more annoyed that nobody else has proved it, and more eager to fill this hole in the literature.

Posted by: John Baezb on April 23, 2014 11:33 AM | Permalink | Reply to this

### Re: Finite Products Theories

Occasionally I wonder whether category theory has more than its fair share of ‘folklore results’, relative to other fields of mathematics. I do get an impression that a lot of category theory keeps getting rediscovered because people perceive a need for such-and-such a result and, not finding it “in the literature”, wind up proving it for themselves (sometimes in a less-than-optimal way). But I don’t have hard data to back up those suspicions.

Posted by: Todd Trimble on April 23, 2014 1:36 PM | Permalink | Reply to this

### Re: Finite Products Theories

I’ve wondered about the same thing. It does seem to happen a lot, because category theory is useful in so many fields of math and yet most non-category-theorists are not well versed in the category-theoretic literature, that they often rediscover (and, sadly, rename) things for themselves. There may also be an effect coming from the fact that so many proofs in category theory are so straightforward once you’re familiar with the subject; as Tom has pointed out several times, very often there’s only one thing you can do, so you do that thing, and it works. So that may incline people to leave such proofs to the reader more than otherwise.

But I also don’t really have data to back this up. The other fields that I have the most acquaintance with are algebraic topology and type theory, and I think there’s plenty of folklore in each of them too. Less than in category theory? I don’t even know how to go about trying to quantify that.

Posted by: Mike Shulman on April 23, 2014 7:43 PM | Permalink | Reply to this

### Re: Finite Products Theories

Okay, thanks for the additional information, John. There seem to be a lot of accounts of trees and free operads and so forth, but I’ve often been unhappy with the accounts I’ve seen, for one reason or another. A lot of the time it has to do with a somewhat cavalier attitude towards nullary operations, or with general hand-waviness, or something. I don’t wish to name names here; suffice it to say that I expect a good account from you!

Of course, you and Jim Dolan famously worked on typed operads in your development of opetopes, and so all the stuff we’re discussing (multisorted cartesian operads) should be old familiar ground, in some sense, even though you guys were dealing with the doctrine of symmetric monoidal categories rather than cartesian monoidal categories.

In case it’s useful to you, I’ve written down one possible account which proves the theorem I asserted earlier in this thread:

If $C$ is cocomplete, and has finite products that distribute over colimits, then for any $\Lambda$-sorted Lawvere theory $\Theta$, the forgetful functor $U: Mod_C(\Theta) \to C^\Lambda$ is monadic.

I chose to prove this by going through and checking the hypotheses of the crude monadicity theorem. This is not actually the route that I favor (you don’t have to deal with technical hypotheses of crude monadicity at all – one can check monadicity quite directly!), but I thought at least the buzzwords would be more familiar in such an approach, more so than in the other approach that I’d prefer.

Anyway, it’s all laid out here.

Posted by: Todd Trimble on April 22, 2014 2:54 AM | Permalink | Reply to this

### Re: Finite Products Theories

Todd wrote:

Anyway, it’s all laid out here.

Wow, great!

Would you prefer that I cite this, or include it as an appendix to our paper, authored by you?

The latter might be good, because there seems to be a kind of hole in the literature around this point, and not everyone is comfortable citing websites yet, so putting this result in a journal might be helpful. Of course you might be embarrassed to have a smallish result with a deliberately ‘crude’ proof appear under your name… you could obviously write something much grander… but what you did is really just the right level for the context of our paper, and we can add suitable disclaimers if it helps. (Also, I’d make some of the language a bit more formal and stiff, as befits a journal.)

There seem to be a lot of accounts of trees and free operads and so forth, but I’ve often been unhappy with the accounts I’ve seen, for one reason or another. A lot of the time it has to do with a somewhat cavalier attitude towards nullary operations, or with general hand-waviness, or something.

Yes, I’ve been feeling the same way as Nina and I try to put this paper together. I’d hoped that all the infrastructure had been adequately developed and we could just use it. But the foundations feel a bit shaky. Some results have unncessary restrictive assumptions on nullary and unary operations, and many authors use the concept of ‘tree’ without defining it, which seems fine until you notice that different authors are using different notions.

We want to describe free operads and coproducts of operads using trees. It’s possible to do this ‘directly’, by hand, but this becomes quite fussy. So it seems better to start by constructing these structures ‘abstractly’, applying general results on multi-sorted Lawvere theories to the theory of operads, and then prove that the structures thus constructed can be describe in terms of trees. And indeed, the really good concepts of ‘tree’ fall out as consequences of operad theory, as sketched here.

I don’t wish to name names here; suffice it to say that I expect a good account from you!

I doubt we’ll do things in an optimal way, since I don’t have the patience and it’s all a big digression from the original goal of the paper. In particular, our definition of ‘planar tree’ is a longish nuts-and-bolts affair, which we retroactively make elegant by showing how planar trees are precisely operations in the free operad on the terminal collection. I bet someone here could polish the initial definition to a fine sheen of perfection. But I don’t want to… I want the proofs to be actual proofs, but I don’t want this foundational material to utterly take over what started as a paper on phylogenetic trees!

Posted by: John Baez on April 22, 2014 8:46 AM | Permalink | Reply to this

### Re: Finite Products Theories

As a kind of sidebar to all this discussion: even for humble examples of algebraic theories, such as the one-sorted theory of groups, there is a sizable literature on the structure of free topological models, with long and difficult-looking papers particularly in the Russian literature, by the likes of Markov, Mal’cev, and others.

I think a lot of the technicalities of the subject might have to do with concerns that many people might find extraneous, such as the need to ensure that the unit of the monad is a topological embedding and the like.

Anyway, when I googled this just now, I was pleased to note this paper by Porst, who emphasizes the desirability to work not in $Top$ (where some things go kafloo-ey) but in some convenient category of spaces such as $k$-spaces.

Posted by: Todd Trimble on April 22, 2014 1:32 PM | Permalink | Reply to this

### Re: Finite Products Theories

Although I had slightly “dissed” the approach I wrote up (towards answering John’s query) as maybe needlessly complicated, since the monadicity can be established directly without verifying the hypotheses of the crude monadicity theorem, one bright side of this approach did occur to me a little while ago.

The point is that while it’s nice to know that $Op \to C^\mathbb{N}$ (for a cartesian closed cocomplete $C$) is monadic, this by itself doesn’t give you everything you’d like to know. It’s a notorious fact about monads $T$ and their algebras that even if your base category $B$ is cocomplete, the category of algebras $B^T$ might not be. Barr and Wells have a lot of material to address this very point.

For example, maybe you want to convince yourself that $Op$ has colimits. Even just coproducts: I’ve seen papers that go through some machinations just to prove that the category of $C$-valued operads has coproducts.

But happily, all this comes out of the wash when you take the “crude monadicity theorem” approach. Let me recall that theorem:

Crude monadicity theorem. A functor $U: A \to B$ is monadic if

• $U$ has a left adjoint $F$,
• $A$ has reflexive coequalizers,
• $U$ preserves reflexive coequalizers, and reflects isomorphisms.

Here’s the extra bonus:

Under the hypotheses of the crude monadicity theorem, if $B$ is cocomplete, then so is $A$.

Proof: Let $T$ be the monad $U F$; let $\eta: 1_B \to U F$ be the unit and $\varepsilon: F U \to 1_A$ be the counit of the adjunction. First, a family of free $T$-algebras $\{F(c_i)\}_{i \in I}$ has a coproduct: it’s just $F(\sum_i c_i)$ since the left adjoint $F$ preserves coproducts.

Next, under our hypotheses, the category of $T$-algebras $A$ has arbitrary coproducts, because the coproduct of a family $\{a_i\}_{i \in I}$ of algebras can be exhibited as a coequalizer of a reflexive fork diagram consisting of coproducts of free algebras:

$\sum_i F U a_i \stackrel{\sum_i F \eta U a_i}{\to} \sum_i F U F U a_i \stackrel{\overset{\sum_i \varepsilon F U a_i}{\to}}{\underset{\sum_i F U \varepsilon a_i}{\to}} \sum_i F U a_i$

Finally, coequalizers (not just reflexive coequalizers) exist in $A$, because $A$ has binary coproducts, and the coequalizer of a general pair of arrows $a' \stackrel{\overset{f}{\to}}{\underset{g}{\to}} a$ can be computed as the coequalizer of the reflexive fork

$a \stackrel{incl}{\to} a + a' \stackrel{\overset{(1_a, f)}{\to}}{\underset{(1_a, g)}{\to}} a.$

Posted by: Todd Trimble on April 25, 2014 5:08 PM | Permalink | Reply to this

### Re: Finite Products Theories

A nice observation! Basically, an easy way to show cocompleteness is to invoke a theorem of Linton which says that as soon as a category of algebras for a monad on a cocomplete category has reflexive coequalizers, then it is cocomplete. But if you showed that the category was monadic using CMT, then you’ve already done the work of showing that it has reflexive coequalizers.

Note that instead of your separate argument for coequalizers at the end, you could also observe that in the usual construction of arbitrary colimits out of coproducts and coequalizers, the coequalizer is actually reflexive.

Posted by: Mike Shulman on April 25, 2014 9:17 PM | Permalink | Reply to this

### Re: Finite Products Theories

Note that instead of your separate argument for coequalizers at the end, you could also observe that in the usual construction of arbitrary colimits out of coproducts and coequalizers, the coequalizer is actually reflexive.

Ah! That had never occurred to me before, but of course you’re right. (Just very recently I had responded to Emily’s comment on that canonical diagram for a colimit out of coproducts and coequalizers being the tail end of a simplicial object [a two-sided bar construction], but it hadn’t dawned on me that this means a reflexive fork is sitting right there…)

Posted by: Todd Trimble on April 26, 2014 12:49 AM | Permalink | Reply to this

### Re: Finite Products Theories

Dear John,

I think that exactly what you need, at exactly the right level of generality, is in:

Borceux and Day, Universal algebra in a closed category, JPAA 16 (1980)

Apply Theorem 2.2.2 to the morphism of theories from $F\Lambda$, the free category with finite products on $\Lambda$, into $C$.

Posted by: Richard Garner on May 4, 2014 10:10 PM | Permalink | Reply to this

### Re: Finite Products Theories

(Assuming that you are working with some cartesian closed category of spaces, rather than with $\mathbf{Top}$ itself.)

Posted by: Richard Garner on May 5, 2014 4:19 AM | Permalink | Reply to this

### Re: Finite Products Theories

Thanks a lot, Richard—I’ll check it out! We’re indeed happy to work with a cartesian closed category of spaces, so that’s fine.

In the meantime Todd has written up a proof, so we’ll have to see what’s new and publishable and what’s not.

Posted by: John Baez on May 5, 2014 10:57 AM | Permalink | Reply to this

### Re: Finite Products Theories

Actually, if you just need exactly the thing you asked for, then you could do no better than Boardman and Vogt’s “Homotopy invariant algebraic structures on topological spaces” (from 1973!)

“Defineorem 2.24” on page 49 says exactly that, for any (topological) $\Lambda$-sorted algebraic theory, the forgetful functor from the category of models into $\mathbf{Top}^\Lambda$ has a left adjoint.

Proposition 2.33 on page 56 says exactly that the forgetful functor is (strictly) monadic.

These are special cases of the Day and Borceux result I cited earlier (which are in turn special cases of more general later results on Lawvere theories due to, amongst others, Power, Lack and Rosicky). But for something that matches up precisely to what you want, you couldn’t do much better than Boardman and Vogt!

Posted by: Richard Garner on May 5, 2014 12:36 PM | Permalink | Reply to this

Post a New Comment