## May 24, 2007

### Cohomology and Computation (Week 24)

#### Posted by John Baez

In the 1950s, Cartan, Eilenberg, Mac Lane and others systematically studied the cohomology of many different algebraic gadgets — groups, associative algebras, Lie algebras, and so on. It was later realized that underlying all these different cohomology theories there’s a marvelous unifying idea: the bar construction. In this week’s seminar on Cohomology and Computation, we began trying to understand what makes the bar construction tick:

• Week 24 (May 17) - The bar construction. Why do adjoint functors give simplicial objects? First, $\Delta_{alg}$ is the free monoidal category on a monoid object — or "the walking monoid", for short. Second, adjoint functors give certain monoids, called "monads".

Last week’s notes are here; next week’s notes are here.

Why is $\Delta_{alg}$, the free monoidal category on a monoid, called the “walking monoid”?

This is one of Jim Dolan’s jokes. Supppose some guy has really big bushy eyebrows, so that when you see him walking down the street you first notice his eyebrows and only later realize there’s a person attached. Then you might call him a "walking pair of eyebrows". Such a guy is basically just a minimal life support system for his eyebrows!

In math, we see the same phenomenon in things like “the free group on 2 elements”. This is a group whose sole purpose in life is to have 2 elements. To pick out 2 elements in any group $G$, we just need a homomorphism from the free group on 2 elements to $G$. Similarly, the monoidal category $\Delta_{alg}$ is a monoidal category whose sole purpose in life is to contain a monoid object.

I explained some variants of this idea back in week173 and week174 — namely, the walking equivalence, the walking adjoint equivalence, the walking adjunction, and the walking ambidextrous adjunction. Aaron Lauda discusses the walking adjunction and the eyebrows joke on page 20 of his paper Frobenius algebras and ambidextrous adjunctions. For more of the history of this joke, and how Jim sometimes feels uncomfortable when I tell his jokes in public — whoops! — read the interview by Bruce Bartlett.

Posted at May 24, 2007 12:43 AM UTC

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

### Re: the Walking Monoid

There’s another nice fact about $\Delta$ which fits with the picture of “the walking monoid”, but one degree up in categorical dimension.

First, $\Delta$, being the category of finite ordinals and order-preserving maps, is a 2-category: the 2-cells are instances $f \leq g$ of the pointwise order between order-preserving maps. In fact, $\Delta$ with its ordinal sum $+$ forms a monoidal 2-category.

Next, taking into account the 2-category structure, there are some adjoint relationships between the 1-cells. Let $u: 0 \to 1$ and $m: 2 \to 1$ be the unique maps to the terminal object 1; these of course are the unit and multiplication on the monoid 1. Then, there is a string of adjunctions

$(1 + u: 1 \to 2) \dashv (m: 2 \to 1) \dashv (u + 1: 1 \to 2).$

This is very easy to see; for instance, the counit 2-cell $m(u + 1) \leq id_1$ is an equality, and the unit 2-cell $id_2 \leq (u + 1)m$ is also clear, because $(u + 1)m$ is the function taking both elements of 2 = {0, 1} to the maximal element 1.

Monads for which the multiplication is left adjoint to the unit are called Kock-Zöberlein monads; they were first pointed out in 1972 by Anders Kock. They often arise as “cocompletion monads” of one kind of another. A typical example: consider the ‘finite coproduct completion’ of a category $C$, sometimes denoted $Fam(C)$. The objects of $Fam(C)$ are finite tuples $(c_1, ..., c_n)$ of objects of $C$, and a morphism

$(c_1, ..., c_n) \to (d_1, ..., d_m)$

consists of a function $f: [n] \to [m]$ (where [n] = {1, …, n}) together with an n-tuple of morphisms $g_j: c_j \to d_{f(j)}$ of $C$, composed in the obvious way. [If you know about categorical wreath products, Fam(C) can also be expressed as a wreath product $Fin \int C$.] Finite coproducts in $Fam(C)$ are formed by concatenating tuples, and it is not hard to convince oneself that the obvious inclusion $i: C \to Fam(C)$ has the universal property:

Any functor $F: C \to D$ to a category with finite coproducts $D$ can be extended along $i$ to a coproduct-preserving functor $Fam(C) \to D$, uniquely so up to canonical isomorphism.

Now, if $C$ already has finite coproducts, then the counit, i.e., the coproduct-preserving functor $s = sum: Fam(C) \to C$ which extends the identity on $C$, is left adjoint to the inclusion $i: C \to Fam(C)$, i.e., the unit! The counit of $s \dashv i$ is an isomorphism, and the unit, applied to an object $(c_1, ..., c_n)$ in Fam(C), is just the tuple of canonical injections into the coproduct $\sum_i c_i$ in $C$:

$(c_1, ..., c_n) \to (\sum_i c_i).$

In cases like this, where the counit of a bi-adjunction is left adjoint to the unit in this manner, we say that the bi-adjunction is KZ or Kock-Zöberlein.

Here is a more precise definition: a bi-adjunction $(F: C \to B) \dashv (G: B \to C)$ between bicategories, with unit $u: 1_C \to G F$ and counit $c: F G \to 1_B$ and triangulators

$s: (G c)(u G) \stackrel{\sim}{\to} 1_G$

$t: 1_F \stackrel{\sim}{\to} (c F)(F u),$

is said to Kock-Zöberlein if $s$ is the counit of an adjunction $G c \dashv u G$ (equivalently, if $t$ is the unit of an adjunction $F u \dashv c F$; proving that equivalence is a fun exercise in bicategorical algebra). Similarly, there is a notion of Kock-Zöberlein (pseudo)monad $(M, m, u)$, where there is a string of adjunctions

$M u \dashv m \dashv u M.$

If you’ve followed me this far, you will have no trouble guessing the punch line:

Theorem (Kock): The monoidal 2-category $\Delta$ is the “walking Kock-Zöberlein monoid.”

See the penultimate paper referenced here for details.

I think this result is pretty widely known within the categorical community, but a quick Google search on Kock-Zöberlein or KZ monads didn’t garner a huge number of hits, so I think the result probably bears repeating here. I haven’t thought much about what implications this result would have with respect to the bar construction.

Posted by: Todd Trimble on May 26, 2007 1:04 AM | Permalink | Reply to this

### Re: the Walking Monoid

In my previous post, I should have added (I think it’s pretty cool, anyway) that in $\Delta$, if you look at the $n+1$ injections

$d_0 \leq ...\leq d_n: [n] \to [n+1]$

and the $n$ surjections

$s_1 \leq ... \leq s_n: [n+1] \to [n]$

then what you get is a big long string of adjunctions

$d_0 \dashv s_1 \dashv d_1 \dashv s_2 \dashv ... \dashv s_n \dashv d_n$

as a result of the KZ property.

Posted by: Todd Trimble on May 26, 2007 1:41 AM | Permalink | Reply to this

### Re: the Walking Monoid

That is cool. Thanks for explaining all this stuff about Kock-Zöberlein monads. I need to lock myself in the cellar and ponder them sometime.

I occasionally feel I understand them — thanks mainly to your attempts to explain them, but also to the prevalence of ‘weakly idempotent’ pseudomonads on $Cat$ having the flavor of ‘cocompletion processes’: I’ve seen lots of those in my time!

But, the relation of all this to the monoidal 2-category version of $\Delta$ seems mysterious to me, and phrases like “$s$ is the counit of an adjunction $G c \dashv u G$” make my mind freeze like a deer in the headlights.

I don’t think there’s any more you can do to help: I just need to do some calculations to see for myself how this stuff works!

if you look at the $n+1$ injections

$d_0 \leq ...\leq d_n: [n] \to [n+1]$

and the $n$ surjections

$s_1 \leq ... \leq s_n: [n+1] \to [n]$

then what you get is a big long string of adjunctions

$d_0 \dashv s_1 \dashv d_1 \dashv s_2 \dashv ... \dashv s_n \dashv d_n$

as a result of the KZ property.

Cool! I vaguely seem to remember results that say “any sufficiently long string of adjunctions has to be sort of degenerate in some way.” I’ve looked for such results, but I don’t remember what I found. This example constrains what theorems I could possibly be imagining.

Do you know any results along these lines?

Posted by: John Baez on May 26, 2007 2:52 AM | Permalink | Reply to this

I vaguely seem to remember results that say “any sufficiently long string of adjunctions has to be sort of degenerate in some way.” I’ve looked for such results, but I don’t remember what I found. This example constrains what theorems I could possibly be imagining. Do you know any results along these lines?

There’s an absolutely remarkable theorem of this flavor due to Richard Wood and Bob Rosebrugh; I don’t know if it’s close to what you were trying to remember. I think it goes something like this:

$y: C \to Set^{C^{op}}.$

As we all know, $y$ preserves all limits which happen to exist in $C$. But the condition that $y$ is a right adjoint: that turns out to be a very strong cocompleteness condition on $C$. In that case, people sometimes say that $C$ is total (don’t know who made up that term).

Presheaf categories (and Grothendieck toposes generally) are total in this sense. In the presheaf case, the left adjoint $m$ to the Yoneda embedding

$y: Set^{C^{op}} \to Set^{(Set^{C^{op}})^{op}}$

is (somewhat interestingly)

$Set^{y_C^{op}}: Set^{(Set^{C^{op}})^{op}} \to Set^{C^{op}}.$

(As an aside, the condition that the Yoneda embedding on $C$ have a left exact left adjoint is actually rather close to the condition that $C$ is a Grothendieck topos!).

Now, in the presheaf case $Set^{C^{op}}$, the left adjoint to Yoneda has itself a left adjoint

$L_y: Set^{C^{op}} \to Set^{(Set^{C^{op}})^{op}}$ given essentially by taking left Kan extension along a Yoneda embedding. (I’m not sure about this, but the existence of such a string of left adjoints which starts from the Yoneda embedding $y_C$ and proceeds leftwards:

$L \dashv m \dashv y_C$

might be equivalent to the condition that $C$ is a presheaf topos.)

Can the left Kan extension

$L_y: Set^{C^{op}} \to Set^{(Set^{C^{op}})^{op}}$

have a left adjoint? It can (but the noose is gradually tightening). For example, if $C$ is a small sup-lattice, then $y: C \to Set^{C^{op}}$ has a left adjoint $\xi: Set^{C^{op}} \to C$, and the left adjoint to $L_y$ would be a left Kan extension $L_{\xi}$ along $\xi$ (more or less).

“Okay, smarty-pants, can this left adjoint $L_{\xi}$ have a left adjoint?” Well, yes it can, but now we’re really getting to the end of the rope: if the sup-lattice $C$ in the previous paragraph were the terminal category 1, then $\xi: Set \to 1$ has a left adjoint $i: 1 \to Set$, namely the initial object (and the left adjoint to $L_{\xi}$ would then be a left Kan extension $L_i$). That’s the absolute limit to how far we can go.

So, then, the Rosebrugh-Wood results are:

• Theorem: There exists a string of adjoints $j \dashv k \dashv l \dashv m \dashv y_C,$ where $y_C$ is the Yoneda embedding of $C$, if and only if $C$ is equivalent to $Set$.
• Corollary: There is no such adjoint string $i \dashv j \dashv k \dashv l \dashv m \dashv y_C.$

I see this result is downloadable here. (I saw Richard Wood give a seminar on this theorem at Macquarie; it was impressive.)

Posted by: Todd Trimble on May 26, 2007 4:32 AM | Permalink | Reply to this

### Re: Cohomology and Computation (Week 24)

There was one other thing about the bar construction which I wanted to mention, since John told me that his course is ending soon and he might not get around to mentioning it himself.

As John said, the bar construction is a wonderful gadget which can be used to compute cohomology for general algebraic theories (groups, algebras, Lie algebras, …), as well as do other things like constructing classifying bundles. Given any monad $M$ and an $M$-algebra $X$, the bar construction is an efficient machine for constructing a ‘free resolution’ of $X$, to which one can then apply the machinery of derived functors to compute the cohomology of $X$.

What John gave in his course was a very nice introduction, with lots of diagrams and pictures, which gave the precise conceptual details underlying the bar construction: a simplicial object whose $n$-dimensional component is a free algebra $M M^n X$ over the monad $M$, with face operators which look like:


...      mMX
-->     mX
MmX     -->     a
... MMMX --> MMX     MX --> X
-->     -->
MMa     Ma



What I want to talk about here is the conceptual sense in which the bar construction is a resolution of $X$, i.e., the acyclicity of the bar construction as a simplicial object. I also want to talk about the sense in which the bar construction on $X$ is a universal $M$-free resolution of $X$.

In order for this note to make sense, I’ll first have to recall some of what John said. A monad $M$ is a monoid in a monoidal category, and the story begins by considering the string diagram calculus for monoids in monoidal categories. As John showed in pictures, the string diagrams, modulo the equivalence relation imposed by the monoid equations, look exactly like pictures (cospans) of order-preserving functions between finite ordinals. This was summarized in the slogan, “the category $\Delta$ is the walking monoid”, i.e., $\Delta$ equipped with its terminal object [1] is precisely the initial strict monoidal category equipped with a monoid.

Or, we could say that $\Delta^{op}$ is the “walking comonoid”. It’s nice to know by the way that $\Delta^{op}$ is equivalent to the category of finite intervals (i.e., finite totally ordered sets with a top and bottom, and maps which preserve the order and top and bottom). This is something you can see very well if you stare at John’s pictures of planar 2d cobordisms, which are planar thickenings of string diagrams for monoids, and then let your attention flicker over to the complement (of different shading) and read it upside-down as a 2d cobordism. This idea and the planar 2d cobordisms also figure prominently in Aaron Lauda’s Frobenius algebras and ambidextrous adjunctions.

With that, the bar construction is easy to construct. Let $(M, m: M M \to M, u: 1 \to M)$ be a monad on a category $E$. One has an adjunction

$(F: E \to E^M) \dashv (U: E^M \to E)$

where $E^M$ is the Eilenberg-Moore category of $M$-algebras. This in turn gives a comonad $F U$ acting on $M$-algebras, that is to say, a comonoid in a monoidal category of endofunctors. Because $\Delta^{op}$ is the walking comonoid, there is a unique monoidal functor (the bar construction)

$Bar_M: \Delta^{op} \to [E^M, E^M]$

which sends the comonoid [1] in $\Delta^{op}$ to $F U$. By postcomposing this by the evaluation functor at an $M$-algebra $X$, one gets a simplicial $M$-algebra

$B_M(X): \Delta^{op} \to E^M$

and this is the bar construction applied to $X$. This description appears in Mac Lane’s Categories for the Working Mathematician, which is where I first learned about it (see section VII.6 in the second edition).

As I say, the important point here is that this object is acyclic, in a very strong sense of the word which I need to explain. Part of the philosophy here is that the bar construction is a piece of pure equational logic, and we will correspondingly treat its acyclicity purely algebraically, not as a property involving an existential quantifier but as a structure, called a ‘resolution’ for lack of anything better. Roughly speaking, a resolution structure on a simplicial object $Y$ with augmentation,


... Y[2] --> Y[1] --> Y[0],
-->



is a contracting homotopy which realizes a homotopy equivalence between $Y$ and the constant simplicial object at $Y[0]$, and moreover a contracting homotopy with some very good properties.

Recall that contracting homotopy $h$ on a simplicial object $Y: \Delta^{op} \to E$ is given by a collection of maps

$h_n: Y[n] \to Y[n+1]$

satisfying some equations. Observe also that the map $[n] \mapsto [n+1]$ is the object part of a comonad $[1] + (-): \Delta^{op} \to \Delta^{op}$. Here is the key notion:

• A resolution is a simplicial object $Y$ together with a right-sided coalgebra structure $h: Y \to Y \circ ([1] + (-))$ over the comonad $[1] + (-)$.

This will require some unpacking, but let’s first see how this works in the case of the bar resolution. Since $Bar_M$ preserves the monoidal and comonoid structures, we have a commutative diagram


Delta^{op} -----> [E^M, E^M]
|       Bar_M      |
|                  |
| [1]+( )          | FUo( )
V                  V
Delta^{op} -----> [E^M, E^M]
Bar_M



and we augment this diagram with another:


Delta^{op} -----> [E^M, E^M] ---> [E^M, E]
|       Bar_M       |    U o( )   |
|                   |             |
|[1]+( )      FUo( )|       UFo( )|
V                   V             V
Delta^{op} -----> [E^M, E^M] ---->[E^M, E]
Bar_M            U o( )



The bar resolution is the horizontal composite $UBar_M$. Notice there is is a canonical right $F U$-coalgebra structure on $U$, given by the coaction $u U: U \to U F U = M U$. This gives a right action of the comonad $[1]+ (-)$ on $UBar_M$, as we see from the diagram, therefore we obtain a resolution structure with components

$h_n = u M^n: M^n \to M^{n+1}.$

Now, what exactly is a resolution structure? I’d like to tease that out.

A first trivial observation is that a right-sided coalgebra for the comonad $[1]+(-)$ is the same as an ordinary (left-sided) coalgebra for the comonad on simplicial objects

$E^{[1]+(-)}: E^{\Delta^{op}} \to E^{\Delta^{op}}$

given by pulling back along $[1] + (-)$. I’ll call this pullback comonad $P$, for short.

Second, to make things easier (or perhaps more recognizable), let’s pretend for a moment that $E = Set$. The pullback comonad $P$ then has a left adjoint, given by left Kan extension along $[1]+ ( )$. What is that left Kan extension? On the representable objects, it takes the affine simplex $hom(-, [n])$ to $hom(-, [n+1])$, i.e, it takes the cone of the affine simplex. This cone construction extends to all simplicial sets (by left Kan extension). I’d like to call the Kan extension the ‘cone functor’ on simplicial sets, although we should be careful here: we are not coning a space or simplicial set to a point, because that operation does not preserve disjoint sums (therefore isn’t a left adjoint). What the left Kan extension actually does is cone a space to its set of path components, i.e., it takes the disjoint union of all the cones over all the path components. But as I say, I’m still going to call this left Kan extension the ‘cone functor’, and denote it $C$.

Now, we are in a general situation where we have a comonad $P$ with a left adjoint $C$. There is a general piece of abstract nonsense here, dating back to the original 1965 paper by Eilenberg and Moore, which says that the comonad structure on $P$ corresponds precisely to a monad structure on $C$, in such a way that the category of $P$-coalgebras is naturally equivalent to the category of $C$-algebras. So, now we want to know: what is a $C$-algebra?

Personally, I find it more intuitive to think about it topologically. There is an analogous cone monad $C: Top \to Top$ acting on topological spaces, where $C X$ is defined to be the pushout of the diagram

$[0, 1] \times X \stackrel{inj_0}{\leftarrow} X \stackrel{q}{\to} \pi_0(X)$

where $inj_0(x) := (0, x)$ and $q$ is the canonical projection. A map $a: C X \to X$ is thus given by a pair of maps

$h: [0, 1] \times X \to X$ $i: \pi_0(X) \to X$

where $i$ picks out a basepoint for each path component, and (by the pushout commutativity) $h$ contracts each path component to its basepoint. This already means the pair $(h, i)$ is explicit witness to the fact that $X$ is acyclic (is homotopy equivalent to its discrete space of path components), but there’s more since we have not yet accounted for the monad structure on $C$.

The monad structure on $C$ is induced from a monoid structure on $[0, 1]$, and we will take the monoid multiplication on $[0, 1]$ to be the ‘tropical’ multiplication $(x, y) \mapsto min(x, y)$. An algebra with respect to the monad $C$ is given by a pair $(h, i)$ such that the homotopy $h$ behaves as a ‘flow’ with respect to tropical multiplication: the following equations are satisfied:

$h(s, h(t, x)) = h(min(s, t), x)$ $h(1, x) = x$ $h(0, x) = iq(x).$

[A note to experts: the topos of simplicial sets classifies the theory of intervals; in particular, geometric realization $Set^{\Delta^{op}} \to Top$ is the model which takes the generic interval to the interval [0, 1]. The generic interval carries an intrinsic monoid operation ‘min’, and geometric realization thus maps it over to the monoid $([0, 1], min)$; this is why we took the multiplication on the unit interval to be ‘tropical’.]

The cone monad on topological spaces is again left adjoint to a comonad $P$ on topological spaces, where $P X$ is the pullback of the diagram

$X^{[0, 1]} \stackrel{eval_0}{\to} X \stackrel{id}{\leftarrow} |X|$

where $|X|$ is the underlying set of $X$ equipped with the discrete topology, included in $X$ by the identity function, and a $C$-algebra structure is again equivalent to a $P$-coalgebra structure.

• In summary: a resolution = a $P$-coalgebra = a $C$-algebra = a simplicial object $Y$ equipped with a ‘homotopy flow’ which contracts $Y$ to the discrete space of its path components $Y[0]$. In other words, a resolution is a particularly nice kind of contracting homotopy witnessing acyclicity of $Y$.

Now for the main theorem:

• The bar resolution $UBar_M$ is a universal $M$-algebra resolution for the monad $M$.

This may require some amplification. As above, let $B_M(X)$ denote the result of applying the bar resolution functor to a particular $M$-algebra $X$, i.e., let $B_M(X)$ be the composite

$\Delta^{op} \stackrel{Bar_M}{\to} [E^M, E^M] \stackrel{eval_X}{\to} E^M \stackrel{U}{\to} X.$

Let $Y$ be any $M$-algebra resolution, i.e., a simplicial $M$-algebra $\Delta^{op} \to E^M$ equipped with a $P$-coalgebra structure on the underlying simplicial object

$U Y: \Delta^{op} \to E.$

There is a forgetful functor from the category of $M$-algebra resolutions to $M$-algebras, which remembers only the augmentation part $Y[0]$.

The universal property of $B_M(X)$ is that given an $M$-algebra resolution $Y$ and an $M$-algebra map $X \to Y[0]$, there is a unique extension to a map of $M$-algebra resolutions, $B_M(X) \to Y$. This is the familiar ‘acyclic models theorem’:

• Theorem (Acyclic Models): The bar resolution $B_M(-)$ is left adjoint to the forgetful functor from $M$-algebra resolutions to $M$-algebras.

Sketch of proof: The unique simplicial extension $f: B_M(X) \to Y$ of $f_0: X \to Y[0]$ is constructed by induction on dimension. The map $f_{n+1}: M^{n+1} X \to Y$ is the unique $M$-algebra map which extends the composite

$M^n X \stackrel{f_n}{\to} Y[n] \stackrel{h_n}{\to} Y[n+1].$

It is immediate that $f$ preserves the contracting homotopies; all that remains to be checked is that $f$ is a simplicial map. This is based on a simple inductive argument; details may be found in my notes.

Posted by: Todd Trimble on May 31, 2007 8:55 PM | Permalink | Reply to this

### Re: Cohomology and Computation (Week 24)

Shall we promote this elaboration to a guest post?

(By the way, it seems you forgot to add the hyperlink to your notes. If you send me or John or David an email with the address, we can insert it into your comment.)

Posted by: urs on May 31, 2007 9:02 PM | Permalink | Reply to this

### Re: Cohomology and Computation (Week 24)

I’d be honored – thanks very much, Urs.

I’ll send you the link in a moment.

Posted by: Todd Trimble on May 31, 2007 9:20 PM | Permalink | Reply to this

### Re: Cohomology and Computation (Week 24)

I’ll send you the link in a moment.

Okay. Fixed.

Posted by: urs on May 31, 2007 9:32 PM | Permalink | Reply to this

### Re: Cohomology and Computation (Week 24)

Earlier I wrote:

This already means the pair (h,i) is explicit witness to the fact that X is acyclic (is homotopy equivalent to its discrete space of path components)

which is not quite right since we don’t yet have the equation $h(1, x) = x$. But in the scheme of things, this is a minor error.
Posted by: Todd Trimble on May 31, 2007 9:18 PM | Permalink | Reply to this
Read the post Cohomology and Computation (Week 25)
Weblog: The n-Category Café