How do I check if a functor has a (left/right) adjoint? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T05:44:39Z http://mathoverflow.net/feeds/question/5786 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint How do I check if a functor has a (left/right) adjoint? Harrison Brown 2009-11-17T06:21:13Z 2010-10-21T19:16:43Z <p>Because adjoint functors are just cool, and knowing that a pair of functors is an adjoint pair gives you a bunch of information from generalized abstract nonsense, I often find myself saying, "Hey, cool functor. Wonder if it has an adjoint?" The problem is, I don't know enough category theory to be able to check this for myself, which means I can either run and ask MO or someone else who might know, or give up.</p> <p>I know a couple of necessary conditions for a functor to have a left/right adjoint. If it doesn't preserve either limits or colimits, for example, I know I can give up. Is there an easy-to-check sufficient condition to know when a functor's half of an adjoint pair? Are there at least heuristics, other than "this looks like it might work?"</p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/5787#5787 Answer by marc for How do I check if a functor has a (left/right) adjoint? marc 2009-11-17T06:28:21Z 2009-11-17T06:28:21Z <p>There's the <a href="http://en.wikipedia.org/wiki/Adjoint%5Ffunctors#General%5Fexistence%5Ftheorem" rel="nofollow">Freyd Adjoint Functor Theorem</a>. </p> <p>A right adjoint functor is continuous (commutes with limits) and a left adjoint functor is cocontinuous (commutes with colimits). So, if a functor has a left adjoint then it is continuous because it is a right adjoint. The adjoint functor theorem is a partial converse to this fact in the case that the domain category is complete (has all small limits) and the functor satisfies a "smallness condition".</p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/5788#5788 Answer by Greg Stevenson for How do I check if a functor has a (left/right) adjoint? Greg Stevenson 2009-11-17T06:31:15Z 2009-11-17T22:44:34Z <p>The adjoint functor theorem <a href="http://en.wikipedia.org/wiki/Adjoint_functor_theorem#General_existence_theorem" rel="nofollow"> as stated here</a> and the special adjoint functor theorem (which can also both be found in Mac Lane) are both very handy for showing the existence of adjoint functors.</p> <p>First here is the statement of the special adjoint functor theorem:</p> <p><b>Theorem</b> Let $G\colon D\to C$ be a functor and suppose that the following conditions are satisfied:<br /> (i) $D$ and $C$ have small hom-sets<br /> (ii) $D$ has small limits<br /> (iii) $D$ is well-powered i.e., every object has a set of subobjects (where by a subobject we mean an equivalence class of monics)<br /> (iv) $D$ has a small cogenerating set $S$<br /> (v) $G$ preserves limits<br /> Then $G$ has a left adjoint.</p> <p><b>Example</b> I think this is a pretty standard example. Consider the inclusion <b>CHaus</b>$\to$<b>Top</b> of the category of compact Hausdorff spaces into the category of all topological spaces. Both of these categories have small hom-sets, it follows from Tychonoff's Theorem that <b>CHaus</b> has all small products and it is not so hard to check it has equalizers so it has all small limits and the the inclusion preserves these. <b>CHaus</b> is well-powered since monics are just injective continuous maps and there are only a small collection of topologies making any subspace compact and Hausdorff. Finally, one can check that $[0,1]$ is a cogenerator for <b>CHaus</b>. So $G$ has a left adjoint $F$ and we have just proved that the Stone-Čech compactification exists.</p> <p>If you have a candidate for an adjoint (say the pair $(F,G)$) and you want to check directly it is often easiest to try and cook up a unit and/or a counit and verify that there is an adjunction that way - either by using them to give an explicit bijection of hom-sets or by checking that the composites $$G \stackrel{\eta G}{\to} GFG \stackrel{G \epsilon}{\to} G$$ and $$F \stackrel{F \eta}{\to} FGF \stackrel{\epsilon F}{\to} F$$ are identities of $G$ and $F$ respectively.</p> <p>I thought (although I am at the risk of this getting excessively long) that I would add another approach. One can often use existing formalism to produce adjoints (although this is secretly using one of the adjoint functor theorems in most cases so in some sense is only psychologically different). For instance as in Reid Barton's <a href="http://mathoverflow.net/questions/1620/is-there-a-free-digraph-associated-to-a-graph/1703#1703" rel="nofollow">nice answer</a> if one can interpret the situation in terms of categories of presheaves or sheaves it is immediate that certain pairs of adjoints exist. Andrew's great answer gives another large class of examples where the content of the special adjoint functor theorem is working behind the scenes to make verifying the existence of adjoints very easy. Another class of examples is given by torsion theories where one can produce adjoints to the inclusions of certain subcategories of abelian (more generally pre-triangulated) categories by checking that certain orthogonality/decomposition properties hold.</p> <p>I can't help remarking that one instance where it is very easy to produce adjoints is in the setting of compactly generated (and well generated) triangulated categories. In the land of compactly generated triangulated categories one can wave the magic wand of Brown representability and (provided the target has small hom-sets) the only obstruction for a triangulated functor to have a right/left adjoint is preserving coproducts/products (and the adjoint is automatically triangulated).</p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/5789#5789 Answer by Andrew Critch for How do I check if a functor has a (left/right) adjoint? Andrew Critch 2009-11-17T06:50:50Z 2009-11-17T09:08:43Z <p>I think frequently the easiest to check <em>sufficient</em> conditions are the following, which also make precise why "this looks like it might work" is so often successful:</p> <p><b>Theorem:</b> A functor $G: C\to D$ is a right adjoint functor (i.e. has a left adjoint) <em>if and only if</em> for each object $Y$ in $D$, there exists an <a href="http://en.wikipedia.org/wiki/Universal%5Fmorphism" rel="nofollow">initial morphism</a> $\phi_Y:Y\to G(I_Y)$ from $Y$ to $G$. Moreover, once you find such an initial morphism from each $Y$ to $G$, the association $Y\mapsto I_Y$ extends in a unique way to act on morphisms defining a functor $F: D\to C$, which <em>moreover</em> is left adjoint to the original functor $G$.</p> <p>This is well-known and easy to prove (well, depending on who you ask), but is non-trivial and involves many steps, which are explained relatively well <a href="http://en.wikipedia.org/wiki/Adjoint%5Ffunctors#Adjunctions%5Fin%5Ffull" rel="nofollow">here.</a> (Essentially one is recovering the entire adjoint situation from just one functor and a unit transformation.) </p> <p>Once you know it, you can really take confidence in "follow your nose"-style adjoint construction. It doesn't involve having an "initial guess" for the left adjoint (as a functor), but actually constructs it for you in a way that is uniquely determined by the limited data of the initial morphisms --- really unique, not just up to natural isomorphism.</p> <p><b>As an example</b> of how this can be useful, think of the inclusion functor $U$ from $AbGrp$ to $Grp$. It's easy to see that any group $H$ has an abelianization $Ab(H) = H/[H,H]$ in $AbGrp$ with a map <br> $H\to Ab(H)$ satisfying an initial (universal) property. But then by the above theorem, we can automatically extend this association in a unique way to act on morphisms as well, defining an abelianization functor $Ab$ which is left adjoint to the inclusion $U$.</p> <p>This same trick expedites the construction of adjoints in pretty much any situation you can think of. </p> <p><hr /></p> <p><b>Edit:</b> Sometimes this theorem is used as an alternative definition for adjoint functors in terms of universal morphisms. However you look at it, the real utility is knowing that this "weak", and in fact asymetric, condition actually implies the "stronger", symmetric definitions of adjoints via hom-sets or units/counits. I think it's really worthwhile to sift through the three different characterizations of adjoints given on <a href="http://en.wikipedia.org/wiki/Adjoint%5Ffunctors#Adjunctions%5Fin%5Ffull" rel="nofollow">Wikipedia</a>.</p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/5794#5794 Answer by Andrew Stacey for How do I check if a functor has a (left/right) adjoint? Andrew Stacey 2009-11-17T07:38:00Z 2009-11-17T08:26:26Z <p>Obligatory n-lab reference: <a href="http://ncatlab.org/nlab/show/adjoint+functor+theorem" rel="nofollow">adjoint functor theorems</a></p> <p>Figuring out when functors had adjoints or not was something I did a lot of in <a href="http://www.math.ntnu.no/~stacey/Research/Preprints/smthcat.html" rel="nofollow">Comparative Smootheology</a> (section 8).</p> <p><strong>Edit:</strong> Thought I'd expand on my comment to Andrew Critch's answer. A simple application of the Special Adjoint Functor Theorem is to universal algebra where it becomes:</p> <p><strong>Theorem</strong> Let $D$ be a category that has finite products, is co-complete, is an $(E, M)$ category where $E$ is closed under finite products, is $E$-co-well-powered, and its finite products commute with filtered co-limits. Let $V$ be a variety of algebras. Let $F$ be a category with co-equalisers. Let $G : F \to DV$ (here, $DV$ is the category of $V$-algebra objects in $D$) be a covariant functor. Then the following statements are equivalent.</p> <ol> <li>$G$ has a left adjoint.</li> <li>The composition $|G| : F \to D$ of $G$ with the forgetful functor $DV \to D$ has a left adjoint.</li> </ol> <p>In particular, if we take $D$ to be $Set$, the category of sets, then we obtain the following (which can be found in any text book on universal algebra), in which the variety of algebras $V$ is identified with its category of models in $Set$:</p> <p><strong>Corollary</strong> Let $F$ be a co-complete category, $V$ a variety of algebras. For a covariant functor $G : F \to V$, the following statements are equivalent.</p> <ol> <li>$G$ has a left adjoint.</li> <li>$G$ is representable by a co-$V$-algebra object in $F$.</li> <li>$|G|$ is representable by an object in $F$.</li> </ol> <p>(And, of course, all of this can be turned round for adjoint pairs of contravariant functors)</p> <p>In further particular, if $G : F \to V$ preserves underlying sets then $|G|$ is representable (by the initial $F$-object) and so $G$ has a left adjoint.</p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/5820#5820 Answer by G. Rodrigues for How do I check if a functor has a (left/right) adjoint? G. Rodrigues 2009-11-17T14:36:13Z 2010-08-09T16:33:14Z <p>There are two parts to this answer.</p> <ol> <li><p>First, a functor must be continuous (cocontinuous) to have a left (right) adjoint. Most of the times, it is easy to check that a functor does <em>not</em> preserve (co)limits and thus it cannot have a a left (right) adjoint.</p></li> <li><p>(co)continuity is not enough to actually prove that a functor has the required adjoint, but it is <em>almost</em> good enough. Let me elaborate on this. If you have a functor $F:P\to Q$ between complete partial orders (and thus cocomplete) then it is an easy exercise to construct a left adjoint by taking a $\sup$ of an appropriate subset. This can be generalized in a straightforward way to any functor by taking an appropriate (co)limit. The bad news is that this (co)limit is in general over a large category so it may not exist. This is where the so-called solution-set conditions come in; they are way to trim down this large category to a small one.</p></li> </ol> <p>As many people already said there are various variations of this type of conditions, from the more general but also very cumbersome to check solution-set condition to easier conditions which combine some form of well-poweredness (each object has only a set of subobjects -- or quotients, whatever the case may be) with the existence of a small separating (or generating) set. One that guarantees the existence of a right adjoint and that sticks out particularly in my memory is the existence of a small dense subcategory -- check chapter V of Kelly's book on enriched category for the precise details. It is particularly memorable, because many categories come with god-given small dense categories like presheaf categories (courtesy of Yoneda) and sheaf categories (because dense composed with left adjoint is dense).</p> <p>Later edit: many people have complained about the limited usefulness of the adjoint functor theorems in that in many cases there is a direct, and thus much more enlightening, construction. But there <em>are</em> situations where such a direct construction is not available. One that I came across recently is when studying P. Johnstone's book <em>Stone spaces</em>, more precisely chapter III and the section on Manes' theorem about the monadicity of the category of compact Hausdorff spaces. In the sequel, P. Johnstone proves another result due to Manes, the fact that category of algebras (in the sense of universal algebra) in the category of compact Hausdorff spaces is also monadic. He remarks that one has to use the GAFT (and Beck's monadicity theorem) in this case, because there is no easy direct description of the left adjoint. Later in the book (somewhere, I am quoting from memory and do not have the book by me), he argues why there is no simple recipe for the left adjoint.</p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/5911#5911 Answer by Tom Leinster for How do I check if a functor has a (left/right) adjoint? Tom Leinster 2009-11-18T03:08:20Z 2009-12-22T19:51:53Z <p>Other people have mentioned the Adjoint Functor Theorems. Here's a different perspective.</p> <p>There's a famous Cambridge exam question set by Peter Johnstone: </p> <pre> Write an essay on (a) the usefulness, or (b) the uselessness, of the Adjoint Functor Theorems. </pre> <p>I agree with the undertone of the question: the Adjoint Functor Theorems (AFTs) aren't as useful as you might think when you first meet them. They're not <em>useless</em>: but my own experience is that the range of situations in which I've had no easy way of constructing the adjoint, yet have been able to verify the hypotheses of an AFT, has been very limited.</p> <p>Perhaps more useful than knowing the AFTs is knowing some large classes of situation where an adjoint is guaranteed to exist. Here are two such classes.</p> <p>${}$1. <b>Forgetful functors between categories of algebras.</b> Any time you have a category $\mathcal{A}$ of algebras, such as <b>Group</b>, <b>Ring</b>, <b>Vect</b>, ..., the forgetful functor $\mathcal{A} \to \mathbf{Set}$ has a left adjoint. What's not quite so well-known is that you don't have to forget <em>all</em> the structure; that is, the codomain doesn't have to be <b>Set</b>. </p> <p>For example, the functor $\mathbf{AbGp} \to \mathbf{Group}$ forgetting that a group is abelian automatically has a left adjoint. The functor $\mathbf{Ring} \to \mathbf{Monoid}$ forgetting the additive structure of a ring automatically has a left adjoint. The forgetful functor $\mathbf{Assoc} \to \mathbf{Lie}$, sending an associative algebra to its underlying Lie algebra (with bracket $[a, b] = a\cdot b - b \cdot a$) automatically has a left adjoint. (That might not look so much like a forgetful functor, but that's only because the bracket on an associative algebra isn't given as a primitive operation in the usual definition of associative algebra: it has to be derived from the other operations.)</p> <p>The same can be said if you talk about <em>topological</em> groups, rings, etc, basically because <b>Top</b> has all small limits and colimits.</p> <p>All that is a consequence of the General AFT (= 'the' AFT in some people's usage). To my mind it's the principal reason why it's worth learning or teaching the General AFT. </p> <p>${}$2. <b>Kan extensions.</b> Let $F: \mathbf{A} \to \mathbf{B}$ be any functor between small categories. Then there's an induced functor $$F^{*}: {[\mathbf{B}, \mathbf{Set}]} \to {[\mathbf{A}, \mathbf{Set}]}$$ defined by composition with $F$. (Here ${[\mathbf{B}, \mathbf{Set}]}$ means the category of functors from $\mathbf{B}$ to $\mathbf{Set}$, sometimes denoted ${\mathbf{Set}}^{\mathbf{B}}$.)</p> <p>The fact is that $F^{*}$ always has both a left and a right adjoint. These are called left and right Kan extension along $F$. The same is true if you replace $\mathbf{Set}$ by any category with small limits and colimits.</p> <p>This is really useful, though that might not be obvious. For example, suppose we're interested in representations of groups. A group can be regarded as a one-object category, and the category of representations of a group $G$ is just the functor category $[G, \mathbf{Vect}]$. Now take a group homomorphism $f: G \to H$. The induced functor $$f^{*}: [H, \mathbf{Vect}] \to [G, \mathbf{Vect}]$$ sends a representation of $H$ to a representation of $G$ in the obvious way. And it's guaranteed to have both left and right adjoints. These adjoints turn a representation of $G$ into a representation of $H$, in a canonical way. I believe representation theorists call these the 'induced' and 'coinduced' representations, at least in the case that $G$ is a subgroup of $H$ and $f$ is the inclusion.</p> <p><i>Exercise</i>: let $G$ be a group. There are unique homomorphisms $G \to 1$ and $1 \to G$, where $1$ is the trivial group. Each of these two homomorphisms induces a functor "$f^{*}$" between the category $[G, \mathbf{Set}]$ of $G$-sets and the category $[1, \mathbf{Set}] = \mathbf{Set}$ of sets. These two functors each have adjoints on both sides. So we end up with six functors and four adjunctions. What are they?</p> <p>The existence of Kan extensions is best derived from the theory of ends. In fact, ends allow you to describe them explicitly. </p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/5935#5935 Answer by Kevin Buzzard for How do I check if a functor has a (left/right) adjoint? Kevin Buzzard 2009-11-18T08:32:12Z 2009-11-18T08:32:12Z <p>Lots of people-who-are-fond-of-adjoint-functor-theorems have responded to this post saying "adjoint functor theorems". Let me give a more mundane and rather different answer which fits much better into my world view.</p> <p>In my experience (which may differ from others), the true answer is that category theorists have these adjoint functor theorems which work well in some cases, but whose problem, as I see it, is simply that they are quite general. I am certainly not a category theorist but I am a "working mathematician" and my experience with these general theorems has been quite negative. For example take the notion of free groups. I was talking to another staff member here once and they said they'd just set an UG project on constructing free groups and I said "can't you just say 'done by adjoint functor theorem'?" and we both laughed because we knew it was true. And then I actually went and looked up SAFT and checked that it could construct free groups---and it can't, because the category of groups (hardly an exotic or esoteric category!) does <em>not</em> have a small cogenerating set. As I write, the top answer here has 15 votes and a lovely statement of SAFT but if you can't get free groups with it then you surely have to question its usefulness. In fact, although this sort of goes against the grain of what most people are saying here, in my experience you would be crazy trying to invoke adjoint functor theorems to construct free groups: you're much better off making them yourself, not least because making them yourself will teach you much more about how the objects work.</p> <p>My experience is that things like SAFT are almost always justified with the statement "Stone-Cech compactification!". I have heard this justification, and <em>only</em> this, so often now that the excuse is wearing thin.</p> <p>So here is my answer: Yes, there are some general theorems. But if you're not a category theorist then <em>in my experience</em> they have limited applicability. You're better off thinking about things on your own, saying "hmm, here's an object with structure X, how might one naturally build an object with structure Y from it?". If you can go both ways you might well have constructed a pair of adjoint functors, and you could then try to check this by doing mathematics rather than waving general category-theory theorems which have specifically beein designed with a one-size-fits-all purpose in mind, and which don't apply to such exotic categories as the category of groups. </p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/6022#6022 Answer by Evan Jenkins for How do I check if a functor has a (left/right) adjoint? Evan Jenkins 2009-11-18T22:24:56Z 2009-11-18T22:24:56Z <p>Here is one situation where left and right adjoints always exist. Let $\mathcal{C}$ and $\mathcal{D}$ be semisimple $k$-linear categories such that</p> <ul> <li> $\mathcal{C}$ has only finitely many simple objects, and</li> <li> for any simple object $X$ of $\mathcal{C}$ or $\mathcal{D}$, $\operatorname{End}(X) \cong k$.</li> </ul> <p>The second condition is automatic if $k$ is algebraically closed. Under these circumstances, any $k$-linear functor $\mathcal{C} \to \mathcal{D}$ has both a left and a right adjoint, and their constructions are quite explicit.</p> <p>This fact is useful for working with fusion categories over an algebraically closed field (which automatically satisfy the conditions on $\mathcal{C}$). </p> http://mathoverflow.net/questions/5786/how-do-i-check-if-a-functor-has-a-left-right-adjoint/43090#43090 Answer by Buschi Sergio for How do I check if a functor has a (left/right) adjoint? Buschi Sergio 2010-10-21T19:16:43Z 2010-10-21T19:16:43Z <p>Certainly the fundamental theorem of the addition and the existence theorem of Freyd. However, this theorem is the base of a whole literature (eg categories reflective), to investigate whether and under what circumstances the conditions of the theorem of Freyd occurred</p> <p>(See, for example, "Abstract and Concrete Categories - The Joy of Cats" in <a href="http://www.tac.mta.ca/tac/reprints/index.html" rel="nofollow">http://www.tac.mta.ca/tac/reprints/index.html</a>, or the old H. Herrlich, Topologische Reflexionen und Coreflexionen. Lecture Notes in Mathematics 78).</p> <p>But there Is another smart and strategic way to the existence or nature of a functor as added, because the theory of monads and tripleability, we can lift an adjoint to a functor posted a diagram with suitable assumptions (there are several theorems respect).</p> <p>See "Triples, algebras and cohomology Jonathan Mock Beck "in <a href="http://www.tac.mta.ca/tac/reprints/index.html" rel="nofollow">http://www.tac.mta.ca/tac/reprints/index.html</a></p>