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.

January 16, 2020

Codensity Monads

Posted by Tom Leinster

Yesterday I gave a seminar at the University of California, Riverside, through the magic of Skype. It was the first time I’ve given a talk sitting down, and only the second time I’ve done it in my socks.

The talk was on codensity monads, and that link takes you to the slides. I blogged about this subject lots of times in 2012 (1, 2, 3, 4), and my then-PhD student Tom Avery blogged about it too. In a nutshell, the message is:

Whenever you meet a functor, ask what its codensity monad is.

This should probably be drilled into learning category theorists as much as better-known principles like “whenever you meet a functor, ask what adjoints it has”. But codensity monads took longer to be discovered, and are saddled with a forbidding name — should we just call them “induced monads”?

In any case, following this principle quickly leads to many riches, of which my talk was intended to give a taste.

Posted at January 16, 2020 2:36 PM UTC

TrackBack URL for this Entry:

18 Comments & 0 Trackbacks

Re: Codensity Monads

Incidentally, here’s a puzzle I posed in the talk. The inclusion of the category of fields into the category of commutative rings has a codensity monad TT, a formula for which is in the slides. What are the TT-algebras?

I don’t know the answer.

Posted by: Tom Leinster on January 16, 2020 6:33 PM | Permalink | Reply to this

Re: Codensity Monads

Wow! It’s really intriguing to see those arithmetical structures come up so naturally. At least in the case when RR has only finitely many prime ideals, then your functor R 𝔭Frac(R/𝔭)R \mapsto \prod_{\mathfrak{p}} Frac(R/\mathfrak{p}) produces a finite product of fields, whose prime ideals are in bijection with the components, which makes the monad idempotent in this case. So I guess among rings with finite spectrum, the algebras of your monad are exactly the products of fields, and those have a unique algebra structure? For a ring infinitely many prime ideals though, the product will be infinite, and I suspect that its prime ideals will be in bijection with the ultrafilters on Spec(R)Spec(R). Thus in general the algebras of your monad may also carry some topological structure? But I imagine that you’ve already thought about this.

Does this all seem reasonable? If so, it’s somewhat reminiscent of the adele ring, but I’m not competent enough to comment further on this. Anyway, I’m probably not saying anything that you don’t already know.

Posted by: Tobias Fritz on January 17, 2020 6:28 PM | Permalink | Reply to this

Re: Codensity Monads

Don’t you actually get a product of integral domains, not necessarily of fields?

Posted by: L Spice on January 17, 2020 6:44 PM | Permalink | Reply to this

Re: Codensity Monads

They’re fields: for each prime ideal 𝔭\mathfrak{p} of RR, the ring R/𝔭R/\mathfrak{p} is an integral domain, and Frac(R/𝔭)Frac(R/\mathfrak{p}) denotes its field of fractions.

Posted by: Tom Leinster on January 17, 2020 10:36 PM | Permalink | Reply to this

Re: Codensity Monads

Somehow, despite re-reading that multiple times to see what I was missing, my eyes skipped over ‘Frac’ each time. Thanks!

Posted by: L Spice on January 21, 2020 3:11 PM | Permalink | Reply to this

Re: Codensity Monads

Tobias, thank you for thinking about this!

This morning on the bus, I started thinking about this problem, and got to precisely the same point as you got to in your first paragraph… but unlike me, you wrote it down!

I agree with your partial result:

among rings with finite spectrum, the algebras of your monad are exactly the products of fields, and those have a unique algebra structure

I don’t know if there’s some intrinsic description of rings that are (finite) products of fields.

For general rings AA, I agree that a TT-algebra structure on AA very likely involves some topological structure. But I don’t know what.

It also dawned on me on the bus that I’d tried to solve this problem years ago, and not succeeded then either. I see that my paper contains (in Example 5.1) the following sentence:

On the geometric side, Spec(T G(A))Spec(T^G(A)) is the Stone-Čech compactification of the discrete space Spec(A)Spec(A).

Here AA is a commutative ring and T GT^G is the codensity monad TT we’re talking about. But frustratingly, I gave no reference for this fact, which probably means I didn’t know one. I guess I was just making a set-theoretic statement (i.e. the prime ideals of T(A)T(A) are the ultrafilters on the set of prime ideals of AA), rather than asserting a homeomorphism. The author was unclear. Anyway, this means that I agree(d) with your suspicion about what the prime ideals of T(A)T(A) are.

it’s somewhat reminiscent of the adele ring, but I’m not competent enough to comment further on this

This made me smile, because John said almost exactly the same words during my seminar, right down to the not-entirely-believable competence disclaimer :-)

Posted by: Tom Leinster on January 17, 2020 10:34 PM | Permalink | Reply to this

Re: Codensity Monads

Thank you for drawing attention to codensity monads. It’s such a ubiquitous, yet overlooked concept!

Posted by: Paolo Perrone on January 17, 2020 2:56 PM | Permalink | Reply to this

Re: Codensity Monads

Let’s see if we can polymath the first puzzle.

The question There is a monad TT on the category CRing\mathbf{CRing} of commutative rings given by

T(A)= 𝔭Spec(A)Frac(A/𝔭). T(A) = \prod_{\mathfrak{p} \in Spec(A)} Frac(A/\mathfrak{p}).

Here AA is a ring (== commutative ring henceforth), Spec(A)Spec(A) is the set of prime ideals of AA, and FracFrac means field of fractions. I won’t say explicitly here what the monad structure on TT is, but abstractly, TT is the codensity monad of the inclusion FieldCRing\mathbf{Field} \to \mathbf{CRing}.

And the question is:

What are the algebras for the monad TT?

It’s a slightly open-ended question, in that you could just grumpily reply “they are what they are”. But I think we’ll know a satisfactory answer when we see it.

Posted by: Tom Leinster on January 17, 2020 11:35 PM | Permalink | Reply to this

Re: Codensity Monads

Here are some things we already know.

First, two short things.

  • As Tobias pointed out in an earlier comment, if AA is a finite product of fields then AA has a unique TT-algebra structure. (Indeed, in that case T(A)T 2(A)T(A) \cong T^2(A) canonically.)

  • For any ring AA, the ring T(A)T(A) is reduced (has no nonzero nilpotents). Hence any subring of T(A)T(A) is also reduced. But if AA carries a TT-algebra structure then it’s isomorphic to a subring of T(A)T(A). So, any ring carrying a TT-algebra structure is reduced.

Now a longer thing.

As Tobias suspected, and as asserted in Example 5.1 of this paper, the prime ideals of T(A)T(A) are in bijection with the ultrafilters on Spec(A)Spec(A), for any ring AA. Here’s how this works.

Actually, we’ll prove that for any product B= xXk xB = \prod_{x \in X} k_x of fields, taken over an arbitrary set XX, the prime ideals of BB are in bijection with the ultrafilters on XX. I’ll use some notation: for b=(b x) xXBb = (b_x)_{x \in X} \in B, write

Z(b)={xX:b x=0}X. Z(b) = \{ x \in X : b_x = 0\} \subseteq X.

In one direction, given a prime ideal 𝔭\mathfrak{p} of BB, there’s an ultrafilter Ω 𝔭\Omega_{\mathfrak{p}} on XX defined by

Ω 𝔭={Z(b):b𝔭}. \Omega_{\mathfrak{p}} = \{Z(b): b \in \mathfrak{p}\}.

In the other direction, given an ultrafilter Ω\Omega on XX, there’s a prime ideal 𝔭 Ω\mathfrak{p}_\Omega of BB defined by

𝔭 Ω={bB:Z(b)Ω}. \mathfrak{p}_\Omega = \{ b \in B : Z(b) \in \Omega\}.

And these two processes are mutually inverse, establishing a bijection between the prime ideals of B= xXk xB = \prod_{x \in X} k_x and the ultrafilters on XX. I’ve omitted a bunch of checks here, but none of them requires special techniques.

(As a sanity check, if XX is finite then every ultrafilter is principal, so the ultrafilters on XX are in bijection with the elements of XX. And it’s easy to see that the prime ideals of a finite product of fields B=k 1××k nB = k_1 \times \cdots \times k_n are just things like {0}×k 2××k n\{0\} \times k_2 \times \cdots \times k_n — hence, one for each element of {1,,n}\{1, \ldots, n\}.)

The main thing we want ideals for is to quotient by them. So we need to ask: given an ultrafilter Ω\Omega on XX, what’s the quotient of BB by the prime ideal 𝔭 Ω\mathfrak{p}_{\Omega}, and what is its field of fractions?

The answers turn out to be simple. More or less by definition, B/𝔭 ΩB/\mathfrak{p}_\Omega is the ultraproduct ( xk x)/Ω\bigl(\prod_x k_x\bigr)/\Omega. In other words, two elements b=(b x) xXb = (b_x)_{x \in X} and c=(c x) xXc = (c_x)_{x \in X} of BB represent the same element of B/𝔭 ΩB/\mathfrak{p}_\Omega if and only if the set of indices xx such that b x=c xb_x = c_x is “large”, i.e. belongs to Ω\Omega.

The excellent fact now is that B/𝔭 ΩB/\mathfrak{p}_\Omega is already a field. (So taking its field of fractions does nothing. And every prime ideal of BB is in fact maximal.) That’s because, even though an ordinary product of fields isn’t a field, an ultraproduct of fields is a field. I explained why under the heading “Extended example” here, and it’s also an instance of Łoś’s theorem (also explained there).

So, our monad TT acts as follows on any product of fields B= xk xB = \prod_x k_x:

T( xXk x)= ultrafiltersΩonX( xXk x)/Ω. T\Bigl( \prod_{x \in X} k_x \Bigr) = \prod_{\text{ultrafilters}\ \Omega \ \text{on}\ X} \Bigl( \prod_{x \in X} k_x \Bigr) \Big/ \Omega.

Since we’re interested in algebras for our monad TT, and the definition of TT-algebra involves the composite T 2=TTT^2 = T\circ T, eventually we’re going to have to ask what T 2T^2 actually is. And we’ve already got our answer. Since T(A)T(A) is a product of fields, we can take B=T(A)B = T(A) in the description just given, which provides a more or less explicit formula for T 2(A)T^2(A). It’s this:

T 2(A)= ultrafiltersΩonSpec(A)( 𝔭Spec(A)Frac(A/𝔭))/Ω. T^2(A) = \prod_{\text{ultrafilters}\ \Omega \ \text{on}\ Spec(A)} \Bigl( \prod_{\mathfrak{p} \in Spec(A)} Frac(A/\mathfrak{p}) \Bigr) \Big/ \Omega.

Posted by: Tom Leinster on January 18, 2020 12:13 AM | Permalink | Reply to this

Re: Codensity Monads

No one’s biting, and I don’t think I’m close to an answer to my question, but here seems as good a place as any to record some further observations.

First, any product of fields — perhaps an infinite product — appears to have a natural TT-algebra structure. I showed before that for a product of fields B= xk xB = \prod_x k_x,

T(B)= ultrafiltersΩonX( xXk x)/Ω. T(B) = \prod_{\text{ultrafilters}\ \Omega \ \text{on}\ X} \Bigl( \prod_{x \in X} k_x \Bigr) \Big/ \Omega.

There’s a canonical map π B:T(B)B\pi_B: T(B) \to B: it’s projection onto the product of the principal ultrafilters on XX (noting that if Ω y\Omega_y denotes the principal ultrafilter at yXy \in X then ( xk x)/Ω y=k y(\prod_x k_x)/\Omega_y = k_y). Presumably π B\pi_B is an algebra structure on BB.

To verify that in full, we’d need to know something about the multiplication maps μ A:T 2(A)T(A)\mu_A: T^2(A) \to T(A) of the monad TT (where AA denotes a ring). Since T(A)T(A) is itself a product of fields, we’ve already constructed a homomorphism T 2(A)T(A)T^2(A) \to T(A): it’s the map π T(A)\pi_{T(A)} got by taking B=T(A)B = T(A) in the previous paragraph. And I guess that must be what μ A\mu_A is.

So, we seem to know:

  • any finite product of fields has a unique TT-algebra structure;

  • any possibly-infinite product of fields has a canonical TT-algebra structure.

Second observation: I noted before that if BB is a product of fields then every prime ideal in BB is maximal: in the jargon, BB is zero-dimensional. In particular, T(A)T(A) is zero-dimensional for any ring AA. It’s easy to see that the property of zero-dimensionality is inherited by retracts. If AA is a TT-algebra then by definition, AA is a retract of T(A)T(A). So, if a ring AA admits a TT-algebra structure then AA is zero-dimensional.

Topologically, zero-dimensionality of a ring is equivalent to Spec(A)Spec(A) being T 1T_1 (i.e. points are closed), and also equivalent to Spec(A)Spec(A) being Hausdorff. So, if AA admits a TT-algebra structure then Spec(A)Spec(A) is Hausdorff.

(The spectrum of any ring is compact, so once again we’ve got compact Hausdorff spaces floating around…)

But I couldn’t get any further than this. In particular, I don’t know whether there are any non-free TT-algebras. (I suspect there are.)

Posted by: Tom Leinster on January 23, 2020 2:29 PM | Permalink | Reply to this

Re: Codensity Monads

Dear Tom,

the category of TT-algebras has products (in fact, all limits) which are created by the forgetful functor (by general reasons). Since fields have a unique algebra structure, it follows formally that products of fields have a canonical TT-algebra structure as well (it might be non-unique).

What should also be mentioned here is the concept of a von Neumann regular ring. In the commutative case, there are lots of equivalent conditions (some of them are proven in: “Zero-dimensional commutative rings”, Lecture Notes in pure and applied mathematics 171, Chapter 1 “Background and Preliminaries on Zero-dimensional Rings” by Robert Gilmer):

For a commutative ring AA, the following are equivalent:

1) AA is von Neumann regular, i.e. for every aAa \in A there is some bAb \in A with a=abaa = aba. 2) Every (principal) ideal of AA is idempotent. 3) Every (principal) ideal of AA is a radical ideal. 4) Every element aAa \in A has a weak inverse bA b \in A (i.e. a=abaa = aba and b=babb = bab). Notice that weak inverses are unique. 5) AA is isomorphic to a subring of a product of fields closed under weak inverses. 6) AA is reduced and every prime ideal is maximal (i.e. dim(A)0\dim(A) \leq 0). 7) For every prime 𝔭\mathfrak{p} the local ring A 𝔭A_{\mathfrak{p}} is a field. 8) Every element of AA is a product of an idempotent element and a unit. 9) Every finitely generated ideal of AA is principal and generated by an idempotent element. 10) Every AA-module is flat.

The characterization with weak inverses shows that the category NRing\mathbf{NRing} of commutative von Neumann regular rings is algebraic (we add an additional unary operation ww to the theory of commutative rings and require a=aw(a)aa = a \cdot w(a) \cdot a and w(a)=w(a)aw(a)w(a) = w(a) \cdot a \cdot w(a)). On the other hand, since all local rings are fields (and hence every module is flat), we are not far from the category of fields. This is why NRing\mathbf{NRing} is one of my favorite categories which is “close enough” to the category of fields but “still algebraic”.

From the characterizations it follows immediately that T(A)T(A) is von Neumann regular (use 5) and that every commutative ring AA with a TT-algebra structure is von Neumann regular (since there is a split epimorphism T(A)AT(A) \to A) and hence is reduced and has dimension 0\leq 0. This has already been proven here in the thread, but from this perspective it is just very easy in my opinion, since no ultraproducts or ultrafilters are necessary.

Also, TT restricts to a monad TT' on NRing\mathbf{NRing}, and it is now clear that TT-algebras are the same as TT'-algebras. So let us write TT instead of TT' and work with NRing\mathbf{NRing} instead of CRing\mathbf{CRing}. I think that this is a natural setting.

Since T(A)T(A) is an infinite product and we are looking for maps out of it, it seems unlikely to me that there will be a concise description of the category of TT-algebras.

However, we may restrict ourselves to an even more basic subcategory of NRing\mathbf{NRing}, namely the category of boolean rings Bool\mathbf{Bool}. (Notice that commutative von Neumann regular rings are “not far” from being boolean since every element is idempotent up to a unit, but of course also rings with x n=xx^n = x are von Neumann regular.) I believe that every boolean TT-algebra is a product of copies of 𝔽 2\mathbb{F}_2, and that this is an equivalence between the category of TT-algebras and Set op\mathbf{Set}^{op}. By Stone duality this is equivalent to a topological statement, which I have just asked about here. Let’s see if this is true at all.

Posted by: Martin Brandenburg on February 7, 2020 11:42 AM | Permalink | Reply to this

Re: Codensity Monads

Another thing to look for when lacking a left adjoint is the pro-left adjoint. Is there anything to say relating this construction to the codensity monad?

Posted by: David Corfield on January 18, 2020 7:48 AM | Permalink | Reply to this

Re: Codensity Monads

I don’t know anything about shape theory. But for the example of G:FinSetSetG:\mathbf{FinSet}\to\mathbf{Set}, the induced functor hom(,G):Set[FinSet,Set] op\mathrm{hom}(-,G):\mathbf{Set}\to[\mathbf{FinSet},\mathbf{Set}]^\mathrm{op} factors through Pro(FinSet)\mathrm{Pro}(\mathbf{FinSet}), and I think this gives another resolution of the ultrafilter monad. Is this what you had in mind?

(Here Pro(FinSet)\mathrm{Pro}(\mathbf{FinSet}) = Stone spaces, but this seems to work generally for codensity of G:BAG:B\to A whenever the BB is small with finite limits and GG preserves them.)

Posted by: Sam Staton on January 23, 2020 9:54 AM | Permalink | Reply to this

Re: Codensity Monads

One answer is to work in DistDist, the bicategory of distributors (or profunctors). If then K:ABK:A\to B is a functor, and one forms the corresponding codensity monad in DistDist of KK as a distributor which of course has an adjoint and thus yields a codensity monad, the shape theory of KK is related to the Kleisli category of that monad.

(This is here a summary of course, and it is years since I worked with this so I may have got some things wrong!)

I agree with Tom’s comment that assuming pro-left adjoints is a step too far in general. It can be useful in specific instances but that is then less generic. This is all in the book written by Jean-Marc Cordier and myself published first in 1989, but we did not try to do anything in the fascinating cases involving anything probabilistic.

Posted by: Tim Porter on January 27, 2020 5:16 PM | Permalink | Reply to this

Re: Codensity Monads

I forgot to give the reference for the link between distributors and shape theory. That is in a paper by Dominique Bourn and Jean-Marc Cordier in the Cahiers 21 (1980) 161 - 189.

Posted by: Tim Porter on January 27, 2020 5:46 PM | Permalink | Reply to this

Re: Codensity Monads

Thanks! I didn’t have anything very definite in mind – just wondering if there’s an interesting range of ways to make up for lack of left adjoint. And a hope some day to have time to see what’s going on with pyknotic sets/condensed sets.

Posted by: David Corfield on January 23, 2020 1:49 PM | Permalink | Reply to this

Re: Codensity Monads

I guess I’ve already sufficiently emphasized that codensity monads are an absolutely canonical concept of category theory, and I don’t need to bang that drum any further.

While I can’t claim to have digested the concept of pro-left adjoint, I note that the definition does involve a somewhat arbitrary choice, namely, of a class of limits. Specifically, it involves the pro-completion of a category, i.e. the free completion under the class of cofiltered limits. (And the definition of pro-left adjoint is only made for those functors that preserve finite limits.) One can envisage making similar definitions for other classes of limit.

So while I wouldn’t necessarily disagree with the proposition there’s an “interesting range of ways to make up for lack of left adjoint”, I would argue that among those ways, codensity monads are canonical in a sense that pro-left adjoints are not.

Posted by: Tom Leinster on January 23, 2020 2:13 PM | Permalink | Reply to this

Re: Codensity Monads

Codensity monads are fascinating. Let me share two remarks and ask a question.

  1. A codensity monad can be considered as a special case of a pushforward of a monad along a functor: if S is a monad and G is a functor, then the right Kan extension Ran G(GS)Ran_{G}(G\circ S) is always a monad. The proof this fact is just slightly extended proof of the fact that a codensity monad is a monad. A codensity monad is then just a pushfoward of the identity monad.

  2. However, there is a bit more general perspective: as we all know, a monad on a category CC just a monoid in the monoidal category of endofunctors of CC, let us call it call it Endof(C)Endof(C). If G:CDG\colon C\to D is a functor and DD is complete, then R:Endof(C)Endof(D)R\colon Endof(C)\to Endof(D) given by R(S)=Ran G(GS)R(S)=Ran_{G}(G\circ S) is a monoidal functor. Since RR is monoidal, it maps monoids in Endof(C)Endof(C) to monoids in Endof(D)Endof(D) and this is the pushforward.

Question: Is the monoidal perspective in the remark 2. actually developed in some papers?

Posted by: Gejza Jenča on January 25, 2020 11:00 PM | Permalink | Reply to this

Post a New Comment