Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

September 20, 2012

Where Do Monads Come From?

Posted by Tom Leinster

If you know some category theory, you probably know that every functor with a left adjoint induces a monad. But much less well known — and undeservedly so — is that you don’t need your functor to have an adjoint in order for it to induce a monad! Even a functor without a left adjoint induces a monad, just as long as certain limits exist.

This is called the codensity monad of the functor. I’ve just arXived a paper about them (and ultrafilters, which I won’t get to today). This is the first of a short series of posts explaining what’s in my paper.

Today I’ll explain what a codensity monad is.

Here’s the grammar of it: a functor G:BAG: \mathbf{B} \to \mathbf{A} may or may not have a codensity monad. If it does, it’s a monad on A\mathbf{A}, and I’ll call it T GT^G. In the event that GG has a left adjoint, FF, the codensity monad does exist, and it’s simply GFG F.

I’ll state the definition of codensity monad in four ways, using varying amounts of categorical vocabulary.

 

1. The slickest definition: the codensity monad of GG is the right Kan extension of GG along itself. (This may or may not exist.) The monad structure comes from the universal property of Kan extensions.

 

2. Slightly more explicitly, the codensity monad T GT^G can be defined as an end: for AAA \in \mathbf{A},

T G(A)= B[A(A,GB),GB]. T^G(A) = \int_B [\mathbf{A}(A, G B), G B].

Here [A(A,GB),GB][\mathbf{A}(A, G B), G B] is a power in A\mathbf{A}: that is, it’s the product of lots of copies of the object GBG B, one for each element of the set A(A,GB)\mathbf{A}(A, G B). The end might or might not exist.

 

3. If you’re not comfortable with ends, maybe you’ll prefer the same formula expressed as a limit. Let AAA \in \mathbf{A}. Let A/GA/G be the comma category whose objects are maps f:AGBf\colon A \to G B (or more exactly, pairs (B,f)(B, f) where BBB \in \mathbf{B} and fA(A,GB)f \in \mathbf{A}(A, G B)). There’s a functor A/GAA/G \to \mathbf{A} sending this object to GBG B, and T G(A)T^G(A) is defined to be its limit (if it exists).

 

4. Here’s a fourth and final way to say it. For this, let’s assume that B\mathbf{B} is small and A\mathbf{A} has small limits. Then, à la Kan, the functor GG induces an adjunction

Hom(,G):A[B,Set] op:Hom(,G) Hom(-, G) : \mathbf{A} \stackrel{\longleftarrow}{\rightarrow} [\mathbf{B}, \mathbf{Set}]^{op} : Hom(-, G)

where I’m calling both functors Hom(,G)Hom(-, G), though they’re not the same. The left adjoint Hom(,G):A[B,Set] opHom(-, G): \mathbf{A} \to [\mathbf{B}, Set]^{op} is defined by (Hom(A,G))(B)=A(A,GB)(Hom(A, G))(B) = \mathbf{A}(A, G B). I’ll skip the description of the right adjoint — see the paper if you want to know. Of course, the right adjoint is determined by the fact that it’s a right adjoint: explicitly,

Hom A(A,Hom(Y,G))Hom [B,Set](Y,Hom(A,G)) Hom_{\mathbf{A}}(A, Hom(Y, G)) \cong Hom_{[\mathbf{B}, \mathbf{Set}]}(Y, Hom(A, G))

whenever AAA \in \mathbf{A} and Y[B,Set]Y \in [\mathbf{B}, \mathbf{Set}]. Anyway, being an adjunction, it induces a monad, and this is the codensity monad of GG.

 

Example  Suppose GG has a left adjoint, FF. Using any of the descriptions above, you can show that the codensity monad T GT^G is just the ordinary monad GFG F (Proposition 6.1 of my paper, but known for donkeys’ years).

 

Example  Every set SS has a monoid of endomorphisms End(S)\mathbf{End}(S), and an action of a monoid MM on SS can be described as a map MEnd(S)M \to \mathbf{End}(S) of monoids. Modules over rings, representations of groups, algebras for operads, etc., can all be described in a similar way.

What seems less well known is that algebras for monads can also be described in this way. Let AA be an object of a category A\mathbf{A}. Under mild hypotheses, AA has an endomorphism monad End(A)\mathbf{End}(A), whose crucial feature is that for any other monad SS on A\mathbf{A}, an SS-algebra structure on AA can be described as a map SEnd(A)S \to \mathbf{End}(A) of monads. It is, in fact, the codensity monad of the functor 1A\mathbf{1} \to \mathbf{A} that picks out the single object AA.

Explicitly, this monad End(A)\mathbf{End}(A) sends an object XX of A\mathbf{A} to the power [A(X,A),A][\mathbf{A}(X, A), A]. (That’s a special case of the end or limit formula above.) Why is it the case that an SS-algebra structure on AA amounts to a monad map SEnd(a)S \to \mathbf{End}(a)? Keep reading to find out.

 

Example  Here’s something a bit more substantial. Take the category Ring\mathbf{Ring} of commutative rings, its full subcategory Field\mathbf{Field}, and the inclusion functor G:FieldRingG\colon \mathbf{Field} \hookrightarrow \mathbf{Ring}.

There’s probably no canonical way of turning a ring into a field, and as a matter of fact, GG doesn’t have a left adjoint. Why not? Here’s one of many possible arguments. The category Ring\mathbf{Ring} has an initial object, \mathbb{Z}, and any left adjoint would send \mathbb{Z} to an initial object of Field\mathbf{Field}. But Field\mathbf{Field} has no initial object, since there are no homomorphisms between fields of different characteristics.

So, we don’t get an induced monad on Ring\mathbf{Ring} by the standard monad-from-adjunction method.

But we do get a codensity monad, T GT^G. It does its best to turn rings into fields. What it actually does is turn a ring into a product of fields: for a ring AA,

T G(A)= pSpec(A)Frac(A/p) T^G(A) = \prod_{p \in Spec(A)} Frac(A/p)

where Spec(A)Spec(A) is the set of prime ideals of AA and Frac(A/p)Frac(A/p) is the field of fractions of the quotient ring A/pA/p.

You might wonder whether the unit map AT G(A)A \to T^G(A) embeds our original ring AA into a product of fields (in other words, whether it’s injective). An obvious necessary condition is that AA contains no nilpotent elements other than zero. In fact, some basic commutative algebra implies that this is also a sufficient condition (Example 5.1 of my paper).

For instance,

T G()=×(/2)×(/3)×(/5)× T^G(\mathbb{Z}) = \mathbb{Q} \times (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/3\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z}) \times \cdots

which is the product of one copy each of the prime fields. (It contains \mathbb{Z} as a subring.) Also, for n1n \geq 1,

T G(/n)= primes p|n/p. T^G(\mathbb{Z}/n\mathbb{Z}) = \prod_{primes  p | n} \mathbb{Z}/p\mathbb{Z}.

You can rewrite this as

T G(/n)=/rad(n) T^G(\mathbb{Z}/n\mathbb{Z}) = \mathbb{Z}/rad(n)\mathbb{Z}

where rad(n)rad(n) is the radical of nn. If you’ve been reading about the ABC conjecture recently, you’ll have met the radical: it’s the product of the distinct prime factors of nn.

 

I want to finish by convincing you that codensity monads really do deserve to be thought of as substitutes for monads induced by adjunctions, usable in situations where no adjoint exists.

The first example above was one piece of evidence for this point of view: that if GG does have a left adjoint, then the codensity monad is the same thing as the monad induced by the adjunction. So, the two constructions agree where they’re both defined, but codensity monads are defined more often.

Here’s some stronger evidence that we’re doing the categorically right thing. Take, as before, a functor G:BAG\colon \mathbf{B} \to \mathbf{A}, and suppose that the codensity monad T GT^G exists. Then it’s a theorem that given any monad SS on A\mathbf{A}, there’s a natural one-to-one correspondence between:

  • maps of monads ST GS \to T^G, and
  • functors BAlg(S)\mathbf{B} \to \mathbf{Alg}(S) over A\mathbf{A}.

Here “over A\mathbf{A}” refers to the fact that both B\mathbf{B} and Alg(S)\mathbf{Alg}(S) come equipped with functors into A\mathbf{A} (namely, GG and the forgetful functor); the functor BAlg(S)\mathbf{B} \to \mathbf{Alg}(S) is required to make the obvious triangle commute. If you want a proof, you can find this as Proposition 6.2 of my paper.

(Back in the example of endomorphism monads, maybe you wondered why maps SEnd(A)S \to \mathbf{End}(A) were the same thing as SS-algebra structures on AA. It’s because of the result just mentioned: just take G:1AG\colon \mathbf{1} \to \mathbf{A} to be the functor picking out the object AA.)

So: the process of constructing codensity monads is adjoint to the process of constructing the category of algebras for a monad. This can be put precisely in a couple of ways, which you can find in Section 6 of my paper. I’ll just mention one.

Fix a category A\mathbf{A}. Not every functor into A\mathbf{A} has a codensity monad, and certainly not every functor into A\mathbf{A} is monadic. Write:

  • CAT/A\mathbf{CAT}/\mathbf{A} for the slice category of CAT\mathbf{CAT} over A\mathbf{A}
  • (CAT/A) CM(\mathbf{CAT}/\mathbf{A})_{CM} for the full subcategory consisting of those functors that have a codensity monad
  • (CAT/A) mndc(\mathbf{CAT}/\mathbf{A})_{mndc} for the full subcategory of monadic functors.

These are successively smaller, since any monadic functor has a left adjoint and therefore (by our very first example) a codensity monad. So we have

(CAT/A) mndc  (CAT/A) CM. (\mathbf{CAT}/\mathbf{A})_{mndc}   \subseteq  (\mathbf{CAT}/\mathbf{A})_{CM}.

The theorem now is that it’s a reflective subcategory. That is, the inclusion functor (CAT/A) mndc(CAT/A) CM(\mathbf{CAT}/\mathbf{A})_{mndc} \hookrightarrow (\mathbf{CAT}/\mathbf{A})_{CM} has a left adjoint. The adjoint takes a functor G:BAG\colon \mathbf{B} \to \mathbf{A} and turns it into the forgetful functor Alg(T G)A\mathbf{Alg}(T^G) \to \mathbf{A}.

In other words, the canonical way to force a functor to be monadic is to first take its codensity monad, then form the corresponding monadic functor.

In future installments: ultrafilters, ultraproducts, and: what could it sensibly mean for a vector space to be compact?

Posted at September 20, 2012 11:55 AM UTC

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

36 Comments & 0 Trackbacks

Re: Where Do Monads Come From?

This has actually been somewhat common knowledge for a bit now amongst people who are interested in both category theory and Haskell. There we have a Monad type class:

    class Monad m where
      pure  :: forall a. a -> m a
      -- often more convenient for programming than join :: m (m a) -> m a
      (>>=) :: forall a b. m a -> (a -> m b) -> m b

that identifies monads over the category Hask, which has Haskell types as objects and Haskell functions as arrows, and is enriched in itself (or, something along those lines). Quantifiers enforce (di)naturality conditions, so one can define:

    newtype Codensity f a = Codensity (forall r. (a -> f r) -> f r)

Which is the above end (and always exists). And it was known that a Monad definition could be given without knowing anything about f (it is necessarily Hask-valued, but we don’t care what kind of weird category with Hask’s objects we have to make up to make f actually a functor).

I have, of course, never seen anything on the more rigorous category theory side about this, so I was never sure how flukey it was (the above is kind of like saying that for all Set-valued functors that come from a category with Set’s objects but not necessarily its morphisms, the above end exists and is a monad on Set). It’s interesting to see it generalized.

We also of course have (made up syntax for ease of presentation):

    newtype Density f a = Density (exists s. f s * (f s -> a))

for the dual, which always has an implementation of a Comonad class.

(Also, this fact was known even earlier for a continuation passing style monad:

    newtype ContT f r a = Con ((a -> f r) -> f r)

f is irrelevant to the Monad definition for ContT f r.)

Posted by: Dan Doel on September 20, 2012 2:54 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

I didn’t know any of that! Thanks.

I hope I didn’t give the impression that codensity monads are my own invention. They’re most definitely not. I did a pretty exhaustive/ing literature search for my paper, and there’s a history of (co)density on page 4. From what I gather, codensity monads were first written about by Anders Kock (1966), and they’d been discovered independently at about the same time by Myles Tierney, who later wrote about them with H(arry?) Appelgate.

Posted by: Tom Leinster on September 20, 2012 3:32 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Out of curiousity: who was the first person to write about “endomorphism monads” specifically (i.e., as classifiers of algebra structures)?

I “discovered” endomorphism monads while still a lowly graduate student, and I still have a soft spot for them because they were the very first “new” thing I ever discovered (where “new” here means “something my advisor didn’t know about”).

Even then, I figured I might not be the first person to think about this, but I never found them in the literature. (I wouldn’t have guessed to look for stuff on “codensity monads”.)

Posted by: Charles Rezk on September 20, 2012 4:00 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Interesting question. I don’t actually know, but I’m going to guess Anders Kock. This is partly because he did write about endomorphism monads:

Anders Kock, On double dualization monads. Mathematica Scandinavica 27 (1970), 151–165.

It’s also partly because, as one of the originators of the notion of codensity monad, he’d have been well-placed to do it.

However, what Kock did in that paper was not quite the same as what I describe above: it’s in a slightly different categorical context.

It wouldn’t surprise me if someone like Linton or Manes or Lawvere or … had written something about endomorphism monads in the early days, but I don’t know a reference.

Posted by: Tom Leinster on September 20, 2012 4:15 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Also incidentally, a surprising number of monads of interest to us (in programming) arise either this way, or as the right Kan extension of two functors, and is related to implementation of those types in continuation passing style.

For instance, if we define ‘Endo a = a -> a’, then Codensity Endo is (isomorphic to) the free monoid monad; lists:

    List a = Codensity Endo a = forall r. (a -> r -> r) -> r -> r

    nil :: List a
    nil = \f z -> z

    cons :: a -> List a -> List a
    cons x xs = \f z -> f x (xs f z)

    append :: List a -> List a -> List a
    append xs ys = \f z -> xs f (ys f z)

    foldr :: (a -> r -> r) -> r -> List a -> r
    foldr f z xs = xs f z

    ...

This is often known as the Church encoding of lists (or Boehm-Berarducci if you prefer). If instead of Codensity Endo we choose Ran Id Endo, we get forall r. (a -> r) -> r -> r which is isomorphic to 1 + a. A fellow put together a package for these a while back.

Posted by: Dan Doel on September 20, 2012 6:05 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Good to know!

The earliest references I’d found were Ross Street in 72 and Dubuc in 74.

Posted by: Edward Kmett on September 20, 2012 6:31 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

I’m not sure I know those. Is Street (72) “The Formal Theory of Monads”? And which paper of Dubuc?

Posted by: Tom Leinster on September 20, 2012 6:38 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

people who are interested in both category theory and Haskell. There we have a Monad type class:

[…]

I have, of course, never seen anything on the more rigorous category theory side about this,

Just recently I had felt like digging out and recording the canonical references that neatly discuss monads as used in computer science (in particular in Haskell but not only there! :-) in abstract mathematical form … only to discover that no such reference seems to exist!?

We ended up discussing this a bit here on the nnForum and then an nnLab entry monad in computer science came into existence, which states at least some basics.

But somebody out there should really feel motivated to write a good comprehensive and mathematical account of monads in computer science. It’s too important to always gloss over.

If somebody knows that this has already happened and the link to it is just too well hidden for Google to find it, I’d be most grateful for a pointer.

Posted by: Urs Schreiber on September 20, 2012 6:50 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

This is all off the top of my head, but….

The person who is typically first credited with using monads in computer science was Eugenio Moggi. You presumably found his stuff, since you’re using his coined “Notions of Computation” phrase in your link.

Moggi’s work, as I understand it, is to use monads in denotational semantics. Roughly, you have a typed functional programming language, and want to interpret the types as sets. But many languages have effects that make the functions not merely the set of all mathematical functions between the two types. Instead, one can construct a monad that models all the effects inherent in the language, and interpret the language into the Kleisli category, rather than Set. Or something along those lines.

However, the above is all about the semantics of programming languages. For use of monads within a language, I believe the typical citation is Philip Wadler. His earliest paper on the subject is from 1992, which fits the folklore that he was pulling from Moggi’s 1991 paper.

The best way to understand Wadler’s work, I think, is that having effects able to appear everywhere in our programs is undesirable. Working with just mathematical functions is often easier and less error prone. So, instead of interpreting the entire language into something with all the effects we’d ever want, we embed languages with effects as types within our host language. Monads specify the algebra of these embedded languages, and Moggi’s work leads to a nice notation for programming in languages with effects specified in this way. Thus we can program with effects locally where necessary/convenient while still having an overall language with ‘pure functions’, where reasoning is easier.

That’s the gist of it. There’s lots of stuff since then, of course, but perhaps that’s along the lines of what you’re looking for?

Posted by: Dan Doel on September 20, 2012 8:10 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Actually Ralf Hinze has a relevant category-theoretic write-up precisely about codensity (and more generally kan extensions) in programming. It proves in particular that any monad is a codensity for some functor. Link.

Posted by: Arnaud Spiwack on September 21, 2012 10:53 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

Thanks, Arnaud.

In the category-theoretic context, the statement that any monad is a codensity monad is the combination of two basic facts. (I know you weren’t saying it wasn’t basic; I just want to explain for anyone else reading.)

The first fact is that every monad is induced by some adjunction. The second is that when you have an adjunction, the monad it induces is the same as the codensity monad of the right adjoint (the first “example” in my post). Put the two facts together, and you conclude that every monad is a codensity monad.

Posted by: Tom Leinster on September 21, 2012 12:48 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

I’m glad to see codensity monads getting some press! I haven’t read your paper yet, but reading your blog post made me want to mention a couple of related things….

The endomorphism monad of an object is also used to good effect in 2-category theory. For instance, as soon as you know what a pseudo morphism between algebras for a 2-monad are, you know what a pseudo algebra for a 2-monad TT is: it’s a pseudo morphism of 2-monads from TT to the endomorphism 2-monad of some object.

This observation is also what makes colimits of monads useful: since an algebra for a monad is just a monad map out of it, the algebras for a colimit of monads can be described in terms of algebras for the monads involved in the colimit.

Posted by: Mike Shulman on September 20, 2012 3:14 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Tom, you seem to have not noticed the following. :-)

There is a section on Codensity Monads (section 2.6) in

J.-M. Cordier and T. Porter, 2008, Shape Theory, categorical methods
of approximation, Dover (reprint of earlier 1989 edition).

(The earlier edition was published by Ellis Horwood.)

The reason for considering them was that they give a very neat description of the categorical shape theory of a functor. This was noted by Frei (1976). The Kleisli category of the codensity monad of a functor is the categorical shape category of the functor.

There is also, in the source above, discussion of this situation and its relation with the bicategory of distributeurs / profunctors (section 4.2). This was taken from a paper by Bourn and Cordier (Cahiers, 1980).

I was also a bit surprised not to see reference to the paper:

D. Gildenhuys and J. Kennison, Equational completions, model induced
triples and pro-objects , J. Pure Applied Alg., 4, (1971), 317–346.

as this relates the ultrafilter stuff and profinite stuff in a neat way, but it may be off to the side of what you are doing, but have a look.

The way in which all the geometric theories (in the naive sense) of shape relate to the current interest in Ax-Grothendieck and even the abc-conjecture, is a mystery to me, but whether or not the similarities are mere coincidences or a sign of something `deep’ I have no idea.

Posted by: Tim Porter on September 21, 2012 7:37 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

Hi Tim. Thanks for the references. Actually, I don’t think I’ve ever laid eyes on your book, although of course I’ve known of it for many years. Our library doesn’t have it, unfortunately, but I just added it to my ever-expanding Amazon basket.

Actually, I think the first time I saw mention of codensity monads was in a paper on shape theory by Michael Batanin.

I hadn’t heard of the Gildenhuys and Kennison paper. I’ll look that up; thanks again.

Posted by: Tom Leinster on September 21, 2012 12:53 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

For what it’s worth, the Gildenhuys and Kennison is volume 1 (issue 4), not volume 4.

Posted by: Tom Leinster on September 22, 2012 12:30 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

Thanks for the correction since it must be an error in a bibtex file I am using and that needs correcting!

Posted by: Tim Porter on September 22, 2012 7:34 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

This all looks very interesting, and let’s hope it provides a clue for our question over here.

I haven’t seen this codensity monad construction before. Could I ask about some basics? How was the terminology chosen? Presumably we’re starting from the notion of density, as in the rationals are dense in the reals. Do we move straight to the idea of something being codense relative to something else? Or was it rather that from density, people developed the notion of density comonad and then dualised everything in sight?

Posted by: David Corfield on September 22, 2012 11:11 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

Most of what I know about the history is on page 4 of my paper. First, John Isbell defined what it meant for a full subcategory to be dense or codense — except that he used “left/right adequate” rather than dense/codense. Then lots of stuff happened at about the same time:

  • Friedrich Ulmer introduced the word “dense” (for functors, not just subcategory inclusions).
  • Anders Kock (knowing of Ulmer’s work) introduced codensity monads and density comonads, under that name.
  • Myles Tierney, independently, was also working on codensity monads and density comonads, under the name of model-induced (co)triples.

Other names have been used, e.g. “algebraic completion” and “equational completion” mean more or less the same thing.

Mathematically, yes, I believe the terminology is inspired by examples such as the rationals in the reals. Roughly, a subcategory B\mathbf{B} of a category A\mathbf{A} is codense if every object of A\mathbf{A} is a limit of objects of B\mathbf{B}, just as a subspace BB of a space AA is dense if every element of AA is a limit of elements of BB.

The two dual notions have always been written about together, from the beginning. However, it’s much easier to come up with examples of dense subcategories than codense subcategories. E.g. A\mathbf{A} is always dense in [A op,Set][\mathbf{A}^{op}, \mathbf{Set}], the category of finite-dimensional vector spaces is dense in the category of vector spaces, the category of finite sets is dense in the category of sets, etc.

The other point is that a functor is codense if and only if its codensity monad is isomorphic to the identity. So the codensity monad of a functor measures its failure to be codense. I guess that’s what Kock had in mind when he coined the term.

Posted by: Tom Leinster on September 22, 2012 1:43 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Thanks. It looks like the nnLab could do with some work in this area.

Here are some examples from Isbell’s Adequate Subcategories to include:

In a category of algebras with nn-ary operations, the free algebra on nn generators is left adequate. In compact spaces, the 2-cell is right adequate. In sets, a single point is left adequate. The duals of these examples are less neat. For sets, a countably infinite set is right adequate if and only if no measurable cardinals exist. For compact spaces, no set of them is left adequate. The 1-cell is left adequate for Peano spaces, and for all products of Peano spaces up to the first weakly inaccessible cardinal. No nontrivial instance is found of a single algebra being right adequate for a large class, excepting the few which come from the examples mentioned by duality.

So let’s see. Right adequate means codense, so the inclusion of the 2-cell in the category of compact (did Hausdorff go without saying back then?) spaces. So the codensity monad had better be the identity. What, so there are no other maps from Maps(X, 2-cell) to the 2-cell than evaluation at a point in X?

Posted by: David Corfield on September 23, 2012 12:23 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Yes, I believe that’s what he meant, though I haven’t read that part of the paper. I agree that “Hausdorff” must be understood, otherwise I think the result would be false.

Let me state (my interpretation of) Isbell’s result a bit more precisely. Write CptHff\mathbf{CptHff} for the category of compact Hausdorff spaces. Write B 2B^2 for the “2-cell” (which I take to mean the closed 2-ball). Since Isbell dealt only with full subcategories, he’s saying that the full subcategory of CptHff\mathbf{CptHff} consisting of the single object B 2B^2 is codense.

This can be rephrased without mentioning codensity. Let XX be a compact Hausdorff space. Both CptHff(X,B 2)\mathbf{CptHff}(X, B^2) and B 2B^2 carry natural actions by the endomorphism monoid End(B 2)End(B^2). For the inclusion to be codense means that any End(B 2)End(B^2)-equivariant map

CptHff(X,B 2)B 2 \mathbf{CptHff}(X, B^2) \to B^2

is uniquely of the form ff(x)f \mapsto f(x), for some xXx \in X.

This is very similar in spirit to the last result mentioned in my new post.

Posted by: Tom Leinster on September 23, 2012 4:00 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Very nice, Tom.

The forgetful functor from fields to rings (though my memory is not too good) has a multiadjoint, the multiinitial object being the set of prime fields.

What is the codensity monad for a multiadjunction?

Then there are polyadjoints, where there is a groupoid of candidates for each universal object.

Yves Diers worked on this in the 1980s, followed by François Lamarche and me.

Paul Taylor

Posted by: Paul Taylor on September 23, 2012 10:01 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

Thanks, Paul. I confess that I’ve never learned about multiadjoints. Let’s see. From the prime field example, I suppose it must be the case that a set S\mathbf{S} of objects of a category C\mathbf{C} is multiinitial if for all XCX \in \mathbf{C}, the disjoint union

SSHom(S,X) \sum_{S \in \mathbf{S}} Hom(S, X)

has exactly one element. From that, I should be able to figure out the definitions of multiadjoint and multilimit. Am I on the right track?

Posted by: Tom Leinster on September 23, 2012 4:06 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

I confess that my memory of this subject is not very good after twenty years, but from what I recall, one of the ways of looking at multiadjunctions was by considering initial objects of connected components of presheaves viewed as diagrams.

However, my preference was to use factorisation systems. For example, to get the free field on a ring relative to another field, you would factorise the given homomorphism from the ring to the field, obtaining its image as a subfield.

I would say that my question is not a big deal as a research point, but would be a useful exercise for any graduate student who is interested in exploring the ideas in your original post.

The polyadjoint case would be more interesting.

Posted by: Paul Taylor on September 24, 2012 5:57 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Here’s a neat connection that just occurred to me. The notions of adjunction, monad, left and right Kan extension, (co)density, and (co)density (co)monads can be formulated internally to any 2-category (although in general, internal Kan extensions might not exist). Unsurprisingly, right Kan extensions in a 2-category KK are the same as left Kan extensions in K coK^{co} (where we reverse the 2-cells), and hence codensity monads in KK are the same as density comonads in K coK^{co}.

However, there’s another way to dualize a 2-category, by reversing the 1-cells; this one is called K opK^{op}. A right Kan extension in K opK^{op} is called a right Kan lifting in KK. Left and right Kan liftings don’t necessarily exist in CatCat, but they always exist when the morphism in question has a suitable adjoint. Just as the codensity monad of a right adjoint always (exists and) is the monad induced by the adjunction in the familiar way, the “co-op-density monad” of a left adjoint always exists and is also the familiar monad induced by the adjunction. Thus, in particular, we could say that a fully faithful left adjoint functor is “co-op-dense”.

Moreover, in the bicategory ProfProf of categories and profunctors, right Kan liftings do always exist — and additionally, the “representable” profunctor induced by any functor is a left adjoint. So for two different reasons, any functor induces a co-op-density monad in ProfProf. A monad in ProfProf on a category AA simply consists of another category AA' with the same objects as AA and an identity-on-objects functor AAA\to A', and for the co-op-density monad of a functor f:ABf:A\to B we have A(a 1,a 2)=B(f(a 1),f(a 2))A'(a_1,a_2) = B(f(a_1),f(a_2)). In particular, ff is co-op-dense in ProfProf exactly when it is fully faithful.

Posted by: Mike Shulman on September 23, 2012 6:37 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Again this is closely related to the form of categorical shape theory studied by Hilton and Deleanu. In many ways this is not that deep, but had (for the time) surprising connections with a lot of other areas.

Posted by: Tim Porter on September 24, 2012 10:00 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

What is there to say category theoretically about the inclusion of Field\mathbf{Field} into Ring\mathbf{Ring}? Is it a case of moving from nice objects to a nice category?

Is it important that the definition of field requires coherent logic rather than equational logic?

Tom tells us about ultraproducts in the paper, is there a reason why fields are so commonly used here, e.g., to produce a pseudo-finite field?

Paul points out the existence of a multi-adjoint and a multi-initial family. These don’t seem common constructions. Are there any comparable cases?

Is there something about Ring\mathbf{Ring} that explains why it has this interesting kind of subcategory?

Posted by: David Corfield on September 25, 2012 11:51 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

Not a complete answer, but you might be interested in section 4.C of Adamek and Rosicky’s book Locally presentable and accessible categories, where they discuss “locally multipresentable categories”. Recalling that

  • an accessible category is equivalently:

    • a full subcategory of a presheaf category that’s closed under κ\kappa-filtered colimits for some κ\kappa
    • the category of models of a sketch
  • a locally presentable category is equivalently:

    • a reflective full subcategory of a presheaf category that’s closed under κ\kappa-filtered colimits for some κ\kappa
    • the category of models of a limit sketch
    • an accessible category with all small limits
    • an accessible category with all small colimits

we can “break in half” the difference between the two and define

  • a locally multipresentable category to be equivalently:
    • a multireflective full subcategory of a presheaf category that’s closed under κ\kappa-filtered colimits for some κ\kappa
    • the category of models of a limit and coproduct sketch
    • an accessible category with all small connected limits
    • an accessible category with all small multicolimits

and

  • a weakly locally presentable category to be equivalently:
    • a weakly reflective full subcategory of a presheaf category that’s closed under κ\kappa-filtered colimits for some κ\kappa
    • the category of models of a limit and epi sketch
    • an accessible category with all small products
    • an accessible category with all small weak colimits

In particular, the fact that the definition of fields requires coherent logic is very relevant, because that means you can’t define them with a limit sketch.

Posted by: Mike Shulman on September 26, 2012 1:45 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

That deserves being nnLab-ified. So I’ve copied and pasted to sketch. The page needs some sorting out now.

Posted by: David Corfield on September 27, 2012 8:57 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

The theory of multiadjoints was developed extensively by Yves Diers, so a mathscinet search on his name will give you the references.

Posted by: Tim Porter on September 26, 2012 5:03 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

The example with Field->Ring reminds me of the field with one element
http://en.wikipedia.org/wiki/Field_with_one_element
Is there some connection?

Posted by: Werner Thumann on December 13, 2012 10:11 AM | Permalink | Reply to this

Re: Where Do Monads Come From?

I don’t know — I don’t think I’m seeing what you’re seeing. In what way did it remind you of this?

Posted by: Tom Leinster on December 13, 2012 12:21 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

In the sense, that the field with one element could be an initial object in the “right” category of fields, and so Field->Ring might have an adjoint. So the codensity monad you describe could be a descendant of the unknown adjunction above. This is maybe too vague and mysterious, as is the field with one element, sorry for that. ;)

Posted by: Werner Thumann on December 13, 2012 1:41 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Ah, I see. That’s an interesting idea. There are some readers here who know a lot more about the field with one element than I do (not hard), and I hope some of them will come along and pick this up.

Posted by: Tom Leinster on December 13, 2012 1:47 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Well, the obvious questions are: Is the codensity monad T, which you described in the example, monadic? (Beck’s Theorem might give an answer to this?). If yes, then consider the category of T-algebras. Does it have an initial object? This object could be a candidate for the one element field.

(As I’m writing this, I’m getting aware of the fact that I’m talking well beyond my competence. I apologize if I’m talking nonsense.)

Posted by: Werner Thumann on December 13, 2012 2:32 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

As you suspected, some of this doesn’t quite make sense. In particular, it doesn’t make sense to ask whether a monad is monadic. Here’s a brief explanation.

Any monad TT on a category A\mathbf{A} gives rise to a new category, called the category of algebras of TT and written as either Alg(T)\mathbf{Alg}(T) or A T\mathbf{A}^T. It also gives rise to a functor U T:Alg(T)AU^T\colon \mathbf{Alg}(T) \to \mathbf{A}.

Typical example: if A\mathbf{A} is the category of sets and TT is the free group monad then Alg(T)\mathbf{Alg}(T) is the category of groups and U T:Alg(T)=GrpA=SetU^T\colon \mathbf{Alg}(T) = \mathbf{Grp} \to \mathbf{A} = \mathbf{Set} is the usual forgetful functor.

Not every functor is of the form U TU^T for some monad TT. Those that are are called monadic. (So it’s a functor, not a monad, that can be monadic or not.) The monadicity theorem, also called Beck’s theorem, provides a useful way of recognizing monadic functors.

Anyway:

consider the category of T-algebras.

Here TT is the codensity monad of the inclusion FieldRingField \hookrightarrow Ring (where RingRing means commutative rings). The formula for TT that I gave in the post was

T(A)= pSpec(A)Frac(A/p) T(A) = \prod_{p \in Spec(A)} Frac(A/p)

for rings AA. I didn’t describe the unit and multiplication of the monad, but the unit at least is fairly obvious: its component at a ring AA is

η A:AT(A)= pSpec(A)Frac(A/p) \eta_A \colon A \to T(A) = \prod_{p \in Spec(A)} Frac(A/p)

whose pp-component is the obvious homomorphism AFrac(A/p)A \to Frac(A/p).

I don’t know what TT-algebras look like. Maybe they’re something well-known: can anyone figure this out?

Explicitly, a TT-algebra is a ring AA together with a homomorphism

α:T(A)= pSpec(A)Frac(A/p)A \alpha\colon T(A) = \prod_{p \in Spec(A)} Frac(A/p) \to A

satisfying a couple of axioms. One of them says that αη A\alpha \circ \eta_A is the identity, which implies that η A\eta_A is injective, which implies in turn that AA is reduced (i.e. has no nonzero nilpotents). The other says that α\alpha interacts well with the multiplication of the monad.

I know that, for example, \mathbb{Z} admits no TT-algebra structure. Indeed, there is no homomorphism α:T()\alpha\colon T(\mathbb{Z}) \to \mathbb{Z} at all. For call a ring AA “good” if there exists aAa \in A such that 4a=24 a = 2. In the post, I observed that

T()=×(/2)×(/3)×(/5)× T(\mathbb{Z}) = \mathbb{Q} \times (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/3\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z}) \times \cdots

from which it follows that T()T(\mathbb{Z}) is good. But \mathbb{Z} is not good, and it is clear that there can be no homomorphism from a good ring to a non-good ring.

Does it have an initial object?

Yes, for very general reasons. The initial object is in fact the ring

T()=×(/2)×(/3)×(/5)× T(\mathbb{Z}) = \mathbb{Q} \times (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/3\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z}) \times \cdots

above. (The TT-algebra structure on T()T(\mathbb{Z}) is the multiplication map T 2()T()T^2(\mathbb{Z}) \to T(\mathbb{Z}). I haven’t thought about what this map actually is.)

That seems a bit ordinary to be a good candidate for the field with one element. What do you think?

Posted by: Tom Leinster on December 13, 2012 6:26 PM | Permalink | Reply to this

Re: Where Do Monads Come From?

Hi Tom,

yeah, sorry, shortly after I submitted the post I realized that “monadic monad” is nonsense. ^^
Well, what do you mean by “ordinary”. I also can’t see the T-algebra structure on T(Z), it’s probably complicated. But you have to think of T(Z) lying in the category of T-algebras, not in the category of rings. This way T(Z) is probably not so ordinary as it suggests when viewed as a ring in Rings.
Anyway, the category of fields embeds into the category of T-algebras (right/wrong?), and maybe one should re-interpret the properties in
http://en.wikipedia.org/wiki/Field_with_one_element
for this bigger category and check whether the are true for T(Z). Does this even make sense? ;)

Posted by: Werner Thumann on December 14, 2012 2:22 PM | Permalink | Reply to this

Post a New Comment