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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3188

36 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

Around about 39 minutes into his talk Who cares about pyknosis? your Edinburgh colleague, Clark Barwise, speaks about the ultrafilter monad as a codensity monad.

Posted by: David Corfield on March 6, 2020 10:49 AM | 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

Re: Codensity Monads

Here’s what I think is an interesting example of a codensity monad closely related to C C^\infty-rings. I’m not yet sure how to describe the monad explicitly, and perhaps someone here may be able to help out.

Let MfdMfd be the category of smooth manifolds and smooth maps. Assuming second countability in the definition of manifold, MfdMfd is essentially small. Now let U:Mfd opSetU : Mfd^{\mathrm{op}} \to Set be the hom-functor Mfd(,)Mfd(-,\mathbb{R}). What is its codensity monad?

In lieu of having an answer, let me ask something a little easier. It seems intuitively clear that the category of algebras of the codensity monad will have a forgetful functor to C C^\infty-rings, because the maximal finitary submonad is presumably exactly the monad of C C^\infty-rings. Is there a general theorem of which this (putative) observation would be an instance?

Posted by: Tobias Fritz on April 4, 2020 2:31 AM | Permalink | Reply to this

Re: Codensity Monads

I should have provided a bit of context. My idea is that the algebras of that codensity monad will have a lot in common with C C^\infty-rings, and in particular could possibly be used in the context of differential geometry. But unlike C C^\infty-rings, they would not privilege finitary operations over arbitrary one. Also, the abstract definition seems to be more elegant, flexible, and easier to motivate.

Posted by: Tobias Fritz on April 4, 2020 2:36 AM | Permalink | Reply to this

Re: Codensity Monads

I like this line of thought, as I agree that C C^\infty-rings have a codensity monad feel to them. I don’t have an answer to your questions, but let me try thinking out loud a little bit.

You start with the hom-functor

C =Mfd(,):Mfd opSet, C^\infty = Mfd(-, \mathbb{R}): Mfd^{op} \to Set,

and you’re interested in its codensity monad, which is a monad on SetSet. Call it TT. Then more or less by definition, for a set AA,

T(A)= XMfd[C (X) A,C (X)]. T(A) = \int_{X \in Mfd} [C^\infty(X)^A, C^\infty(X)].

So an element of T(A)T(A) is a consistent method of choosing, for each manifold XX and AA-indexed family of smooth functions on XX, a single smooth function on XX.

What are some of the elements of T(A)T(A)?

  • Any element aAa \in A gives rise to an element of T(A)T(A): it’s the “method” that sends an AA-indexed family of functions to its aath member. That’s how the unit map η A:AT(A)\eta_A: A \to T(A) works.

  • More generally, any formal real polynomial in elements of AA gives rise to an element of T(A)T(A), because C (X)C^\infty(X) is an \mathbb{R}-algebra for any manifold XX. In other words, given an AA-indexed family of smooth functions on XX, combine them according to the polynomial.

  • More still, any smooth function ϕ: n\phi: \mathbb{R}^n \to \mathbb{R} (not necessarily a polynomial!), together with an nn-tuple (a 1,,a n)(a_1, \ldots, a_n) of elements of AA, gives rise to an element of T(A)T(A). Indeed, given a manifold XX and an AA-indexed family (f a) aA(f_a)_{a \in A} of smooth functions on XX, we get a new smooth function ϕ(f a 1,,f a n) \phi \circ (f_{a_1}, \ldots, f_{a_n}) on XX.

So yes, I agree that the monad for C C^\infty-rings should be a submonad of your codensity monad TT. (And I guess I now understand why you’re asking the question!) Hence there’s a forgetful functor from TT-algebras to C C^\infty-rings.

Presumably, though, T(A)T(A) is somewhat bigger than the free C C^\infty-ring on AA, for a general set AA. As you suggest, it should contain some infinitary operations too. Can you give me an example of one?

Posted by: Tom Leinster on April 5, 2020 4:04 PM | Permalink | Reply to this

Re: Codensity Monads

Right! Thank you for spelling it out like that, it’s exactly what I’ve had in mind and what motivated the question.

The underlying philosophy is that I’d like to think of a monad on SetSet as an algebraic theory (with possibly infinitary operations), where the elements of T(A)T(A) are interpreted as operations of arity AA. Thinking of codensity monads like this, one can pose and answer questions like “Given this formal mathematical construction, what is the most general algebraic structure that it carries?” For example, consider the fundamental group functor π 1:Top *Set\pi_1 : Top_* \to Set. Could it be that it actually has more algebraic structure than just being a group? Ignoring the potential size issue here, I think that the codensity monad TT of π 1\pi_1 gives the answer: for every based space XX, the set π 1(X)\pi_1(X) is a TT-algebra. So this codensity monad TT is arguably the free group monad.

Likewise for the hom-functor Mfd(,):Mfd opSetMfd(-,\mathbb{R}) : Mfd^\mathrm{op} \to Set: its codensity monad gives a description of the complete algebraic structure carried by every ring of smooth functions C (X)C^\infty(X).

Has this perspective on codensity monads already been developed somewhere?

As you suggest, it should contain some infinitary operations too. Can you give me an example of one?

Actually no…! I’ve been trying for a while and failed, and I’m starting to suspect:

Conjecture: The codensity monad of Mfd(,)Mfd(-,\mathbb{R}) on SetSet is finitary. More precisely, it is isomorphic to the monad whose algebras are C C^\infty-rings.

Let me sketch which construction of infinitary operations I’ve tried and why it has failed. Let (g n) nN(g_n)_{n \in \N} be any family of smooth functions \mathbb{R} \to \mathbb{R} such that ng n (k) <\sum_n \|g_n^{(k)}\|_\infty \lt \infty for all kk. For example, let gC ()g \in C^\infty(\mathbb{R}) be any compactly supported smooth function and g n:=2 ngg_n := 2^{-n} g. Then for any sequence of smooth functions (f n) nN(f_n)_{n \in \N} on any manifold XX, I was hoping to get a new smooth function given by ng nf n.\sum_n g_n \circ f_n. Naively one might think that the given assumptions on the (g n)(g_n), or perhaps some variant thereof, would guarantee that this sum converges and is again a smooth function. But this does not seem to be the case: if the (f n)(f_n) oscillate faster and faster as nn \to \infty, then already the first derivatives f n(g nf n)f'_n \cdot (g'_n \circ f_n) may not be summable. The Weierstrass function is a famous example of this sort of thing.

Posted by: Tobias Fritz on April 5, 2020 5:17 PM | Permalink | Reply to this

Re: Codensity Monads

As it turns out, there indeed are embarrassingly simple examples of genuinely infinitary operations in TT. These easily disprove my apparently very naive conjecture from the comment above. The following example is based on a math.SE answer by Greg Martin.

Let ψ:\psi : \mathbb{R} \to \mathbb{R} any smooth function which is non-zero precisely on infinitely many disjoint intervals. In other words, suppose that ψ\psi has infinitely many bumps. Enumerate these bumps by a positive integer nn. For example, the intervals may be of the form (2n,2n+1)(2n,2n+1), meaning that ψ\psi vanishes precisely on the closed intervals [2n+1,2n+2][2n+1,2n+2] and (,0](-\infty,0].

Now let XX be any manifold and let (f i) i(f_i)_{i \in \mathbb{N}} be a sequence of smooth functions on XX. Define a new smooth function gg on XX by using the value of f 0f_0 as a “control variable”:

1) For xXx \in X such that ψ(f 0(x))=0\psi(f_0(x)) = 0, put g(x)0g(x) \coloneqq 0.

2) Otherwise if f 0(x)f_0(x) is in the nn-th bump of ψ\psi, then put g(x)ψ(f 0(x))f n(x)g(x) \coloneqq \psi(f_0(x)) \cdot f_n(x).

It’s not difficult to see that gg is again a smooth function on XX; the only case in which care needs to be taken is when f 0(x)f_0(x) is just at the boundary of a bump of ψ\psi, but at such a point also all derivatives of gg vanish since those of ψ\psi do. Thus gg is indeed smooth, and clearly depends on all countably many f if_i. Finally since gg only depends on the values of the f if_i, the relevant naturality condition holds as well. We have thus defined an element of T()T(\mathbb{N}) which is not contained in the maximal finitary submonad of TT.


So what should we make of TT-algebras then? Are they of any interest at all as models of generalized smooth spaces? I don’t have good answers to these questions yet and would be interested in hearing others’ thoughts. Here’s what I think at the moment.

The existence of genuinely infinitary operations suggests that it will be difficult to find a concrete description of T(A)T(A) for an arbitrary set AA. But just as for any monad, we can still define particular TT-algebras in terms of generators and relations. For example, there will be a TT-algebra generated by a single element ff subject to the relation f 2=0f^2 = 0. As a proof of concept that one can actually work with TT-algebras in practice, I’d hope to have a concrete description of at least the underlying set (or underlying ring) of this TT-algebra, and I’d expect it to coincide with the ring of dual numbers [f]/(f 2)\mathbb{R}[f]/(f^2). But I don’t know how to go about this yet. An answer to the following question may help:

Let MM be a monad on SetSet, and let M finM_fin be its maximal finitary submonad. Then there is an obvious forgetful functor from MM-algebras to M finM_fin-algebras. Is this functor an equivalence on finitely generated (or even finitely presented) algebras?

This feels morally true and may not be difficult to prove. Assuming that it holds, it would follow that the finitely generated (presented) TT-algebras coincide with the finitely generated (presented) C C^\infty-rings. And perhaps it could then be argued that TT-algebras are the more natural concept in the general case.

Posted by: Tobias Fritz on April 8, 2020 5:18 PM | Permalink | Reply to this

Re: Codensity Monads

Likewise for the hom-functor Mfd(,):Mfd opSetMfd(-,\mathbb{R}) : Mfd^\mathrm{op} \to Set: its codensity monad gives a description of the complete algebraic structure carried by every ring of smooth functions C (X)C^\infty(X).

Has this perspective on codensity monads already been developed somewhere?

To me this sounds like the theorem of Dubuc stated on slide 7 of my talk. In the case at hand, it says that among all maps in the slice category CAT/SetCAT/Set from C :Mfd opSetC^\infty: Mfd^{op} \to Set to a monadic set-valued functor, the initial one has as its codomain the forgetful functor Set TSetSet^T \to Set. Here TT is the codensity monad of C C^\infty and Set TSet^T is its category of algebras.

There’s more on this kind of thing in Section 6 of my paper on codensity monads.

Posted by: Tom Leinster on April 5, 2020 5:37 PM | Permalink | Reply to this

Re: Codensity Monads

I see, that makes sense. It’s interesting how the development of some personal intuition and motivation can make that type of abstract result so much more approachable and meaningful.

As for the question about the codensity monad of Mfd(,)Mfd(-,\mathbb{R}), I realize that finding an answer may require a deeper understanding of the fine structure of smooth functions than I have. Further ideas, results or suggestions will be very welcome.

Posted by: Tobias Fritz on April 5, 2020 5:54 PM | Permalink | Reply to this

Re: Codensity Monads

Actually, your question about manifolds raises a broader question about codensity monads that deserves attention in its own right. Namely:

What is the codensity monad of a representable functor?

Your question involved a contravariant representable, but let me begin with a covariant one, say

B(b,):BSet. B(b, -): B \to Set.

If BB has copowers then B(b,)B(b, -) has a left adjoint, sending a set AA to the copower A×bA \times b. Since B(b,)B(b, -) has a left adjoint, its codensity monad is just the monad on SetSet induced by the adjunction, which is

AB(b,A×b). A \mapsto B(b, A \times b).

We can get a bit further if we assume that the object bb of BB is connected, in the sense that B(b,)B(b, -) preserves coproducts. Then the codensity monad is

AB(b,b)×A. A \mapsto B(b, b) \times A.

In other words, it’s the monad End(b)×End(b) \times - induced by the monoid End(b)=B(b,b)End(b) = B(b, b). An algebra for it is a set with an End(b)End(b)-action.

Now let’s look at contravariant representables,

B(,b):B opSet. B(-, b): B^{op} \to Set.

If BB has powers then B(,b)B(-, b) has a left adjoint, Ab AA \mapsto b^A, and the codensity monad is

AB(b A,b). A \mapsto B(b^A, b).

So it’s a kind of double dualization.

In your case, B=MfdB = Mfd and b=b = \mathbb{R}. The trouble is, MfdMfd doesn’t have all powers. (We’re running into a well-known obstacle: the category of manifolds doesn’t have many limits, or colimits for that matter.) Specifically, the power A\mathbb{R}^A doesn’t exist when AA is an infinite set. If it did, your codensity monad TT would be given by

T(A)=Mfd( A,). T(A) = Mfd(\mathbb{R}^A, \mathbb{R}).

Although there’s no such manifold as A\mathbb{R}^A (for an infinite set AA), it’s possible that there’s something to be gained by fantasizing about it. That is, perhaps there’s some kind of “smooth space” that deserves to be called A\mathbb{R}^A, and then T(A)T(A) can be thought of as the set of smooth real-valued functions on it. Maybe thinking this way can help with your quest of figuring out whether the codensity monad contains any infinitary operation, i.e. whether C (X)C^\infty(X) admits any infinitary operations for a generic manifold XX.

Incidentally, whatever the fictional A\mathbb{R}^A might be, one way of getting a smooth function A\mathbb{R}^A \to \mathbb{R} should be as follows: take a finite subset BB of AA, project from A\mathbb{R}^A to B\mathbb{R}^B (which is a manifold), then apply your favourite smooth function B\mathbb{R}^B \to \mathbb{R}. But that’s trivial — it’s not getting us the infinitary operations you’re interested in.

Posted by: Tom Leinster on April 6, 2020 1:27 PM | Permalink | Reply to this

Re: Codensity Monads

That looks like a useful perspective. Since MfdMfd still has at least finite powers, I think that it can be used to show that the finitary part of the codensity monad gives indeed the theory of C C^\infty-rings!

My idea was to consider TT-Alg opAlg^{\mathrm{op}} itself as a category of generalized smooth spaces, into which MfdMfd embeds fully faithfully. In particular, the formal dual of the free TT-algebra T(A)T(A) should itself play the role of a generalized smooth space model of A\mathbb{R}^A. But trying to leverage existing models of generalized smooth spaces in order to attack my conjecture also sounds like an idea worth looking into.

Posted by: Tobias Fritz on April 6, 2020 2:35 PM | Permalink | Reply to this

Re: Codensity Monads

Perhaps this came up in a previous thread, but do we know if there’s a categorified codensity monad construction to be had for the inclusion of the 2-category of finite categories, FinCatFinCat, into CatCat?

Could there be a kind of Stone-Čech compactification for categories?

I’m wondering this from reading Jacob Lurie’s Ultracategories. Hmm, could those lax/colax morphisms have something to do with his left and right ultrastructures?

[Perhaps for the latter, the inclusion of FinSetFinSet as discrete categories would do the trick.]

Posted by: David Corfield on April 14, 2020 8:44 AM | Permalink | Reply to this

Re: Where Do Ultrafilters Come From?

Ah, I see Mike was wondering about the inclusion of finitely presented ∞-groupoids into all ∞-groupoids back here.

Would the answer to my question change had I asked it about the inclusion of finitely presented categories?

Posted by: David Corfield on April 14, 2020 11:24 AM | Permalink | Reply to this

Re: Codensity Monads

Good question! I don’t know. I also don’t have much feeling for which notion of finiteness of a category would be most interesting to consider here.

At the strictest extreme (?), we could use those categories whose nerve has only finitely many nondegenerate simplices. These are the finite skeletal categories containing no endomorphisms except for identities.

Or, as you suggest, we could simply use the finite categories, i.e. those containing only finitely many objects and maps.

Or, we could use the finitely presentable categories. (And no, I don’t mean “locally finitely presentable”…)

And there are surely other options.

For each option, we have an essentially small subcategory of Cat, hence a codensity (2-)monad. It’s conceivable that some of these monads are the same, i.e. there’s some insensitivity to which notion of finiteness we start with. I say this because of the following theorem in the case of sets:

Let BB be a full subcategory of FinSetFinSet containing at least one set with at least three elements. Then the codensity monad of BSetB \hookrightarrow Set is the ultrafilter monad.

This theorem lends some plausibility to the hope that one dimension up, for CatCat, the codensity monad is unaffected by which notion of finiteness of a category that we start with. That would be nice! But I don’t know whether that’s hoping for too much.

Posted by: Tom Leinster on April 14, 2020 10:00 PM | Permalink | Reply to this

Re: Codensity Monads

I’ve given my guess for the case of finite discrete categories included in all categories on the other thread, the 2-monad that sends a category to the category of ‘ultrastructures’ on it.

Even if that’s right, I’d like to know answers to these other questions.

Posted by: David Corfield on April 14, 2020 10:52 PM | Permalink | Reply to this

Re: Codensity Monads

I say this because of the following theorem in the case of sets:

Let BB be a full subcategory of FinSetFinSet containing at least one set with at least three elements. Then the codensity monad of BSetB \hookrightarrow Set is the ultrafilter monad.

This theorem lends some plausibility to the hope that one dimension up, for CatCat, the codensity monad is unaffected by which notion of finiteness of a category that we start with. That would be nice! But I don’t know whether that’s hoping for too much.

Thanks for mentioning this intriguing question!

In the case of FinSetSetFinSet \hookrightarrow Set, there is a characterisation of T(X)T(X), where XX is a set and TT is the codensity monad, as the set of natural transformations from the functor Hom Set(X,):FinSetSetHom_{Set}(X, -): FinSet \rightarrow Set to the inclusion functor. As Tom spells out in his paper, this amounts to saying that an element of T(X)T(X) is an operation which takes as input a finite set BB and a map XBX \rightarrow B, and returns an element of BB, in a way which is natural in BB.

I attempted just now to figure out if there is some such nice characterisation in the case of G:FinCatCatG: FinCat \hookrightarrow Cat. I didn’t have time to check details, but I think there may be. Indeed, I believe that the right adjoint to the functor Hom(,G):Cat[FinCat,Set] opHom(-, G): Cat \rightarrow [FinCat, Set]^{op} in the notation of Tom’s paper should be something like the functor which takes a functor Y:FinCatSetY: FinCat \rightarrow Set and returns a category whose objects are functors Y(B)BY(B) \rightarrow B, running over finite categories BB, and viewing Y(B)Y(B) as a discrete category, and whose arrows are functors between finite categories which make the obvious square commute. In other words, the objects are indexed families of objects of finite categories, and the arrows are the morphisms of these (in the obvious sense).

As I say, I have not checked carefully that this gadget has the correct universal property, but something like this should be true I think.

One then gets I think a description of T(X)T(X) for a category XX as: an operation which takes as input a finite category BB and an indexed family of functors XBX \rightarrow B, and returns an indexed family of objects of BB, and does so in a way which is natural in BB.

This seems like quite a reasonable thing to work with! We could then try to see whether we can mimic the proof in Tom’s paper of the fact he mentions. One can certainly observe just as in the case for sets that there is such an operation for every object xx of XX, namely evaluation of each functor in the indexed family at xx. The question is whether one can cook up some ultrafilter-like operation as well.

I have run out of time to think about this for today! It is not clear to me yet whether, if what I have written above is correct, it helps to decide whether the codensity monad is sensitive to the notion of finiteness chosen; my feeling is that this will depend instead on the nature of the ‘ultrafilter-like operation’ that remains to be cooked up.

Posted by: Richard Williamson on April 16, 2020 12:08 AM | Permalink | Reply to this

Re: Codensity Monads

With a few more brain cells than I have, perhaps one could put together Di Liberti’s paper relating codensity with Isbell duality and some comments by Jim Dolan and John Baez at the latter’s page Doctrines:

There is a finite limits theory FinSetFin\Set, which is the embodiment of propositional logic. All finite sets can be formed from 22 by products and equalizers, so this finite limits theory is the Cauchy completion of the Lawvere theory whose objects are powers of 22, which is the opposite of the category of finitely presented Boolean algebras. Note: [FinSet,Set]=BoolAlg[Fin\Set, Set] = \Bool\Alg is the opposite of the category of profinite sets. [FinSet op,Set]=Set[Fin\Set^{op}, Set] = Set since FinSet opFin\Set^{op} is the free finite limits theory on one object.

Categorifying this example, we should get an interesting doctrine which is the embodiment of predicate logic. Namely, let FPGpd\FP\Gpd, the (2,1)(2,1)-category of finitely presented groupoids. Claim: theories of this doctrine are theories of first-order predicate logic. Conjecture: [FPGpd,Gpd][\FP\Gpd, Gpd] is the opposite of the category of profinite groupoids. [FPGpd op,Gpd]=Gpd[\FP\Gpd^{op}, Gpd] = Gpd. With luck this will explain the appearance of profinite groups in number theory.

Shouldn’t this suggest the codensity (2-)monad for the inclusion of FPGpdFPGpd in GpdGpd?

Posted by: David Corfield on April 16, 2020 3:50 PM | Permalink | Reply to this

Re: Codensity Monads

So we should take a look at the codensity 2-monad for the 2-Yoneda embedding of FPCatFPCat and relate this to Isbell duality.

Posted by: David Corfield on April 17, 2020 5:44 AM | Permalink | Reply to this

Re: Codensity Monads

Continuing wittering on to myself, section 10 of Enriched categories as a free cocompletion tells us about Kan extensions for (enriched) bicategories. So is there anything to prevent a right Kan extension for the 2-Yoneda embedding?

Something that might crop up in this particular case is that the 2-category of finite categories lacks finite colimits, while the 2-category of finitely presented categories lacks finite limits. If there is some Isbell duality to be had restricting to finite-limit preservation, we’d perhaps want [FPCat op,Cat][FPCat^{op}, Cat]. Is that just CatCat?

Posted by: David Corfield on April 17, 2020 12:57 PM | Permalink | Reply to this

Post a New Comment