category theory

# Contents

## Statement

###### Theorem

(The adjoint lifting theorem). Consider the following commutative square of functors:

$\begin{array}{ccc}\mathrm{\pi }& \stackrel{Q}{\beta }& \mathrm{\beta ¬}\\ {}^{U}\beta & & {\beta }^{V}\\ \mathrm{\pi }& \underset{R}{\beta }& \mathrm{\pi }\end{array}$\begin{array}{cccc}\mathcal{A} & \overset{Q}{\to} & \mathcal{B} \\ ^{U}\downarrow & & \downarrow^{V} \\ \mathcal{C} & \underset{R}{\to} & \mathcal{D} \end{array}

and suppose that

• $U$ and $V$ are monadic, and

• $\mathrm{\pi }$ has coequalizers of reflexive pairs.

Then, if $R$ has a left adjoint, then $Q$ also has a left adjoint.

A detailed proof may be found in Sec. 4.5 of Vol. 2 of Borceux (see especially Theorem 4.5.6 on p. 226 and Ex. 4.8.6 on p. 252). Also (Johnstone, prop. 1.1.3) For a sketch of proof, see ahead.

###### Corollary

If the bottom functor $R$ of the above square is the identity arrow (so that $U=V\beta Q$), if $U$ and $V$ are monadic, and if $\mathrm{\pi }$ has coequalizers of reflexive pairs, then $Q$ is monadic.

###### Proof

The adjoint lifting theorem implies the existence of a left adjoint, and the rest is a straightforward application of the monadicity theorem.

## Sketch of proof

We may assume the situation of the following diagram (with $VQ=RU$):

$\begin{array}{ccc}{\mathrm{\pi }}^{\mathrm{\pi }}& \underset{Q}{\overset{K\left(?\right)}{\beta }}& {\mathrm{\pi }}^{\mathrm{\pi }}\\ {}^{U}\beta {\beta }^{F}& & {}^{G}\beta {\beta }^{V}\\ \mathrm{\pi }& \underset{R}{\overset{L}{\beta }}& \mathrm{\pi }\end{array}$\begin{array}{cccc}\mathcal{C}^\mathbb{T} & \underoverset{Q}{K(?)}{\leftrightarrows} & \mathcal{D}^\mathbb{S} \\ ^{U}\downarrow \uparrow^{F} & & ^{G}\uparrow\downarrow^{V} \\ \mathcal{C} & \underoverset{R}{L}{\leftrightarrows} & \mathcal{D} \end{array}

where $\mathrm{\pi }=\beta ¨T,\mathrm{\Xi ΅}:{1}_{\mathrm{\pi }}\beta T,\mathrm{\Xi Ό}\beta ©$ is a monad on $\mathrm{\pi }$, $\mathrm{\pi }=\beta ¨S,\mathrm{\Xi Ά}:{1}_{\mathrm{\pi }}\beta S,\mathrm{\Xi ·}\beta ©$ is a monad on $\mathrm{\pi }$, $U$ and $V$ are the forgetful functors, and $F$ and $G$ are the free algebra functors.

Let us write $\mathrm{Ο}:FU\beta {1}_{{\mathrm{\pi }}^{\mathrm{\pi }}}$ for the counit of the adjunction $F\beta £U$ and $\mathrm{Ο}:GV\beta {1}_{{\mathrm{\pi }}^{\mathrm{\pi }}}$ for the counit of the adjunction $G\beta £V$. As usual, we have $T=UF$, $S=VG$, $\mathrm{\Xi Ό}=U\mathrm{Ο}F$, and $\mathrm{\Xi ·}=V\mathrm{Ο}G$.

Finally, let $L$ be a left adjoint to $R$ (which exists by assumption), and let $\mathrm{\Xi ±}:{1}_{\mathrm{\pi }}\beta RL$ and $\mathrm{\Xi ²}:\mathrm{LR}\beta {1}_{\mathrm{\pi }}$ be the unit and counit (respectively) of the adjunction $L\beta £R$.

We would like to construct a functor $K:{\mathrm{\pi }}^{\mathrm{\pi }}\beta {\mathrm{\pi }}^{\mathrm{\pi }}$. To get a hint of what $K$ should look like, let us assume for a moment that such a $K$ already exists. In this case, we have $KG\beta £VQ\left(=RU\right)$. But $FL$ is also left adjoint to $RU$, and by the uniqueness of a left adjoint we must have $KG=FL$ (at least up to a natural isomorphism).

From this, we already know how to define $K$ on free algebras. Also, being a left adjoint, $K$ preserves in particular all coequalizers. But every $\mathrm{\pi }$-algebra $\beta ¨D,\mathrm{\Xi Ύ}:\mathrm{SD}\beta D\beta ©$ is the (object part) of a reflexive coequalizer, namely, the canonical presentation

$GS\left(D\right)\underset{G\mathrm{\Xi Ύ}}{\overset{{\mathrm{Ο}}_{GD}}{\beta }}G\left(D\right)\stackrel{{\mathrm{Ο}}_{\beta ¨D,\mathrm{\Xi Ύ}\beta ©}=\mathrm{\Xi Ύ}}{\beta }\beta ¨D,\mathrm{\Xi Ύ}\beta ©$G S(D)\underoverset{G\xi}{\sigma_{G D}}{\rightrightarrows}G(D)\overset{\sigma_{\langle D,\xi\rangle}=\xi}{\rightarrow}\langle D,\xi \rangle

Applying $K$ and using $\mathrm{KG}=\mathrm{FL}$, we see that $K\beta ¨D,\mathrm{\Xi Ύ}\beta ©$ should be the object part of a reflexive coequalizer in ${\mathrm{\pi }}^{\mathrm{\pi }}$ of the form

$FLS\left(D\right)\underset{FL\mathrm{\Xi Ύ}}{\overset{?}{\beta }}FL\left(D\right)\stackrel{x}{\beta }K\beta ¨D,\mathrm{\Xi Ύ}\beta ©$F L S(D)\underoverset{F L\xi}{?}{\rightrightarrows}F L(D)\overset{x}{\rightarrow}K\langle D,\xi \rangle

(recall that we assume that ${\mathrm{\pi }}^{\mathrm{\pi }}$ has coequalizers of reflexive pairs).

To eventually define $K\beta ¨D,\mathrm{\Xi Ύ}\beta ©$ as a coequalizer (as above), we first need some reasonable guess for the ?-arrow. For this, we will need a lemma.

###### Lemma

There exists a natural transformation $\mathrm{\Xi »}:SR\beta RT$ for which the following diagram of functors and natural transformations is commutative:

$\begin{array}{ccccccc}R& \stackrel{\mathrm{\Xi Ά}R}{\beta }& SR& & \stackrel{\mathrm{\Xi ·}R}{\beta }& & SSR\\ & {}^{R\mathrm{\Xi ΅}}\beta & {}^{\mathrm{\Xi »}}\beta & & & & {}^{S\mathrm{\Xi »}}\beta \\ & & RT& \stackrel{R\mathrm{\Xi Ό}}{\beta }& RTT& \stackrel{\mathrm{\Xi »}T}{\beta }& SRT\end{array}$\begin{array}{ccccccc} R & \overset{\zeta R}{\to} & S R & & \overset{\eta R}{\leftarrow}& & S S R \\ & ^{R\varepsilon}\searrow & ^{\lambda}\downarrow & & & & ^{S\lambda}\downarrow\\ & & R T & \overset{R\mu}{\leftarrow} & R T T & \overset{\lambda T}{\leftarrow} & S R T \end{array}
###### Proof

Define $\mathrm{\Xi »}:=V\mathrm{Ο}QF\beta VGR\mathrm{\Xi ΅}$, so that

$\mathrm{\Xi »}:SR=VGR\stackrel{VGR\mathrm{\Xi ΅}}{\beta }VGRT=VGRUF=VGVQF\stackrel{V\mathrm{Ο}QF}{\beta }VQF=RUF=RT.$\lambda \colon S R = V G R\overset{V G R\varepsilon}{\to}V G R T = V G R U F = V G V Q F\overset{V\sigma Q F}{\to} V Q F = R U F = R T.

The required commutativity may be verified by using the commutative diagrams in the definitions of a monad and an EM-algebra, naturality, and the triangular identities. For details, see the proof of Lemma 4.5.1 of Borceux, pp. 222-223. (Note that this lemma does not depend neither on the existence of a left adjoint for the bottom horizontal arrow, nor on the existence of coequalizers. Only the commutativity is required.)

We may now return to our task of defining the ?-arrow in the diagram preceding the lemma. We would like to get from $FLS\left(D\right)$ to $FL\left(D\right)$, and for this, we will construct a natural transformation $FLS\beta FL$ in the following way. First, we have

$S\stackrel{S\mathrm{\Xi ±}}{\beta }SRL\stackrel{\mathrm{\Xi »}L}{\beta }RTL.$S\overset{S\alpha}{\to} S R L \overset{\lambda L}{\to} R T L.

Applying $L$ and composing with $\mathrm{\Xi ²}TL$, we get

$\mathrm{LS}\stackrel{L\mathrm{\Xi »}L\beta \mathrm{LS}\mathrm{\Xi ±}}{\beta Ά}LRTL\stackrel{\mathrm{\Xi ²}\mathrm{TL}}{\beta }\mathrm{TL}.$LS\overset{L\lambda L\circ LS\alpha}{\longrightarrow}L R T L \overset{\beta TL}{\to} TL.

Applying $F$ and composing with $\mathrm{Ο}FL$, we finally get

$FLS\stackrel{F\mathrm{\Xi ²}TL\beta FL\mathrm{\Xi »}L\beta FLS\mathrm{\Xi ±}}{\beta Ά}FTL=FUFL\stackrel{\mathrm{Ο}FL}{\beta }FL$F L S\overset{F\beta T L\circ F L\lambda L\circ F L S\alpha}{\longrightarrow}F T L = F U F L\overset{\tau F L}{\to} F L

Let us call the resulting natural transformation $\mathrm{Ο}$, that is,

$\mathrm{Ο}:=\mathrm{Ο}FL\beta F\mathrm{\Xi ²}TL\beta FL\mathrm{\Xi »}L\beta FLS\mathrm{\Xi ±}.$\omega:=\tau F L \circ F\beta T L\circ F L\lambda L\circ F L S\alpha.

Now we take the sought for ?-arrow to be ${\mathrm{Ο}}_{D}$, and define $K\beta ¨D,\mathrm{\Xi Ύ}\beta ©$ as the object of some fixed coequalizer of ${\mathrm{Ο}}_{D}$ and $FL\mathrm{\Xi Ύ}$:

$FLS\left(D\right)\underset{FL\mathrm{\Xi Ύ}}{\overset{{\mathrm{Ο}}_{D}}{\beta }}FL\left(D\right)\stackrel{x}{\beta }K\beta ¨D,\mathrm{\Xi Ύ}\beta ©.$F L S(D)\underoverset{F L\xi}{\omega_D}{\rightrightarrows}F L(D)\overset{x}{\rightarrow}K\langle D,\xi \rangle.

In order to do this, we must first verify that the parallel arrows above have a common section (since we only assume that ${\mathrm{\pi }}^{\mathrm{\pi }}$ has coequalizers of reflexive pairs). To find a guess for a common section, note that the common section for the parallel pair in the above canonical presentation in ${\mathrm{\pi }}^{\mathrm{\pi }}$ is $G{\mathrm{\Xi Ά}}_{V\beta ¨D,\mathrm{\Xi Ύ}\beta ©}=G{\mathrm{\Xi Ά}}_{D}$, and if $K$ exists, then applying $K$ gives $KG{\mathrm{\Xi Ά}}_{D}=FL{\mathrm{\Xi Ά}}_{D}$. Having this guess, it is now straightforward to verify that $FL{\mathrm{\Xi Ά}}_{D}$ is indeed a common section, as required.

So, we have defined an object function of a would be left adjoint $K$. To make it into a functor left adjoint to $Q$, we will build a universal arrow from $\beta ¨D,\mathrm{\Xi Ύ}\beta ©$ to $Q$, whose object part is $K\beta ¨D,\mathrm{\Xi Ύ}\beta ©$ (Theorem IV.1.2(ii) of Categories Work).

To get an arrow $\beta ¨D,\mathrm{\Xi Ύ}\beta ©\beta QK\beta ¨D,\mathrm{\Xi Ύ}\beta ©$ , suppose for a moment that we have a natural transformation $\mathrm{Ο}:G\beta QFL$ such that $\mathrm{Ο}\beta \mathrm{Ο}G=Q\mathrm{Ο}\beta \mathrm{Ο}S$. Then the left square in the following diagram commutes:

$\begin{array}{ccccc}GS\left(D\right)& \underset{G\mathrm{\Xi Ύ}}{\overset{{\mathrm{Ο}}_{GD}}{\beta }}& G\left(D\right)& \stackrel{{\mathrm{Ο}}_{\beta ¨D,\mathrm{\Xi Ύ}\beta ©}=\mathrm{\Xi Ύ}}{\beta }& \beta ¨D,\mathrm{\Xi Ύ}\beta ©\\ {}^{{\mathrm{Ο}}_{SD}}\beta & & {}^{{\mathrm{Ο}}_{D}}\beta & & {}^{\mathrm{Ο}}\beta \\ QFLSD& \underset{QFL\mathrm{\Xi Ύ}}{\overset{Q{\mathrm{Ο}}_{D}}{\beta }}& QFLD& \stackrel{Qx}{\beta }& QK\beta ¨D,\mathrm{\Xi Ύ}\beta ©\end{array}$\begin{array}{ccccc}G S(D)& \underoverset{G\xi}{\sigma_{G D}}{\rightrightarrows} & G(D) &\overset{\sigma_{\langle D,\xi\rangle}=\xi}{\rightarrow}&\langle D,\xi \rangle \\ ^{\varphi_{S D}}\downarrow && ^{\varphi_D}\downarrow && ^{\chi}\downarrow\\ Q F L S D &\underoverset{Q F L\xi}{Q\omega_D}{\rightrightarrows} & Q F L D &\overset{Q x}{\rightarrow}&Q K\langle D,\xi\rangle \end{array}

Since both rows are forks, it follows that $Qx\beta {\mathrm{Ο}}_{D}$ has the same composition with the arrows of the upper
parallel pair, and hence there exists a unique arrow $\mathrm{Ο}:\beta ¨D,\mathrm{\Xi Ύ}\beta ©\beta QK\beta ¨D,\mathrm{\Xi Ύ}\beta ©$ making the right square commutative (recall that the upper row is a coequalizer).

It is now possible to prove that the pair $\beta ¨K\beta ¨D,\mathrm{\Xi Ύ}\beta ©,\mathrm{Ο}\beta ©$ is a universal arrow from $\beta ¨D,\mathrm{\Xi Ύ}\beta ©$ to $Q$, showing that $K$ is indeed (the object function) of a left adjoint (for details, see the proof of Theorem 4.5.6, pp. 226-227 in Borceux).

But we still have to prove the existence of a natural transformation $\mathrm{Ο}:G\beta QFL$ such that $\mathrm{Ο}\beta \mathrm{Ο}G=Q\mathrm{Ο}\beta \mathrm{Ο}S$. For this, we define $\mathrm{Ο}:=\mathrm{Ο}QFL\beta GR\mathrm{\Xi ΅}L\beta G\mathrm{\Xi ±}$. Since $V$ is faithful, to prove the required property of $\mathrm{Ο}$, it is enough to prove that $V\mathrm{Ο}\beta V\mathrm{Ο}G=VQ\mathrm{Ο}\beta V\mathrm{Ο}S$, and this is a long, yet straightforward, computation (noting that $V\mathrm{Ο}=\mathrm{\Xi »}L\beta \mathrm{VG}\mathrm{\Xi ±}$ and using the commutative diagram from Lemma 1; see Lemma 4.5.3, p. 224 of Borceux).

## Examples

### Forgetful functors between varieties of algebras

Since varieties of algebras are cocomplete and monadic over $\mathrm{Set}$, the corollary implies that forgetful functors between varieties of algebras (e.g., the forgetful functor $\mathrm{Rng}\beta \mathrm{Ab}$) are monadic.

### Sufficient conditions for cocompleteness of monadic categories

Let $\mathrm{\pi ₯}$ be an arbitrary category, and consider the commutative diagram

$\begin{array}{ccc}\mathrm{\pi }& \stackrel{\mathrm{\Xi }}{\beta }& {\mathrm{\pi }}^{\mathrm{\pi ₯}}\\ {}^{U}\beta & & {\beta }^{{U}^{\mathrm{\pi ₯}}}\\ \mathrm{\pi }& \underset{\mathrm{\Xi }}{\beta }& {\mathrm{\pi }}^{\mathrm{\pi ₯}}\end{array}$\begin{array}{ccccc}\mathcal{A} & \overset{\Delta}{\to} & \mathcal{A}^\mathcal{J} \\ ^{U}\downarrow & & \downarrow^{U^{\mathcal{J}}} \\ \mathcal{C} & \underset{\Delta}{\to} & \mathcal{C}^\mathcal{J} \end{array}

where $U$ is monadic, $\mathrm{\Xi }$ is the diagonal functor and ${U}^{\mathrm{\pi ₯}}=U\beta \beta $. If $F$ is left adjoint
to $U$, then ${F}^{\mathrm{\pi ₯}}$ is left adjoint to ${U}^{\mathrm{\pi ₯}}$ (using the unit and counit of the original adjunction, one can construct appropriate natural transformations that satisfy the triangular identities, see, e.g., p. 119 of Categories Work). Also, the conditions of the monadicity theorem for $U$ imply those for ${U}^{\mathrm{\pi ₯}}$ (basically because the definition of a split fork involves only compositions and identities, and because natural transformations are composed componentwise).

Now, if $\mathrm{\pi }$ is $\mathrm{\pi ₯}$-cocomplete (so that the bottom horizontal functor has a left adjoint) and $\mathrm{\pi }$ has coequalizers of reflexive pairs, then the adjoint lifting theorem implies that $\mathrm{\pi }$ is $\mathrm{\pi ₯}$-cocomplete. In particular, if $\mathrm{\pi }$ has coequalizers of reflexive pairs and $\mathrm{\pi }$ is small-cocomplete, then $\mathrm{\pi }$ is small cocomplete.

## References

Section 4.5 of volume 2 of

• Peter Johnstone, Adjoint lifting theorems for categories of algebras , Bull. London Math. Soc., 7 (1975), 294-297.

Section A1.1 of

Revised on October 12, 2012 22:41:51 by Mike Shulman (192.16.204.218)