nLab
adjoint functor theorem

Contents

Idea

Adjoint functor theorems are theorems stating that under certain conditions a functor that preserves limits is a right adjoint, and that a functor that preserves colimits is a left adjoint.

A basic result of category theory is that right adjoint functors preserve all limits that exist in their domain, and, dually, left adjoints preserve all colimits. An adjoint functor theorem is a statement that (under certain conditions) the converse holds: a functor which preserves limits is a right adjoint.

The basic idea of an adjoint functor theorem is that if we could assume that a large category DD had all limits over small and large diagrams, then for R:DCR : D \to C a functor that preserves all these limits we might define its would-be left adjoint LL by taking LcL c to be the limit

Lclim cRdd L c \coloneqq \lim_{c\to R d} d

over the comma category c/Rc/R (whose objects are pairs (d,f:cRd)(d,f:c\to R d) and whose morphisms are arrows ddd\to d' in DD making the obvious triangle commute in CC) of the projection functor π:c/RD\pi: c/R \to D:

Lc=lim(c/RD). L c = \lim\; (c/R \to D ) \,.

Because with this definition there would be for every dd an obvious morphism

LRd=lim RdRddd L R d \stackrel{=}{\to} \lim_{R d \to R d'} d' \to d

(the component map over dd of the limiting cone) while moreover because RR preserves limits, we would have an isomorphism

RLclim cRdRd R L c \simeq \lim_{c\to R d} R d

and hence an obvious morphism of cone tips

cRLc. c \to R L c \,.

It is easy to check that these would be the unit and counit of an adjunction LRL\dashv R. See adjoint functor for more.

The problem with this would-be argument is that in general the comma category (c/G)(c/G) may not be small category. But one can generally not expect a large category to have all large limits: even if we pass to a universe in which (c/G)(c/G) is considered small, a classical theorem of Freyd says that any complete small category is a preorder (see complete small category for the proof, which is valid in classical logic and also holds classically in any Grothendieck topos). Thus, the argument we gave above is necessarily an adjoint functor theorem for preorders:

Theorem

If G:DCG:D\to C is any functor between (small) preorders such that DD has, and GG preserves, all small meets, then GG has a left adjoint.

(This theorem holds in constructive mathematics, although not in predicative mathematics; the classical reasoning before this explains why the theorem is not more general, but the proof itself is already constructive.)

To obtain adjoint functor theorems for categories that are not preorders, one must therefore impose various additional “size conditions” on the category DD and/or the functor GG.

Statement

Theorem

Sufficient conditions for a limit-preserving functor G:DCG : D \to C to be a right adjoint include:

In the first two cases, which work by replacing large limits by small ones, it suffices to assume that GG preserves small limits (that it preserves all limits will follow). The third case works by assuming that DD has, while not all large limits, enough so that the theorem goes through; thus is this case GG must be already known to preserve large limits as well.

Proof

Here is a proof of the General Adjoint Functor Theorem: that a functor R:CDR : C \to D out of a locally small category CC with all small limits has a left adjoint if it preserves these limits and satisfies the solution set condition.

From the discussion at adjoint functors – In terms of universal arrows we have that the existence of the adjoint is equivalent to the existence for each dDd \in D of an initial object i d:dRLdi_d : d \to R L d in the comma category (dR)(d \downarrow R): an object such that for each f:dRdf : d' \to R d there is a unique f˜\tilde f such that

d i d f RLd Rf˜ Rd Ld f˜ d \array{ && d \\ & {}^{\mathllap{i_d}}\swarrow && \searrow^{\mathrlap{f}} \\ R L d &&\underset{R \tilde f}{\to}&& R d' \\ \\ L d &&\underset{\tilde f}{\to}&& d' }

commutes. Now an initial object is the limit of the identity functor, but this is generally a large limit; we replace this with some small limit conditions that guarantee existence of an initial object.

  1. Let YY be a category. Call a small family of objects FF weakly initial if for every object yy of YY there exists xFx \in F and a morphism f:xyf: x \to y.

  2. Suppose YY has small products. If FF is a weakly initial family, then xFx\prod_{x \in F} x is a weakly initial object.

  3. Claim: Suppose YY is locally small and small complete. If xx is a weakly initial object, then the domain ee of the joint equalizer i:exi: e \to x of all arrows xxx \to x is an initial object. Proof: clearly ee is weakly initial. Suppose given an object yy and arrows f,g:eyf, g: e \to y; we must show f=gf = g. Let j:dej: d \to e be the equalizer of ff and gg. There exists an arrow k:xdk: x \to d. The arrow i:exi: e \to x equalizes 1 x1_x and ijk:xxi j k: x \to x, so ijki=ii j k i = i. Since ii is monic, j(ki)=1 ej (k i) = 1_e. Thus jj is an epi, and f=gf = g follows.

If CC is locally small and small-complete and R:CDR: C \to D preserves limits, then dRd \downarrow R is locally small and small-complete for every object dd of DD.

If in addition each dRd \downarrow R has a weakly initial family (solution set condition), then by 2. and 3. each dRd \downarrow R has an initial object. This restates the condition that RR has a left adjoint.

Proof of SAFT

As before, the proof proceeds by constructing initial objects of comma categories. We assume that CC is locally small, small-complete, well-powered, has a cogenerating set {c α:αA}\{c_\alpha: \alpha \in A\}, and that R:CDR: C \to D is a small-continuous functor into a locally small category DD.

As before, for each object dd of DD, the comma category dRd \downarrow R is locally small and small-complete. Moreover, it is easy to check that it is well-powered, and that the set of all objects of the form dRc αd \to R c_\alpha is a cogenerating set for dRd \downarrow R.

It then remains to prove that any locally small, small-complete, well-powered category XX with a cogenerating set {k s:sS}\{k_s: s \in S\} has an initial object. The initial object 00 is constructed as the intersection = pullback of all subobjects of sk s\prod_s k_s, i.e., the minimal subobject. Then, given f,g:0xf, g: 0 \to x, the equalizer Eq(f,g)Eq(f, g) is isomorphic to 00 because 00 is minimal, and so f=gf = g: there is at most one arrow 0x0 \to x for each xx.

On the other hand, for each xx the canonical map

i:x sSk s hom(x,k s)i: x \to \prod_{s \in S} k_{s}^{\hom(x, k_s)}

is monic since the k sk_s cogenerate. The following pullback of ii,

k x i sk s 1 sk s ! sk s hom(x,k s),\array{ k & \to & x \\ \downarrow & & \downarrow \mathrlap{i} \\ \prod_s k_{s}^1 & \stackrel{\prod_s k_{s}^!}{\to} & \prod_s k_{s}^{\hom(x, k_s)} },

gives a subobject kk of sk s\prod_s k_s that maps to xx, and into which 00 embeds. Thus there exists a map 0x0 \to x, and we conclude 00 is initial.

In practice an important special case is that of functors between locally presentable categories. For these there is the following version of an adjoint functor theorem.

Theorem

Let F:CDF : C \to D be a functor between locally presentable categories. Then

The second statement, characterizing when FF has a left adjoint, is (AdamekRosicky, theorem 1.66). This is an application of the general adjoint functor theorem: any accessible functor satisfies the solution set condition. The accessibility condition is indeed necessary, as is discussed below in the section In locally presentable categories.

The first statement, characterizing when FF has a right adjoint, can be proven using the special adjoint functor theorem: by a non-trivial theorem (AdamekRosicky, theorem 1.58), any locally presentable category is co-wellpowered.

A right adjoint to any cocontinuous functor F:CDF \colon C \to D between locally presentable categories can also be constructed directly. If CC is locally λ\lambda-presentable and P λP_\lambda is the subcategory of λ\lambda-small objects, then CC is equivalent to the full subcategory of [P λ op,Set][P_\lambda^{op},Set] of presheaves that preserve λ\lambda-small limits (AdamekRosicky, theorem 1.46). The presheaves in the image of the functor D[P λ op,Set]D \to [P_\lambda^{op},Set] defined by dhom(F,d)d \mapsto \hom(F-,d) preserve λ\lambda-small limits because FF is cocontinuous. So this functor factors through the subcategory CC. The functor DCD \to C so-constructed is a right adjoint to FF.

Examples

In locally presentable categories

The following is a counter-example, showing that the necessity of the accesibility clause in theorem 3.

Example

For every infinite cardinal number κ\kappa, let G κG_\kappa be a simple group of cardinality κ\kappa. Define the functor ML:ML: Group \to Set to be the product of all the representable functors Hom(G κ,)Hom(G_\kappa,-). Since no group can admit a nontrivial homomorphism from proper-class-many of the G κG_\kappa, this functor does indeed land (or can be redefined to land) in Set. Since it is a product of representables, it is continuous (and of course Group and Set are locally presentable categories), but it is not itself representable (hence has no left adjoint).

André Joyal has been attributing this example to Saunders MacLane, It appears in print for instance right at the beginning of (AdámekKoubekTrnková01).

In toposes

Proposition

Every sheaf topos is a total category and a cototal category.

See the discussion at Grothendieck topos .

It follows that

Corollary

Let F:CDF : C \to D be a functor between sheaf toposes. Then

In presheaf categories

It is instructive to spell out the construction of the right adjoint from a colimit preserving functor LL in the simple case where all categories are categories of presheaves. This is a particularly simple case, but is useful in itself and serves as a template for the general case.

So let now CC and DD be small categories and

L:PSh(C)PSh(D) L : PSh(C) \to PSh(D)

a colimit-preserving functor. Then its right adjoint is given by

RA:=Hom PSh(D)(L(),A) R A := Hom_{PSh(D)}(L(-),A)

as we shall check in a moment. But first notice that using the co-Yoneda lemma this may be rewritten as

cCHom PSh(D)(L(c),X)c \cdots \simeq \int^{c \in C} Hom_{PSh(D)}(L(c), X) \cdot c

where the coend is equivalently given by the colimit

=lim LcAc. = \lim_{\underset{L c \to A}{\to}} c \,.

This is the formula for the would-be right adjoint from the general discussion above, only that here the colimit is only over the representables, hence over a small category.

Now we check that the RR thus obtained is indeed right adjoint to LL, by explicitly checking the hom-isomorphism of the pair of adjoint functors:

We compute Hom PSh(D)(L(X),A)Hom_{PSh(D)}(L(X),A). In the first step

Hom PSh(D)(L(X),A)Hom PSh(D)(L( cCX(c)c),A) Hom_{PSh(D)}(L(X), A) \simeq Hom_{PSh(D)}(L (\int^{c \in C} X(c) \cdot c), A)

we use the co-Yoneda lemma for XX. Then because LL preserves colimits this is

Hom PSh(D)( cX(c)L(c),A). \cdots \simeq Hom_{PSh(D)}(\int^c X(c) \cdot L(c), A) \,.

Since the hom preserves limits in both arguments, we can take the coend out to get an end

cCHom PSh(D)(X(c)L(c),A) \cdots \simeq \int_{c \in C} Hom_{PSh(D)}(X(c) \cdot L(c), A)

Then we use the standard tensoring of our categories over Set to get

cCHom Set(X(c),Hom PSh(D)(L(c),A)). \cdots \simeq \int_{c \in C} Hom_{Set}(X(c), Hom_{PSh(D)}(L(c),A)) \,.

And finally this is recognized as the formula for the hom-set of presheaves (see functor category)

Hom PSh(C)(X,Hom(L(),A))=Hom PSh(C)(X,RA). \cdots \simeq Hom_{PSh(C)}(X, Hom(L(-),A)) = Hom_{PSh(C)}(X, R A) \,.

In total this establishes the hom-isomorphism

Hom PSh(D)(L(X),A)Hom PSh(C)(X,R(A)). Hom_{PSh(D)}(L(X), A) \simeq Hom_{PSh(C)}(X, R(A)) \,.

References

A brief introductory discussion is around theorem 5.4 of

A detailed expository survey is

  • Oliver Kullmann, The adjoint functor theorem (pdf slides)

The adjoint functor theorem in context with Yoneda embedding is discussed in

  • Friedrich Ulmer, The adjoint functor theorem and the Yoneda embedding Illinois J. Math. Volume 15, Issue 3 (1971), 355-361. (web)

The case for locally presentable categories is discussed in

Revised on March 20, 2014 09:58:53 by Emily Riehl (198.129.65.18)