## September 16, 2019

### Partial Evaluations 2

#### Posted by John Baez

guest post by Carmen Constantin

This post belongs to the series of the Applied Category Theory Adjoint School 2019 posts. It is a follow-up to Martin and Brandon’s post about partial evaluations.

Here we would like to use some results by Clementino, Hofmann, and Janelidze to answer the following questions: When can we compose partial evaluations? and more generally When is the partial evaluation relation transitive?

## Introduction

In this post, for simplicity, we study monads over the category of sets. A similar discussion can be had in more general categories by replacing elements of a set $X$ by generalized elements, that is, arrows into the object $X$. See this previous blog post for more details about this.

An algebra $(A,e)$ of a monad $T$ comes equipped with a way of evaluating the expressions in $T A$ via the map $e \colon T A \rightarrow A$

This algebra map has to interact nicely with the multiplication of the monad, in particular making $e$ the coequalizer of the pair $\mu, Te \colon T T A \rightarrow T A.$

This can be used to refine the notion of evaluation: a term $t_1$ is a partial evaluation of a term $t_0$, written $t_0 \rightsquigarrow t_1$ if there is a ‘one dimension higher’ term $\tau_{01}$ in $T T A$ which witnesses the partial evaluation in the sense that $\mu(\tau_{01})=t_0$ and $Te(\tau_{01})=t_1$ in the diagram

The blue line expresses the partial evaluation relation, that is, the existence of such an element in $T T A$ given $t_0$ and $t_1$. Note that, since the black arrows of the diagram above commute, a necessary condition for the existence of such $\tau_{01}$ is that $e(t_0)$ agrees with $e(t_1)$ in $A$.

We have seen in a previous blog post that the partial evaluation relation is reflexive, and for some monads, e.g. the Free Monoid/List monad, it is also transitive: if $t_0 \rightsquigarrow t_1$ and $t_1\rightsquigarrow t_2$ are witnessed by $\tau_{01}$ and $\tau_{12}$ respectively, then there is some $\tau_{02}$ witnessing $t_0 \rightsquigarrow t_2$

One could ask whether there is a term $\Theta$ in $T T T A$ such that $\mu_T(\Theta)=\tau_{01}$ and $TTe(\Theta)=\tau_{12}$. If such a term exists, then one can simply take $\tau_{02}:=T\mu(\Theta)$ to be the desired witness for transitivity.

The existence of such a term $\Theta$ corresponds to the existence of a strategy for finding a transitivity witness.

This can be summarised in the following picture:

where we have indicated the existence of partial evaluations by a pair of squiggly lines highlighted in dark blue (to avoid confusion with the diagram’s actual arrows), while their composite is highlighted in light blue.

Remark 1. A strategy $\Theta$ always exists if the back square of the cube above (which we shall refer to as ‘the monad’s cube’) is a weak pullback.

A weak pullback square is a commutative square with the existence but not necessarily the uniqueness condition of the universal property of pullbacks (see the nLab page on weak limits). Of course, a transitivity witness might exist even if there is no strategy for finding it.

Note also that the partial evaluations and their composite form a triangle, i.e. a 2-simplex, if view the bar construction as a simplicial set—see the previous blog post.

Moreover, in simplicial language, the outer green arrows correspond to the two edges forming an inner 2-horn, while the one labeled ‘transitivity witness’ is the missing edge of the horn. The existence of the strategy arrow corresponds to the existence of what is called a horn filler. As we have previously noted, a transitivity witness $\tau_{02}$ might exist even if there is no horn filler.

A quick intuitive example to illustrate the transitivity property is given by the free commutative monoid monad, where $T A$ consists of formal sums of elements in $A$. If $A=\mathbb{N}$, the algebra map simply evaluates a formal sum to return an element in $\mathbb{N}$. We can draw a picture of the terms $t_0=1+2+3+4$, $t_1=3+3+6$ and $t_2=6+4$ which illustrates the transitivity of the partial evaluation relation $t_0\rightsquigarrow t_1\rightsquigarrow t_2$.

Of course, if the partial evaluation relation is transitive, then we can think about forming even longer composites. For example, for three composable back-to-back partial evaluations (depicted in dark blue in the figure below) the existence of an associator (and hence a coherent way to compose them) would be given by a 3-simplex, i.e. a filled tetrahedron, which corresponds to an element of $T^4A$. This element should restrict under $\mu$, $T\mu$, $T^2\mu$ and $T^3e$ respectively to the corresponding elements in $T^3A$ that give the strategies for the binary composites.

This can be illustrated by a 4-dimensional cube diagram, where again dark blue lines represent the partial evaluations, light blue lines represent their binary composites and the labels of the monad’s cube have been suppressed to avoid clutter.

Each 3-horn corresponds to a union of all but one of the faces of the $3$-simplex. When the omitted face is the one opposite to the first or last of the corners of the tetrahedron, one speaks of outer horns, otherwise they are called inner horns. This terminology is important because aside from transitivity, which we shall talk about in the remainder of the blog post, we have also looked at the possibility of finding horn fillers for inner horns (for monads which allow binary composites), as their existence would make the structures arising from the bar construction into a quasicategory. However, it turned out that even when binary composites exist for all composable partial evaluations, it is not always possible to find such fillers.

When a monad is weakly cartesian, the partial evaluation relation is transitive. A monad $(T,\mu,\eta)$ is weakly cartesian if the functor $T$ preserves weak pullbacks, and all naturality squares of $\mu$ and $\eta$ are weak pullbacks. In particular the back square of the monad’s cube discussed in Remark 1 is a weak pullback, meaning that the aforementioned $\Theta$ in $T T T A$ exists.

Here is a well-known fact:

Remark 2. If a monad $T$ is associated to a variety of universal algebras, and the variety is operadic, then the functor $T$ is cartesian (and so, in particular, weakly cartesian).

To understand this statement note that a variety $\mathcal{C}$ comes equipped with a monadic free-forgetful adjunction between $\mathcal{C}$ and the category of sets, that is, the Eilenberg-Moore category of algebras for the monad $T$ is isomorphic to $\mathcal{C}$. Now consider a presentation $(\Omega, \phi)$ of the variety $\mathcal{C}$, where $\Omega$ is a signature (a set $\coprod_{n\geq 0} \Omega_n$ of function symbols of arbitrary but finite arity $n$, including the constants of arity zero), and $\phi$ is a set of equational laws or identities between terms in $\Omega$. A variety is operadic if it can be presented using a set of identities which have the same variables appearing in the same order, without repetition, on each side. For example, $a\cdot b+c=a-b\cdot c$ would be an admissible identity for an operadic theory, but $a\cdot b=b\cdot a$ and $a\cdot b=a$ would not.

Operadic (and hence cartesian) varieties include

• all varieties that can be presented with no identities, i.e. by a pair $(\Omega, \phi)$ where $\phi=\emptyset$ and in particular also all varieties in which $\Omega=\Omega_0$, such as sets and pointed sets.
• the variety of monoids, where $\Omega_2=\{*\}$ only contains the monoid multiplication and $\Omega_0=\{e\}$ is the constant representing the unit of the monoid. The identities in $\phi$ corresponding to the law of associativity and the unit law are clearly operadic.
• the variety of semigroups
• all varieties of the form $\mathbf{Set}^M$ where $M$ is a monoid, that is, of monoid actions on sets (including group actions).

The theory of groups on the other hand is not operadic: it contains the identity $g g^{-1}=e$, which is not allowed.

Since the monads associated to these varieties are cartesian, and so weakly cartesian, for these monads the partial evaluation relation is transitive. How, then, do partial evaluations behave for monads which are not weakly cartesian?

## Monads which are not weakly cartesian

The paper The monads of classical algebra are seldom weakly cartesian lists several necessary and several sufficient conditions for weak cartesianness of the functor $T$, the unit $\eta$ and the multiplication $\mu$ respectively for monads defined over algebraic varieties in general and free semimodule monads in particular.

Notably, even if a monad is not weakly cartesian, a strategy for composing partial evaluations can be found by applying the map $T\mu:T^3A\rightarrow T^2A$ within the monad’s cube, as long as the square in Lemma 2 is a weak pullback—a much weaker condition than requiring weak cartesianness of $\mu$ as a natural transformation.

In fact we noticed that some monads which are not weakly cartesian still have transitive partial evaluations, such as the monad corresponding to the variety of $\mathbb{N}$-sets which satisfy the identity $2x=2y$, which in the paper is discussed in Example 3.4.

### A counterexample

The first interesting result for our project comes from the subsequent discussion in the paper, which can be used to show that counterexamples to transitivity also occur.

In particular, it is interesting to look at the free $S$-semimodule monad (let $(T,\eta,\mu)$ denote this monad), where $S$ is a particular semiring. There are a number of conditions stated in the paper such that, if any of them is satisfied by the semiring $S$, then the functor $T$ is a weakly cartesian functor:

• no non-zero elements in $S$ can have an additive inverse

• for every $a,b\in S$ there exists $x\in S$ such that either $a+x=b$ or $b+x=a$

• the additive monoid of $S$ is a monoid with cancellation (equivalently, it can be embedded into an abelian group).

Once $T$ is a weakly cartesian functor, the multiplication is weakly cartesian if and only if additionally

• No non-zero element in $S$ has an additive inverse

• $S$ has no (non-zero) zero divisors

• for any generating subset $C$ of $S$ and any $a,b,c,d\in S$ with $c\in C$ such that $cd=a+b$, there exists a map $t:\{(x,y)\in S\times S \ | \ x+y =d\}\longrightarrow S$ with $\sum_{x+y=d} t(x,y)x=a, \ \ \sum_{x+y=d}t(x,y)y=b, \ \ and \sum_{x+y=d}t(x,y)=c$

The counterexamples we are interested in arise from semirings which satisfy the first 5 conditions but fail to satisfy the last one.

Consider for example the free semimodule monad $T$ over the semiring $S=\mathbb{N}[x]/\langle x^2=2\rangle$. This monad is given by

• $T(X):=\{t:X\rightarrow S \ | \ t \ \text{ has finite support}\}$. To keep the presentation more intuitive, we can use a simpler notation for the elements of $T(X)$, writing each element as a formal sum $\sum s_i\cdot x_i,$ which consists of a finite number of terms in $X$ with coefficients in $S$. Note that two such formal sums represent the same element if and only if they have the same elements of $X$ with the same corresponding coefficients, but perhaps appearing in a different order in the expansion.

• the intuitive equivalent description of the unit is then $\eta_X(x)= 1\cdot x$

• the multiplication represents the familiar distributivity property: if $\tau=\sum_i z_i\cdot \sum_{j_i} s_{j_i}\cdot x_{j_i}$ then $\mu_X(\tau)=\sum_{i,j_i} (z_i s_{j_i})\cdot x_{j_i}$

An algebra map $e$ then simply evaluates the formal weighted sum $\sum s_i\cdot x_i$ to some element $\hat{x}\in X$. Thus an algebra for this monad corresponds to an actual semimodule over $S$, in the classical sense of the term.

Note that the map $T e:T T X\rightarrow TX$ is then given by

$Te\left(\sum_i z_i\cdot \sum_{j_i}s_{j_i}\cdot x_{j_i}\right)=\sum_i z_i\cdot \widehat{x_i}$ where $\widehat{x_i}=e\left(\sum_{j_i}s_{j_i}\cdot x_{j_i}\right)$ is the evaluation of the corresponding sum.

We can not only show that the back square of the monad’s cube is not a weak pullback for this monad, and hence no strategies for finding transitivity witnesses exist, but also that transitivity itself fails to hold for this monad. Let $A:=\{ \ast \}$ be the one element $T$-algebra, i.e. the zero semimodule. The elements of $T A$ are formal sums with just one term $s_i\cdot \ast$ and the evaluation map is trivial in the sense that the value of $s_i\cdot \ast$ is just $\ast$, as one would expect from multiplication acting on zero. There is a partial evaluation between the $T A$ terms $1\cdot \ast$ and $2\cdot \ast$ witnessed by the $T T A$ element $\tau=1\cdot 1\cdot \ast + 1\cdot 0\cdot \ast$ since $\mu(\tau)=(1\cdot 1)\cdot \ast +(1\cdot 0)\cdot \ast =1\cdot \ast +0\cdot \ast =1\cdot \ast$ and also $Te(\tau)=1\cdot e(1\cdot \ast)+ 1\cdot e(0\cdot \ast)=1\cdot \ast + 1\cdot \ast = 2\cdot \ast$

There is also a partial evaluation between $2\cdot \ast$ and $x\cdot \ast$ witnessed by the $T T A$ element $\tau'=x\cdot x\cdot \ast$ namely, $\mu(\tau')=(x\cdot x)\cdot \ast = 2\cdot \ast$ and also $Te(\tau')=x\cdot(x\cdot \ast)=x\cdot \ast$ However, there can be no partial evaluation from $1\cdot \ast$ to $x\cdot \ast$ because $T e$ maps any $\tau''=\sum_i z_i\cdot s_i\cdot \ast$ in $T T A$ to $\sum_i z_i\cdot \ast = \left(\sum_i z_i\right)\cdot \ast.$ So if $\tau''$ were a transitivity witness, we would need $\sum_i z_i= x.$ But $x$ is additively indecomposable in $S$. Hence $\tau''=x\cdot s\cdot \ast$, for some $s\in S$. But then $\mu(\tau'')=(x\cdot s)\cdot \ast$ which cannot equal $1\cdot \ast$, since $x$ is not a unit in $S$.

## Some further thoughts

It was quite satisfying to find a concrete answer to the transitivity question we started from. There are several directions that we could explore further.

• On the one hand, there are interesting connections with probability which Paolo Perrone has discussed in a previous blog post, and Brandon and Martin have written about.

• On the other hand, it has been pointed out to us that it is likely to find connections with multi-stage programming and partially static data structures which have been used by computer scientists to describe computations that give the programmer a fine-grained control over beta reduction. Being able to control evaluation provides a basis for optimisation of binding times.

• We can also further investigate these structures by trying for example to find out when partial evaluations are invertible. Together with transitivity, this would turn the partial evaluation into an equivalence relation.

If the algebra structure square

is a weak pullback, then the partial evaluation relation is an equivalence relation. One can ask if the converse also holds.

• A more sophisticated question than whether the relation being an equivalence is the following: when is the 1-truncation of the bar construction a groupoid? That is, in case we can form a category with partial evaluations as morphisms, when are all morphisms there invertible?

For example, let $G$ be a group. The theory of $G$-sets is operadic, so the associated monad $T(X)=G\times X$ is (strongly) cartesian, and the bar construction gives the nerve of a category. The 0-simplices are the elements $(g,x)$ of $G\times X$, the 1-simplices from $(g,x)$ to $(h,y)$ are the elements $(j,h,x)$ of $G\times G\times S$ such that $g= jh$ and $h\cdot x=y$, and so on. The partial evaluation relation here is an equivalence relation (the multiplication square is even an actual pullback – not just a weak one) and for this theory the bar construction of an algebra $A$ is the nerve of a groupoid.

This is probably very related to group cohomology: in this case, the bar construction is indeed a resolution of $A$, i.e. weakly equivalent to $A$. (The bar construction was actually first invented to compute the cohomology of $G$-modules, which are basically this example, just in an abelian category.)

• One can also ask higher-dimensional questions, such as when is the bar construction an infinity-groupoid (i.e. a Kan complex)?

It turns out that this last question has a partial answer which involves Mal’cev theories.

A Mal’cev operation on a set $A$ is a ternary operation $m:A\times A\times A\to A$ such that for each $a,b\in A$, $m(a,b,b) = a \; \text{and} \; m(a,a,b) = b.$ A Mal’cev theory is an algebraic theory which contains a Mal’cev operation.

In the algebraic theory of groups, there is a Mal’cev operation defined by $m(a,b,c) \; := \; a\,b^{-1}\,c.$ Therefore any theory whose algebras are groups, with possibly extra structures or properties, is a Mal’cev theory. These include for example the theories of groups, rings or modules over a fixed ring but not, for example, the theory of monoids, commutative monoids, semirings, and semimodules.

An example of a Mal’cev theory which is not a theory of particular groups is the theory of heaps.

A theorem by Carboni, Kelly and Pedicchio states that for any Mal’cev theory $T$ every simplicial object in the category of algebras is a Kan complex. This theorem can be found here. See also the nLab page about Kan complexes.

Therefore, for the theory of groups (and heaps, etc.), not only do we get an equivalence relation, but the whole bar construction is an $\infty$-groupoid, of which the equivalence relation is the shadow, i.e. the (0,1)-truncation.

Posted at September 16, 2019 11:31 AM UTC

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

### Re: Partial Evaluations 2

Nice stuff! It reminds me a little of my seminar on cohomology and computation, where I was advocating the bar construction as a systematic way of replacing equations by edges, equations between equations or ‘syzygies’ by triangles, and so on. But I spent the whole seminar explaining the bar construction and didn’t really get very far figuring out the computational aspects. It’s good to see people doing this now. I recommend bringing cohomology into the game.

Posted by: John Baez on September 19, 2019 8:44 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Nice to see you taking an interest!

I recommend bringing cohomology into the game.

That is tempting, but it goes somewhat against the spirit of the project: we’re interested in non-homotopy-invariant questions like

Which (higher) compositional structure are bar constructions instances of?

This question arises from the observation that for suitably nice monads $T$, the bar construction for $T$-algebras produces simplicial sets which have fillers for all inner 2-horns; so if we think of the 1-simplices as morphisms, then it’s possible to “compose” them. It’s surprisingly tricky to find algebraic theories whose associated monads do not have this property! So we’re busy working out the higher compositional structure of the bar construction for weakly cartesian monads. All of this is structure that gets washed away when you go to cohomology.

But perhaps you see some concrete relevance to cohomology that isn’t clear to us? If so, it would be good to know the details!

Posted by: Tobias Fritz on September 21, 2019 4:09 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

I was vaguely thinking of things like Squier’s result on homology and rewriting theory for monoids.

This may not be at all what you’re interested in, but I wrote about this in “week70” of This Week’s Finds, so I’ll quote it here. Pardon the slow start:

Yves Lafont also gave a talk with strong connections to n-category theory. Recall that a monoid is a set with an associative product having a unit element. One way to describe a monoid is by giving a presentation with “generators”, say

a, b, c, d,

and “relations”, say

ab = a, da = ac.

We get a monoid out of this in an obvious sort of way, namely by taking all strings built from the generators a,b,c, and d, and then identifying two strings if you can get from one to the other by repeated use of the relations. In math jargon, we form the free monoid on the generators and then mod out by the relations.

Suppose our monoid is finitely presented, that is, there are finitely many generators and finitely many relations. How can we tell whether two elements of it are equal? For example, does

dacb = acc

in the above monoid? Well, if the two are equal, we will always eventually find that out by an exhaustive search, applying the relations mechanicallly in all possible ways. But if they are not, we may never find out! (For the above example, the answer appears at the end of this article in case anyone wants to puzzle over it. Personally, I can’t stand this sort of puzzle.) In fact, there is no general algorithm for solving this “word problem for monoids”, and in fact one can even write down a specific finitely presented monoid for which no algorithm works.

However, sometimes things are nice. Suppose you write the relations as “rewrite rules”, that go only one way:

ab → a

da → ac

Then if you have an equation you are trying to check, you can try to repeatedly apply the rewrite rules to each side, reducing it to “normal form”, and see if the normal forms are equal. This will only work, however, if some good things happen! First of all, your rewrite rules had better terminate: it had better be that you can only apply them finitely many times to a given string. This happens to be true for the above pair of rewrite rules, because both rules decrease the number of b’s and c’s. Second of all, your rewrite rules had better be confluent: it had better be that if I use the rules one way until I can’t go any further, and you use them some other way, that we both wind up with the same thing! If both these hold, then we can reduce any string to a unique normal form by applying the rules until we can’t do it any more.

Unfortunately, the rules above aren’t confluent; if we start with the word dab , you can apply the rules like this

dab → acb

while I apply them like this

dab → da → ac

and we both terminate, but at different answers. We could try to cure this by adding a new rule to our list,

acb → ac.

This is certainly a valid rule, which cures the problem at hand… but if we foolishly keep adding new rules to our list this way we may only succeed in getting confluence and termination when we have an infinite list of rules:

ab → a

da → ac

acb → ac

accb → acc

acccb → accc

accccb → acccc…

and so on. I leave you to check that this is really terminating and confluent. Because it is, and because it’s a very predictable list of rules, we can use it to write a computer program in this case to solve the word problem for the monoid at hand. But in fact, if we had been cleverer, we could have invented a finite list of rules that was terminating and confluent:

ab → a

ac → da

Lafont’s went on to describe some work by Squier:

6) Craig C. Squier, Word problems and a homological finiteness condition for monoids, Jour. Pure Appl. Algebra 49 (1987), 201-217.

Craig C. Squier, A finiteness condition for rewriting systems, revision by F. Otto and Y. Kobayashi, to appear in Theoretical Computer Science.

Craig C. Squier and F. Otto, The word problem for finitely presented monoids and finite canonical rewriting systems, in Rewriting Techniques and Applications, ed. J. P. Jouannuad, Lecture Notes in Computer Science 256, Springer, Berlin, 1987, 74-82.

which gave general conditions which must hold for there to be a finite terminating and confluent set of rewrite rules for a monoid. The nice thing is that this relies heavily on ideas from n-category theory. Note: we started with a monoid in which the relations are equations, but we then started thinking of the relations as rewrite rules or morphisms, so what we really have is a monoidal category. We then started worrying about “confluences”, or equations between these morphisms. This is typical of “categorification”, in which equations are replaced by morphisms, which we then want to satisfy new equations.

For the experts, let me say exactly how it all goes. Given any monoid M, we can cook up a topological space called its “classifying space” KM, as follows. We can think of KM as a simplicial complex. We start by sticking in one 0-simplex, which we can visualize as a dot like this:

O


Then we stick in one 1-simplex for each element of the monoid, which we can visualize as an arrow going from the dot to itself. Unrolled a bit, it looks like this:

O---a---O


Really we should draw an arrow going from left to right, but soon things will get too messy if I do that, so I won’t. Then, whenever we have ab = c in the monoid, we stick in a 2-simplex, which we can visualize as a triangle like this:

      O
/ \
a   b
/     \
O---c---O


Then, whenever we have abc = d in the monoid, we stick in a 3-simplex, which we can visualize as a tetrahedron like this

          O
/|\
/ | \
/  b  \
a   |   bc
/   _O_   \
/   /   \_  \
/ _ab      c_ \
/_/           \_\
O--------d--------O


And so on… This is a wonderful space whose homology groups depend only on the monoid, so we can call them Hk(M).
If we have a presentation of M with only finitely many generators, we can build KM using 1-simplices only for those generators, and it follows that H1(M) is finitely generated. (More precisely, we can build a space with the same homotopy type as KM using only the generators in our presentation.) Similarly, if we have a presentation with only finitely many relations, we can build KM using only finitely many 2-simplices, so H2(M) is finitely generated. What Squier showed is that if we can find a finite list of rewrite rules for M which is terminating and confluent, then we can build KM using only finitely many 3-simplices, so H3(M) is finitely generated!

What’s nice about this is that homological algebra gives an easy way to compute Hk(M) given a presentation of M, so in some cases we can prove that a monoid has no finite list of rewrite rules for M which is terminating and confluent, just by showing that H3(M) is too big. Examples of this, and many further details, appear in Lafont’s work:

7) Yves Lafont and Alain Proute, Church-Rosser property and homology of monoids, Mathematical Structures in Computer Science 1 (1991), 297-326. Also available at http://iml.univ-mrs.fr/~lafont/publications.html

Yves Lafont, A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier), Journal of Pure and Applied Algebra 98 (1995), 229-244. Also available at http://iml.univ-mrs.fr/~lafont/publications.html

(Answer: dacb = ddab = dda = dac = acc.)

Posted by: John Baez on September 22, 2019 7:10 AM | Permalink | Reply to this

### Re: Partial Evaluations 2

That is very interesting and could be worth looking into — thanks for the pointer!

Posted by: Tobias Fritz on September 22, 2019 2:24 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Carmen wrote

A variety is operadic if it can be presented using a set of identities which have the same variables appearing in the same order, without repetition, on each side.

I wouldn’t say they need to be in the same order. But there’s a difference between non-symmetric operads, where we’d require the variables to be in the same order, and symmetric operads, where we don’t. So, there are two imaginable concepts of ‘operadic variety’.

Most people mean ‘symmetric operad’ when they say operad. But more important than these issues of terminology: do you really need the operad to be non-symmetric for the corresponding monad to be cartesian? I don’t understand this stuff well, but that seems curious to me.

For example, is the monad for commutative monoids cartesian or not? Commutative monoids are algebras of a symmetric operad but not a non-symmetric one. The reason is the identity $a b = b a$.

Posted by: John Baez on September 19, 2019 8:56 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

is the monad for commutative monoids cartesian or not?

No.

The free commutative monoid monad fails to be cartesian in two ways. First, the free commutative monoid endofunctor $T$ doesn’t preserve pullbacks. Second, the multiplication natural transformation $T^2 \to T$ is not cartesian. Details are in Example 4.1.5 of my higher categories book, though I learned about $T$ not preserving pullbacks from Mark Weber.

Another, less rigorous, way to look at it: it’s almost true that any cartesian monad on $Set$ is the monad of some non-symmetric operad. So if the free commutative monoid monad was cartesian, there’d by be some non-symmetric operad whose algebras were commutative monoids. That sounds pretty unlikely! And indeed it’s false.

Posted by: Tom Leinster on September 21, 2019 12:06 AM | Permalink | Reply to this

### Re: Partial Evaluations 2

On the same theme: what if you wanted to prove that the monad for commutative monoids doesn’t come from any non-symmetric operad?

Of course, it’s not enough to say “I can’t think of any non-symmetric operad whose induced monad is the commutative monoid monad”. Unlikely as it may seem, maybe there’s one you haven’t thought of that does the job.

Similarly, it’s not enough to say “the obvious presentation of the theory of commutative monoids involves an equation where the variables change order, so it can’t be encoded by a non-symmetric operad”. Maybe there’s some really sneaky presentation you hadn’t thought of that doesn’t involve permuting the variables.

The only proof I know goes like this:

• The commutative monoid monad isn’t cartesian.

• So there’s no non-symmetric operad in the world whose induced monad is the commutative monoid monad.

Does anyone know any other proof?

Posted by: Tom Leinster on September 23, 2019 6:48 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Tom wrote:

Does anyone know any other proof?

Not immediately, but your proof seems overly sneaky, so I’m motivated to find a more pedestrian proof, based on the naive idea that “a nonsymmetric operad can’t express the commutative law”.

Here’s how I might start trying to tackle it. I believe there’s an adjunction between nonsymmetric operads and symmetric operads, such that if $O$ is a nonsymmetric operad and $L O$ the free symmetric operad on this, the category of algebras of $O$ (in $Set$, say) is equivalent to the category of algebras of $L O$. (Note “algebra of” means different things for nonsymmetric and symmetric operads.) Given an $n$-ary operation $f$ in a symmetric operad we get a bunch of operations I’ll call $f \sigma$, one for each permuation $\sigma \in S_n$. I believe that in a symmetric operad of the form $L O$ all $n!$ of these operations $f \sigma$ are distinct. That is, $S_n$ acts freely on the set of $n$-ary operations for an operad of the form $L O$.

I think this gives a contradiction if we also assume there’s some nonsymmetric operad $O$ whose algebras are commutative monoids. The idea is that the binary multiplication $f$ in $L O$ can’t obey $f = f \sigma$, where $\sigma \in S_2$ is the nontrivial permutation.

To get this contradiction, we need that if operations $f,g$ in a symmetric operad obey an equation $A(f) = A(g)$ for every algebra $A$ of that operad in $Set$, then we must have $f = g$ in the operad itself. I think this follows from known results on Lawvere theories, together with the usual way to turn symmetric operads into Lawvere theories.

This is a quite sketchy sketch of a proof, but I’m getting optimistic that I could fill it in.

Posted by: John Baez on September 23, 2019 7:22 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

your proof seems overly sneaky, so I’m motivated to find a more pedestrian proof, based on the naive idea that “a nonsymmetric operad can’t express the commutative law”.

Since you use the words “your proof”, I should clarify that I surely wasn’t first to come up with this, though I’ve no idea who was.

I’m not sure I’d describe that proof as any less intuitive, or “sneakier”, than the one you sketch. Cartesianness of a monad should be thought of as “preserving shape”, which in this case (monads on $Set$) means keeping the same sequence of variables on each side of the equation rather than permuting them, duplicating them, etc. So to me it seems quite intuitive!

But of course, descriptions like “intuitive”, “sneaky”, “naive” and “pedestrian” are very subjective. And it’s true that the proof I mentioned does involve passing back and forwards between operads and monads, rather than staying purely in the world of operads. In any case, two proofs are better than one!

So let’s see…

I believe there’s an adjunction between nonsymmetric operads and symmetric operads, such that if $O$ is a nonsymmetric operad and $L O$ the free symmetric operad on this, the category of algebras of $O$ (in $Set$, say) is equivalent to the category of algebras of $L O$. (Note “algebra of” means different things for nonsymmetric and symmetric operads.) Given an $n$-ary operation $f$ in a symmetric operad we get a bunch of operations I’ll call $f \sigma$, one for each permuation $\sigma in S_n$. I believe that in a symmetric operad of the form $L O$ all $n!$ of these operations $f\sigma$ are distinct. That is, $S_n$ acts freely on the set of $n$-ary operations for an operad of the form $LO$.

Yes, that’s right. That left adjoint $O \mapsto L O$ is described explicitly in Miles Gould’s PhD thesis, starting at the bottom of page 44. It’s called $F_\Sigma^{pl}$ there (because it turns a plain operad into a $\Sigma$-operad, i.e. a non-symmetric operad into a symmetric operad).

You can actually get a proof right now of the result we’re after, if you’re willing to assume another theorem. It was shown (I think by Mark Weber, using work of Joyal) that if two symmetric operads induce the same monad, they must be isomorphic. That’s quite a tricky theorem, as suggested by the fact that the analogous statement for non-symmetric operads is false: one can find a pair of non-symmetric operads that are not isomorphic but whose induced monads are! So the proof must use the symmetry in some essential way.

Anyway, if you assume that theorem about symmetric operads, it’s game over. For if $O$ is a non-symmetric operad whose induced monad is the commutative monoid monad then $L O$ is a symmetric operad whose induced monad is also the commutative monoid monad. (The two occurrences of “induced monad” in the last sentence mean different things.) Hence by that theorem I just mentioned, $L O$ must be the terminal symmetric operad. But by the explicit description of $L O$, that’s impossible, since $1/n!$ is not usually an integer.

So that gives a second proof. But it’s a proof that calls on a tricky theorem, so maybe we can find a better, third, proof. Back to your sketch, then…

To get this contradiction, we need that if operations $f,g$ in a symmetric operad obey an equation $A(f)=A(g)$ for every algebra $A$ of that operad in $Set$, then we must have $f=g$ in the operad itself.

That I don’t know about. It certainly sounds plausible, and if I had to bet I’d say it’s true. But these things can be a bit slippery, again as evidenced by that result about non-isomorphic non-symmetric operads sometimes inducing the same monad.

Posted by: Tom Leinster on September 23, 2019 8:40 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Tom wrote:

I’m not sure I’d describe that proof as any less intuitive, or “sneakier”, than the one you sketch. Cartesianness of a monad should be thought of as “preserving shape”, which in this case (monads on $Set$) means keeping the same sequence of variables on each side of the equation rather than permuting them, duplicating them, etc. So to me it seems quite intuitive!

Okay. I have no understanding whatsoever of cartesian monads: I have always plugged my ears with cotton whenever anyone starts talking about them, because I have no idea why I should be interested. So the idea of pulling them in to prove that no non-symmetric operad can describe commutative monoids felt like a ‘trick’ to me.

I’m glad to hear that cartesianness of a monad actually has some intuitive essence, namely ‘preserving shape’. I have no idea what that means, but very often the first step toward learning a concept is becoming convinced that it’s not just technical mumbo-jumbo that people like to mumble off in the distance.

You can actually get a proof right now of the result we’re after, if you’re willing to assume another theorem. It was shown (I think by Mark Weber, using work of Joyal) that if two symmetric operads induce the same monad, they must be isomorphic.

Nice! I’m certainly willing to accept this. The way I see it, a symmetric operad is just a Lawvere theory with a certain property. A bit more technically: [symmetric operads] is a full subcategory of [Lawvere theories]. On the other hand, two Lawvere theories that induce the same monad on $Set$ must be isomorphic. So the same is true for symmetric operads.

Maybe I’m mixed up and things are more subtle than this. But this circle of thoughts is why I believe this:

we need that if operations $f,g$ in a symmetric operad obey an equation $A(f)=A(g)$ for every algebra $A$ of that operad in SetSet, then we must have $f=g$ in the operad itself.

You see, this is true for Lawvere theories.

But this makes an interesting counterpoint:

[…] one can find a pair of non-symmetric operads that are not isomorphic but whose induced monads are!

Posted by: John Baez on September 23, 2019 9:33 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

I’m glad to hear that cartesianness of a monad actually has some intuitive essence, namely ‘preserving shape’. I have no idea what that means, but very often the first step toward learning a concept is becoming convinced that it’s not just technical mumbo-jumbo that people like to mumble off in the distance.

Yes, that’s basically all I was trying to get across — that my argument doesn’t rely on some clever trick or technicality.

I probably don’t have the energy to properly justify that statement that cartesian means “preserving shape”. But to give a quick indication: think of the algebraic axioms for strict $\infty$-categories, such as the interchange law:

The left- and right-hand side of the equations have the same shape, in some intuitive sense. And this is related to the fact that the free strict $\infty$-category monad is cartesian.

On page 38 of Miles Gould’s thesis there’s this nice diagram:

The category called FP-operad is equivalent to the category of Lawvere theories. The FP stands for “finite product”, and the point is that a Lawvere theory can be construed as an operad-like thing where instead of having a map $\sigma_\ast: O_n \to O_n$ for each bijection $\sigma: \{1, \ldots, n\} \to \{1, \ldots, n\}$ on a finite set, you have a map $\sigma_\ast: O_n \to O_m$ for each function $\sigma: \{1, \ldots, n\} \to \{1, \ldots, m\}$. (I think some people call these “cartesian operads”.)

$\Sigma$-Operad is the category of symmetric operads, Operad is the category of non-symmetric operads, and $\mathbf{Set}^{\mathbb{N}}$ is the category of sequences of sets.

The curved arrows can be ignored, as they’re just composites of the straight ones. So really we’re just looking at the three adjunctions that form the spine of the diagram.

(A few lines after this diagram, Gould cites p.51-59 of [Bae], which is this. There you constructed a similar chain of adjunctions for PROPs rather than operads.)

Anyway, the fun thing — which tends to mess with my head a bit — is that those left adjoints $F$ look like free functors if you think semantically, but inclusions if you think syntactically! E.g. you mention the “inclusion” of symmetric operads into Lawvere theories (a.k.a. finite product operads). In order to see it as an inclusion, you really have to think of the things as theories rather than sequences of sets equipped with algebraic structure. I know you know this, because the same point is made in [Bae]! I’m just saying it because it’s an important point.

Posted by: Tom Leinster on September 23, 2019 10:22 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Thanks for the examples of “preserving shape”. The pictures really help. Yep, same shape on both sides!

Anyway, the fun thing — which tends to mess with my head a bit — is that those left adjoints $F$ look like free functors if you think semantically, but inclusions if you think syntactically!

Yes, this messed with my head for years, and one reason I wrote it up in [Bae] is that I wanted to get it straight in my mind and tell everyone.

Posted by: John Baez on September 23, 2019 10:49 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Hang on, something’s puzzling me. You wrote:

The way I see it, a symmetric operad is just a Lawvere theory with a certain property. A bit more technically: [symmetric operads] is a full subcategory of [Lawvere theories]. On the other hand, two Lawvere theories that induce the same monad on $Set$ must be isomorphic. So the same is true for symmetric operads.

This certainly sounds plausible. But it sounds equally plausible (to me) if we replace “symmetric” by “non-symmetric”. However, we know that for non-symmetric operads the conclusion is false!

So if we’re to make this argument rigorous, we’re going to have to use the symmetry in some essential way.

Perhaps the subtlety lies in the word “full”. Why exactly is [symmetric operads] a full subcategory of [Lawvere theories]?

Posted by: Tom Leinster on September 24, 2019 11:59 AM | Permalink | Reply to this

### Re: Partial Evaluations 2

Aha, apparently I’ve thought about something closely related before. It’s on the last page of an old paper of mine. In the words of Homer Simpson, who would have guessed reading and writing would pay off?

According to what I wrote there, the functor (non-symmetric operads) $\to$ (monads on $Set$) assigning to each operad its induced monad is not full. The monad induced by any operad is finitary, so we could change the codomain of that functor to (finitary monads on $Set$), which is equivalent to (Lawvere theories). Hence the functor from non-symmetric operads to Lawvere theories isn’t full.

But the surprise is that — again according to what I wrote — it’s not full for symmetric operads either. I cite a result of Weber showing that the canonical functor from (symmetric operads) to (monads on $Set$) induces an equivalence between (symmetric operads) and (analytic monads $+$ weakly cartesian maps). So that’s a non-full subcategory of (monads on $Set$).

I don’t understand why.

Posted by: Tom Leinster on September 24, 2019 12:18 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

It makes sense to me that the functor $F^\Sigma_{fp}$ from symmetric operads to Lawvere theories (equivalently, cartesian operads, or I guess what Gould calls FP-operads) is not full. When thought of as a free functor, $F^\Sigma_{fp}$ freely adjoins diagonals/contractions. Thus if $C$ and $D$ are symmetric operads, a morphism $F^\Sigma_{fp}(C) \to F^\Sigma_{fp}(D)$ could send an operation in $C$ to some contraction of an operation from $D$, hence might not arise from any morphism $C\to D$.

What surprises me is that $F^\Sigma_{fp}$ is injective on isomorphism classes. I don’t have any intuition for why that should be true, especially if it fails when we change the codomain to non-symmetric operads. Is it pseudomonic?

Posted by: Mike Shulman on September 24, 2019 10:29 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

I agree, the non-fullness is unsurprising if you think of that left adjoint as a free functor between categories of algebraic things (operads of whatever flavour). But when you think of it as an inclusion between categories of theories, what’s happening?

I confess, I’m being lazy here, in that I haven’t tried to figure it out for myself…

Posted by: Tom Leinster on September 25, 2019 10:30 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Not every “morphism of cartesian theories” between “symmetric theories” is a “morphism of symmetric theories”. A morphism of theories in the relevant sense takes each (generating) operation of the source to a derived operation in the target, obtained by composing and applying structural rules to the generating operations of the target. Since cartesian theories have more structural rules, there are more derived operations, hence more morphisms even between theories that don’t use these structural rules themselves.

Posted by: Mike Shulman on September 26, 2019 12:21 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

I was trying to see if I could guess two non-symmetric operads that aren’t isomorphic but give isomorphic monads. I wanted to do it without peeking at your paper. Here’s what I got. It seems too easy somehow, so maybe it’s wrong.

First of all, the correspondence between finitary monads and Lawvere theories lets us reduce the problem to this: find two non-isomorphic non-symmetric operads that give isomorphic Lawvere theories.

Here I’m using the fact that the functors

[Lawvere theories] $\to$ [symmetric operads] $\to$ [non-symmetric operads]

have left adjoints, which compose to give a functor

[non-symmetric operads] $\to$ [Lawvere theories]

There’s an non-symmetric operad $L$ that’s free on a binary operation $m_L$ and a nullary operation (or ‘constant’) that serves as a left unit for that binary operation. The algebras of this in $Set$ are ‘left unital magmas’.

There’s also a non-symmetric operad $R$ that’s free on a binary operation $m_R$ and a nullary operation that serves as a right unit for that binary operation. The algebras of this in $Set$ are ‘right unital magmas’.

I don’t think $L$ and $R$ are isomorphic.

But I think the Lawvere theory for left unital magmas is isomorphic to the Lawvere theory for right unital magmas: the isomorphism sends the binary operation $m_L$ of the first Lawvere theory to $m_R \circ \sigma$ in the second Lawvere theory, where $\sigma : 2 \to 2$ is the nontrivial permutation.

Indeed, I think the non-symmetric operads $L$ and $R$ have isomorphic categories of algebras in any monoidal category that happens to be braided.

Does this sound right?

Posted by: John Baez on September 24, 2019 10:44 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

I want this to be right! The only thing I don’t have is a proof that $L$ and $R$ aren’t isomorphic, and I’m too tired to try to think of one now.

It’s different example — and arguably simpler — than the one in my paper. However, it follows the same pattern, in the following sense.

The general idea of my paper is this (and read no further if you’re still trying to figure everything out for yourself). Any nonsymmetric operad $P$ has a reverse $P^{rev}$, which has the same operations and the same identity, but composition is in the opposite order. In other words, the composite

$\theta \circ (\phi_1, \ldots, \phi_n)$

in $P^{rev}$ is the composite

$\theta \circ (\phi_n, \ldots, \phi_1)$

in $P$.

It’s not too hard to see that $P$ and $P^{rev}$ induce isomorphic monads. (There are good abstract explanations of this, but again, too tired to explain.) So, it’s now just a matter of cooking up some operad that isn’t isomorphic to its reverse.

That’s where the nitty-gritty work starts. It’s a bit tricky, as for starters any symmetric operad is isomorphic to its reverse, so you need to pick an operad that can’t be given a symmetric structure.

The one I found in my paper was a certain endomorphism operad, but there must be tons of other examples, and I vaguely remember that Steve Lack found some good ones (unpublished, this was just on email). In your candidate example, the two operads you construct are also each others’ reverses. So it fits the pattern.

But if you’re a mathematician of a certain type, you’ll be satisfied without having to see a particular, explicit operad that isn’t isomorphic to its reverse… you’ll just see that such things must exist, and be glad that it was someone other than you who went through the drudgery of actually constructing one.

Posted by: Tom Leinster on September 25, 2019 10:46 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Tom wrote:

Any nonsymmetric operad $P$ has a reverse $P^{rev}$, which has the same operations and the same identity, but composition is in the opposite order.

Okay, right. Note that my $L$ and my $R$ have $R \cong L^{rev}$. I chose $L$ to be the simplest example I could find of a non-symmetric operad with $L \ncong L^{rev}$… though I wasn’t thinking very hard about the “rev” operation in general, just trying to get two nonisomorphic non-symmetric operads that give isomorphic Lawvere theories.

So I think we’re on the same wavelength here!

It’s interesting that my other guess was wrong, namely my guess that symmetric operads are a full subcategory of Lawvere theories. I now see it was a silly guess, but I’d like to get an explicit counterexample.

Posted by: John Baez on September 25, 2019 11:21 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

I must admit that I’m not entirely convinced by the claim that “cartesianness of a monad should be thought of as preserving shape”. Generally this claim is supported by giving examples of monads that are both cartesian and “preserve shape” (as Tom just did here), and perhaps also examples of monads that are not cartesian and do not “preserve shape”. But all, or nearly all, the examples of “shape-preserving” monads that are generally invoked to make this point are not just cartesian but p.r.a., and often even polynomial. And for polynomial and p.r.a. monads, there are precise things one can say about exactly what “shape” means and how they “preserve” it. So I’m tempted to think that maybe cartesianness is a necessary property of shape-preserving monads, but not a sufficient definition of them. Or can someone give an example of a cartesian monad that’s not p.r.a. and explain why it also “preserves shape” (or doesn’t)?

Posted by: Mike Shulman on September 24, 2019 10:38 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

I wouldn’t necessarily argue with that. I was simply trying to convey some intuitive idea of how a cartesian monad “feels”. To me, the difference between cartesian, p.r.a. and polynomial doesn’t feel that huge anyway. (Of course one could find arguments saying that the difference is huge, but I’m not making a precise statement.)

Posted by: Tom Leinster on September 25, 2019 10:27 PM | Permalink | Reply to this

### Re: Partial Evaluations 2

Above, I wildly guessed that the forgetful functor

$U: [Lawvere \; theories] \to [symmetric \; operads]$

$F : [symmetric \; operads] \to [Lawvere \; theories]$

that is full. Tom shot this down:

Hence the functor from non-symmetric operads to Lawvere theories isn’t full.

But the surprise is that — again according to what I wrote — it’s not full for symmetric operads either. I cite a result of Weber showing that the canonical functor from (symmetric operads) to (monads on Set) induces an equivalence between (symmetric operads) and (analytic monads + weakly cartesian maps). So that’s a non-full subcategory of (monads on Set).

I don’t understand why.

Mike gave a general argument explaining why we shouldn’t expect it to be full: $F$ freely throws in diagonals and projections, and we could have morphism $F(O) \to F(O')$ not coming from morphisms $O \to O'$ that exploit this fact. But for developing an intuition for this, it’s nice see an actual counterexample. Here’s a guess.

Let $O$ be the initial symmetric operad, the one whose algebras in any symmetric monoidal category are just objects in that category. We could call this the “symmetric operad for plain objects”. $F(O)$ is be the initial Lawvere theory, and its algebras in any category with finite products are just objects in that category. So, we could call this the “Lawvere theory for plain objects”.

Let $O'$ be the symmetric operad free on an associative binary operation; its algebras in any symmetric monoidal category are just semigroup objects in that category. We could call this the “symmetric operad for semigroups”. The algebras of $F(O')$ in any category with finite products are semigroup objects in that category. So, we could call this the “Lawvere theory for semigroups”.

Now, a morphism from $O'$ to $O$ would give a natural way to turn any object in any symmetric monoidal category into a semigroup object in that category. There’s no way to do this because if someone hands you an object $X$ in an arbitrary symmetric monoidal category, there’s no natural way to endow $X$ with an associative binary operation.

A morphism from $L(O')$ to $L(O)$, on the other hand, would give a natural way to turn any object $X$ in any category with finite products into a semigroup object in that category. And there is such a way! Namely, use $p_1 : X \times X \to X$, projection onto the first factor, as your associative binary operation!

We can check that there really is a morphism from $L(O')$ to $L(O)$ at work here: it maps the unique binary operation in $L(O')$ to $p_1$ in $L(O)$. So, $L$ is not full.

Note I didn’t really need to mention associativity here: I could have used magmas instead of semigroups. Also, I could have equally well used projection onto the second factor. Unless I’m seriously confused, there are exactly two natural ways to turn sets into magmas… and these happen to give semigroups. These semigroups have names, which only semigroup theorists know, and I will not rob them of their secrets here.

Posted by: John Baez on October 1, 2019 9:29 PM | Permalink | Reply to this

Post a New Comment