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.

December 2, 2009

Size, Yoneda, and Limits of Algebras

Posted by Mike Shulman

Let TT be a monad on a category CC, and C TC^T its category of Eilenberg-Moore algebras with forgetful functor u:C TCu\colon C^T\to C. Consider the following two (true) statements.

  1. For all CC and TT, if d:IC Td\colon I\to C^T is any diagram such that udu\circ d has a limit in CC, then dd has a limit in C TC^T which is preserved by uu.
  2. For all CC and TT, if CC is complete, then so is C TC^T, and uu is continuous.

Obviously the first implies the second. Interestingly, the second also implies the first, by a clever Yoneda-lemma argument. However, the argument applies a priori only to small categories, so it provides one convenient testing-ground to compare different ways of dealing with size.

First let’s prove that if (2) is true for all CC, then (1) is true when CC and II are small. Let TT be a monad on a small category CC, let C^=Set C op\hat{C} = Set^{C^{op}} be the category of presheaves on CC, and let y:CC^y\colon C\to \hat{C} be the Yoneda embedding. Since C^\hat{C} is the free cocompletion of CC, the monad TT extends uniquely to a cocontinuous monad T^\hat{T} on C^\hat{C}. Saying that T^\hat{T} “extends” TT means that T^yyT\hat{T}\circ y \cong y\circ T, coherently with the monad structure. It follows that TT-algebras can be identified with those T^\hat{T}-algebras whose underlying presheaves are representable, and we have the following diagram: C T y T C^ T^ u u^ C y C^\array{C^T & \overset{y^T}{\to} & \hat{C}^{\hat{T}}\\ ^u\downarrow && \downarrow^{\hat{u}}\\ C& \underset{y}{\to} & \hat{C}} in which the horizontal functors are both fully faithful. Now let d:IC Td\colon I\to C^T be a diagram, with II small, such that udu d has a limit \ell in CC. Since yy preserves limits, y()y(\ell) is also a limit of yudu^y Tdy u d \cong \hat{u} y^T d in C^\hat{C}. But C^\hat{C} is complete, so by assumption, C^ T^\hat{C}^{\hat{T}} is complete and u^\hat{u} is continuous. Therefore, since II is small, y Tdy^T d has a limit ^\hat{\ell} in C^ T^\hat{C}^{\hat{T}} which is preserved by u^\hat{u}. This means that u^(^)\hat{u}(\hat{\ell}) is a limit of u^y Td\hat{u} y^T d, and hence isomorphic to y()y(\ell). But then ^\hat{\ell} is a T^\hat{T}-algebra whose underlying presheaf is representable (it is represented by \ell), and thus it “is” a TT-algebra kk with u(k)u(k)\cong \ell. Finally, since fully faithful functors reflect limits, kk is a limit of dd which is preserved by uu.

I actually find this argument kind of striking. It implies that once we’ve proven that (say) products and equalizers lift to the category of algebras for any monad, it follows automatically that all limits lift similarly—even when the base category doesn’t have products and equalizers out of which those other limits can be constructed! Of course, philosophers can debate what it means for two true statements to be equivalent, but in practice this sort of argument can simplify your life.

Now what about when CC is large? Let me first point out some things that don’t work. In general, without any universes, the category Set C opSet^{C^{op}} will not exist. If CC is locally small, then the category of small presheaves on CC does always exist and is the free cocompletion of CC, but it is not complete without further assumptions on CC (such as that CC is small, or itself complete). So it seems hard to get away without some universe-like hypotheses.

Of course, if we assume Grothendieck’s axiom of universes, then we can reason as follows: pick a universe UU such that CC and II are UU-small, and let SetSet denote the UU-large category of UU-small sets; then the above argument goes through. Note that this requires the statement of (2) to be changed to “for any universe UU and any CC and TT, if CC is UU-small-complete, then so is C TC^T, and uu is UU-small-continuous.” However, presumably whatever argument we originally used to prove it would still prove this more general statement.

On the other hand, in strong Feferman set theory ZMC/S, we have a specified universe UU which satisfies the reflection schema, and “small,” “large,” “complete,” and “continuous” have a fixed meaning referring to this UU. We can now argue as follows: the above proof shows that (1) is true for any small categories CC and II. But this is just the “relativization” to UU of the statement (1) itself; thus by the reflection schema, (1) itself is true. Personally, I find this version cleaner, although (taking into account how one proves the consistency of Feferman set theory) they contain more or less the same content.

Posted at December 2, 2009 5:09 PM UTC

TrackBack URL for this Entry:

3 Comments & 0 Trackbacks

Re: Size, Yoneda, and Limits of Algebras

That’s a very nice argument! As far as I can see, though, it isn’t really using many of the specifics of C^\hat{C}? In particular, we only seemed to need the “free co-completion” for the sake of extending TT to T^\hat{T} — so we were just using something like:

there’s a 2-functor (^): CatCAT\mathrm{Cat} \rightarrow \mathrm{CAT}, such that

  1. C^\hat{C} is always complete, and
  2. there’s a natural map y:CC^y:C \rightarrow \hat{C}, full and faithful and preserving all limits that exist in CC.

So… is there some other such 2-functor that works for possibly-large categories as well? If so, then the argument would extend to large categories without needing to worry about issues of size. If I remember right, the “free completion” construction works fine for larger categories, but there, the unit CF cplt(C)C \rightarrow F_{\mathrm{cplt}}(C) doesn’t preserve limits that already existed, so isn’t any good to us…

Posted by: Peter LeFanu Lumsdaine on December 2, 2009 9:53 PM | Permalink | Reply to this

Re: Size, Yoneda, and Limits of Algebras

is there some other such 2-functor that works for possibly-large categories as well?

Good question; I don’t know. The “free completion” does exist for arbitrary locally small categories using small presheaves, but as you say, that’s not helpful.

Even if you find such a 2-functor, though, I don’t think it will quite prove the whole claim: only the case when the domain category II is also small. The arguments using universes and with Feferman set theory apply even when II is large. Admittedly, limits over large domain categories are not usually of great importance in practice, but the philosophical point is that the statement “limits lift to categories of algebras” is not size-dependent: all limits lift.

Posted by: Mike Shulman on December 2, 2009 10:51 PM | Permalink | PGP Sig | Reply to this

Re: Size, Yoneda, and Limits of Algebras

I should probably say that I didn’t invent this argument (at least, the small part of it). I don’t know who noticed it first; I learned it from Steve Lack.

Posted by: Mike Shulman on December 2, 2009 10:43 PM | Permalink | PGP Sig | Reply to this

Post a New Comment