## December 2, 2009

### Size, Yoneda, and Limits of Algebras

#### Posted by Mike Shulman

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

1. For all $C$ and $T$, if $d\colon I\to C^T$ is any diagram such that $u\circ d$ has a limit in $C$, then $d$ has a limit in $C^T$ which is preserved by $u$.
2. For all $C$ and $T$, if $C$ is complete, then so is $C^T$, and $u$ 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 $C$, then (1) is true when $C$ and $I$ are small. Let $T$ be a monad on a small category $C$, let $\hat{C} = Set^{C^{op}}$ be the category of presheaves on $C$, and let $y\colon C\to \hat{C}$ be the Yoneda embedding. Since $\hat{C}$ is the free cocompletion of $C$, the monad $T$ extends uniquely to a cocontinuous monad $\hat{T}$ on $\hat{C}$. Saying that $\hat{T}$ “extends” $T$ means that $\hat{T}\circ y \cong y\circ T$, coherently with the monad structure. It follows that $T$-algebras can be identified with those $\hat{T}$-algebras whose underlying presheaves are representable, and we have the following diagram: $\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\colon I\to C^T$ be a diagram, with $I$ small, such that $u d$ has a limit $\ell$ in $C$. Since $y$ preserves limits, $y(\ell)$ is also a limit of $y u d \cong \hat{u} y^T d$ in $\hat{C}$. But $\hat{C}$ is complete, so by assumption, $\hat{C}^{\hat{T}}$ is complete and $\hat{u}$ is continuous. Therefore, since $I$ is small, $y^T d$ has a limit $\hat{\ell}$ in $\hat{C}^{\hat{T}}$ which is preserved by $\hat{u}$. This means that $\hat{u}(\hat{\ell})$ is a limit of $\hat{u} y^T d$, and hence isomorphic to $y(\ell)$. But then $\hat{\ell}$ is a $\hat{T}$-algebra whose underlying presheaf is representable (it is represented by $\ell$), and thus it “is” a $T$-algebra $k$ with $u(k)\cong \ell$. Finally, since fully faithful functors reflect limits, $k$ is a limit of $d$ which is preserved by $u$.

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 $C$ is large? Let me first point out some things that don’t work. In general, without any universes, the category $Set^{C^{op}}$ will not exist. If $C$ is locally small, then the category of small presheaves on $C$ does always exist and is the free cocompletion of $C$, but it is not complete without further assumptions on $C$ (such as that $C$ 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 $U$ such that $C$ and $I$ are $U$-small, and let $Set$ denote the $U$-large category of $U$-small sets; then the above argument goes through. Note that this requires the statement of (2) to be changed to “for any universe $U$ and any $C$ and $T$, if $C$ is $U$-small-complete, then so is $C^T$, and $u$ is $U$-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 $U$ which satisfies the reflection schema, and “small,” “large,” “complete,” and “continuous” have a fixed meaning referring to this $U$. We can now argue as follows: the above proof shows that (1) is true for any small categories $C$ and $I$. But this is just the “relativization” to $U$ 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:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2123

### 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 $\hat{C}$? In particular, we only seemed to need the “free co-completion” for the sake of extending $T$ to $\hat{T}$ — so we were just using something like:

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

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

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 $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 $I$ is also small. The arguments using universes and with Feferman set theory apply even when $I$ 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