Adjoint functors

In mathematics, specifically category theory, adjunction is a possible relationship between two functors.

Adjunction is ubiquitous in mathematics, as it specifies intuitive notions of optimization and efficiency.

In the most concise symmetric definition, an adjunction between categories C and D is a pair of functors,

  and  

and a family of bijections

which is natural for all variables X in C and Y in D. The functor F is called a left adjoint functor, while G is called a right adjoint functor. The relationship “F is left adjoint to G” (or equivalently, “G is right adjoint to F”) is sometimes written

This definition and others are made precise below.

Introduction

The slogan is "Adjoint functors arise everywhere".

The long list of examples in this article is only a partial indication of how often an interesting mathematical construction is an adjoint functor. As a result, general theorems about left/right adjoint functors, such as the equivalence of their various definitions or the fact that they respectively preserve colimits/limits (which are also found in every area of mathematics), can encode the details of many useful and otherwise non-trivial results.

Spelling (or morphology)

One can observe (e.g. in this article), two different roots are used: "adjunct" and "adjoint". From Oxford shorter English dictionary, "adjunct" is from Latin, "adjoint" is from French.

In Mac Lane, Categories for the working mathematician, chap. 4, "Adjoints", one can verify the following usage.

The hom-set bijection is an "adjunction".

If an arrow in , is the right "adjunct" of (p. 81).

The functor is left "adjoint" for .

Motivation

Solutions to optimization problems

It can be said that an adjoint functor is a way of giving the most efficient solution to some problem via a method which is formulaic. For example, an elementary problem in ring theory is how to turn a rng (which is like a ring that might not have a multiplicative identity) into a ring. The most efficient way is to adjoin an element '1' to the rng, adjoin all (and only) the elements which are necessary for satisfying the ring axioms (e.g. r+1 for each r in the ring), and impose no relations in the newly formed ring that are not forced by axioms. Moreover, this construction is formulaic in the sense that it works in essentially the same way for any rng.

This is rather vague, though suggestive, and can be made precise in the language of category theory: a construction is most efficient if it satisfies a universal property, and is formulaic if it defines a functor. Universal properties come in two types: initial properties and terminal properties. Since these are dual (opposite) notions, it is only necessary to discuss one of them.

The idea of using an initial property is to set up the problem in terms of some auxiliary category E, and then identify that what we want is to find an initial object of E. This has an advantage that the optimization—the sense that we are finding the most efficient solution—means something rigorous and is recognisable, rather like the attainment of a supremum. The category E is also formulaic in this construction, since it is always the category of elements of the functor to which one is constructing an adjoint. In fact, this latter category is precisely the comma category over the functor in question.

As an example, take the given rng R, and make a category E whose objects are rng homomorphisms RS, with S a ring having a multiplicative identity. The morphisms in E between RS1 and RS2 are commutative triangles of the form (RS1,RS2, S1S2) where S1 → S2 is a ring map (which preserves the identity). Note that this is precisely the definition of the comma category of R over the inclusion of unitary rings into rng. The existence of a morphism between RS1 and RS2 implies that S1 is at least as efficient a solution as S2 to our problem: S2 can have more adjoined elements and/or more relations not imposed by axioms than S1. Therefore, the assertion that an object RR* is initial in E, that is, that there is a morphism from it to any other element of E, means that the ring R* is a most efficient solution to our problem.

The two facts that this method of turning rngs into rings is most efficient and formulaic can be expressed simultaneously by saying that it defines an adjoint functor.

Symmetry of optimization problems

Continuing this discussion, suppose we started with the functor F, and posed the following (vague) question: is there a problem to which F is the most efficient solution?

The notion that F is the most efficient solution to the problem posed by G is, in a certain rigorous sense, equivalent to the notion that G poses the most difficult problem that F solves.

This has the intuitive meaning that adjoint functors should occur in pairs, and in fact they do, but this is not trivial from the universal morphism definitions. The equivalent symmetric definitions involving adjunctions and the symmetric language of adjoint functors (we can say either F is left adjoint to G or G is right adjoint to F) have the advantage of making this fact explicit.

Formal definitions

There are various definitions for adjoint functors. Their equivalence is elementary but not at all trivial and in fact highly useful. This article provides several such definitions:

Adjoint functors arise everywhere, in all areas of mathematics. Their full usefulness lies in that the structure in any of these definitions gives rise to the structures in the others via a long but trivial series of deductions. Thus, switching between them makes implicit use of a great deal of tedious details that would otherwise have to be repeated separately in every subject area. For example, naturality and terminality of the counit can be used to prove that any right adjoint functor preserves limits.

Conventions

The theory of adjoints has the terms left and right at its foundation, and there are many components which live in one of two categories C and D which are under consideration. Therefore it can be helpful to choose letters in alphabetical order according to whether they live in the "lefthand" category C or the "righthand" category D, and also to write them down in this order whenever possible.

In this article for example, the letters X, F, f, ε will consistently denote things which live in the category C, the letters Y, G, g, η will consistently denote things which live in the category D, and whenever possible such things will be referred to in order from left to right (a functor F:CD can be thought of as "living" where its outputs are, in C).

Universal morphisms

A functor F : CD is a left adjoint functor if for each object X in C, there exists a terminal morphism from F to X. If, for each object X in C, we choose an object G0X of D for which there is a terminal morphism εX : F(G0X) → X from F to X, then there is a unique functor G : CD such that GX = G0X and εFG(f) = f ∘ εX for f : X a morphism in C; F is then called a left adjoint to G.

A functor G : CD is a right adjoint functor if for each object Y in D, there exists an initial morphism from Y to G. If, for each object Y in D, we choose an object F0Y of C and an initial morphism ηY : YG(F0Y) from Y to G, then there is a unique functor F : CD such that FY = F0Y and GF(g) ∘ ηY = ηg for g : Y a morphism in D; G is then called a right adjoint to F.

Remarks:

It is true, as the terminology implies, that F is left adjoint to G if and only if G is right adjoint to F. This is apparent from the symmetric definitions given below. The definitions via universal morphisms are often useful for establishing that a given functor is left or right adjoint, because they are minimalistic in their requirements. They are also intuitively meaningful in that finding a universal morphism is like solving an optimization problem.

Counit–unit adjunction

A counit–unit adjunction between two categories C and D consists of two functors F : CD and G : CD and two natural transformations

respectively called the counit and the unit of the adjunction (terminology from universal algebra), such that the compositions

are the identity transformations 1F and 1G on F and G respectively.

In this situation we say that F is left adjoint to G and G is right adjoint to F , and may indicate this relationship by writing   , or simply   .

In equation form, the above conditions on (ε,η) are the counit–unit equations

which mean that for each X in C and each Y in D,

.

Note that here denotes identity functors, while above the same symbol was used for identity natural transformations.

These equations are useful in reducing proofs about adjoint functors to algebraic manipulations. They are sometimes called the zig-zag equations because of the appearance of the corresponding string diagrams. A way to remember them is to first write down the nonsensical equation and then fill in either F or G in one of the two simple ways which make the compositions defined.

Note: The use of the prefix "co" in counit here is not consistent with the terminology of limits and colimits, because a colimit satisfies an initial property whereas the counit morphisms will satisfy terminal properties, and dually. The term unit here is borrowed from the theory of monads where it looks like the insertion of the identity 1 into a monoid.

Hom-set adjunction

A hom-set adjunction between two categories C and D consists of two functors F : CD and G : CD and a natural isomorphism

.

This specifies a family of bijections

for all objects X in C and Y in D.

In this situation we say that F is left adjoint to G and G is right adjoint to F , and may indicate this relationship by writing , or simply .

This definition is a logical compromise in that it is somewhat more difficult to satisfy than the universal morphism definitions, and has fewer immediate implications than the counit–unit definition. It is useful because of its obvious symmetry, and as a stepping-stone between the other definitions.

In order to interpret Φ as a natural isomorphism, one must recognize homC(F–, –) and homD(–, G–) as functors. In fact, they are both bifunctors from Dop × C to Set (the category of sets). For details, see the article on hom functors. Explicitly, the naturality of Φ means that for all morphisms f : XX′ in C and all morphisms g : Y Y in D the following diagram commutes:

The vertical arrows in this diagram are those induced by composition with f and g. Formally, Hom(Fg, f) : HomC(FY, X) → HomC(FY′, X′) is given by hf o h o Fg for each h in HomC(FY, X). Hom(g, Gf) is similar.

Adjunctions in full

There are hence numerous functors and natural transformations associated with every adjunction, and only a small portion is sufficient to determine the rest.

An adjunction between categories C and D consists of

An equivalent formulation, where X denotes any object of C and Y denotes any object of D:

For every C-morphism f : FYX, there is a unique D-morphism ΦY, X(f) = g : YGX such that the diagrams below commute, and for every D-morphism g : YGX, there is a unique C-morphism Φ−1Y, X(g) = f : FYX in C such that the diagrams below commute:

From this assertion, one can recover that:

In particular, the equations above allow one to define Φ, ε, and η in terms of any one of the three. However, the adjoint functors F and G alone are in general not sufficient to determine the adjunction. We will demonstrate the equivalence of these situations below.

Universal morphisms induce hom-set adjunction

Given a right adjoint functor G : CD; in the sense of initial morphisms, one may construct the induced hom-set adjunction by doing the following steps.

A similar argument allows one to construct a hom-set adjunction from the terminal morphisms to a left adjoint functor. (The construction that starts with a right adjoint is slightly more common, since the right adjoint in many adjoint pairs is a trivially defined inclusion or forgetful functor.)

counit–unit adjunction induces hom-set adjunction

Given functors F : CD, G : CD, and a counit–unit adjunction (ε, η) : F G, we can construct a hom-set adjunction by finding the natural transformation Φ : homC(F-,-) → homD(-,G-) in the following steps:

The transformations Φ and Ψ are natural because η and ε are natural.
hence ΨΦ is the identity transformation.
hence ΦΨ is the identity transformation. Thus Φ is a natural isomorphism with inverse Φ−1 = Ψ.

Hom-set adjunction induces all of the above

Given functors F : CD, G : CD, and a hom-set adjunction Φ : homC(F-,-) → homD(-,G-), we can construct a counit–unit adjunction

 ,

which defines families of initial and terminal morphisms, in the following steps:

for each f: FYX and g: YGX (which completely determine Φ).
,
and substituting GX for Y and εX = Φ−1GX, X(1GX) for f in the first formula gives the second counit–unit equation
.

History

The idea of an adjoint functor was formulated by Daniel Kan in 1958. Like many of the concepts in category theory, it was suggested by the needs of homological algebra, which was at the time devoted to computations. Those faced with giving tidy, systematic presentations of the subject would have noticed relations such as

hom(F(X), Y) = hom(X, G(Y))

in the category of abelian groups, where F was the functor (i.e. take the tensor product with A), and G was the functor hom(A,–). The use of the equals sign is an abuse of notation; those two groups are not really identical but there is a way of identifying them that is natural. It can be seen to be natural on the basis, firstly, that these are two alternative descriptions of the bilinear mappings from X × A to Y. That is, however, something particular to the case of tensor product. In category theory the 'naturality' of the bijection is subsumed in the concept of a natural isomorphism.

The terminology comes from the Hilbert space idea of adjoint operators T, U with , which is formally similar to the above relation between hom-sets. We say that F is left adjoint to G, and G is right adjoint to F. Note that G may have itself a right adjoint that is quite different from F (see below for an example). The analogy to adjoint maps of Hilbert spaces can be made precise in certain contexts.[1]

Ubiquity

If one starts looking for these adjoint pairs of functors, they turn out to be very common in abstract algebra, and elsewhere as well. The example section below provides evidence of this; furthermore, universal constructions, which may be more familiar to some, give rise to numerous adjoint pairs of functors.

In accordance with the thinking of Saunders Mac Lane, any idea, such as adjoint functors, that occurs widely enough in mathematics should be studied for its own sake.

Concepts can be judged according to their use in solving problems, as well as for their use in building theories. The tension between these two motivations was especially great during the 1950s when category theory was initially developed. Enter Alexander Grothendieck, who used category theory to take compass bearings in other work—in functional analysis, homological algebra and finally algebraic geometry.

It is probably wrong to say that he promoted the adjoint functor concept in isolation: but recognition of the role of adjunction was inherent in Grothendieck's approach. For example, one of his major achievements was the formulation of Serre duality in relative form—loosely, in a continuous family of algebraic varieties. The entire proof turned on the existence of a right adjoint to a certain functor. This is something undeniably abstract, and non-constructive, but also powerful in its own way.

Examples

Free groups

The construction of free groups is a common and illuminating example.

Suppose that F : GrpSet is the functor assigning to each set Y the free group generated by the elements of Y, and that G : GrpSet is the forgetful functor, which assigns to each group X its underlying set. Then F is left adjoint to G:

Terminal morphisms. For each group X, the group FGX is the free group generated freely by GX, the elements of X. Let    be the group homomorphism which sends the generators of FGX to the elements of X they correspond to, which exists by the universal property of free groups. Then each    is a terminal morphism from F to X, because any group homomorphism from a free group FZ to X will factor through    via a unique set map from Z to GX. This means that (F,G) is an adjoint pair.

Initial morphisms. For each set Y, the set GFY is just the underlying set of the free group FY generated by Y. Let    be the set map given by "inclusion of generators". Then each    is an initial morphism from Y to G, because any set map from Y to the underlying set GW of a group will factor through    via a unique group homomorphism from FY to W. This also means that (F,G) is an adjoint pair.

Hom-set adjunction. Maps from the free group FY to a group X correspond precisely to maps from the set Y to the set GX: each homomorphism from FY to X is fully determined by its action on generators. One can verify directly that this correspondence is a natural transformation, which means it is a hom-set adjunction for the pair (F,G).

counit–unit adjunction. One can also verify directly that ε and η are natural. Then, a direct verification that they form a counit–unit adjunction    is as follows:

The first counit–unit equation    says that for each set Y the composition

should be the identity. The intermediate group FGFY is the free group generated freely by the words of the free group FY. (Think of these words as placed in parentheses to indicate that they are independent generators.) The arrow    is the group homomorphism from FY into FGFY sending each generator y of FY to the corresponding word of length one (y) as a generator of FGFY. The arrow    is the group homomorphism from FGFY to FY sending each generator to the word of FY it corresponds to (so this map is "dropping parentheses"). The composition of these maps is indeed the identity on FY.

The second counit–unit equation    says that for each group X the composition

  

should be the identity. The intermediate set GFGX is just the underlying set of FGX. The arrow    is the "inclusion of generators" set map from the set GX to the set GFGX. The arrow    is the set map from GFGX to GX which underlies the group homomorphism sending each generator of FGX to the element of X it corresponds to ("dropping parentheses"). The composition of these maps is indeed the identity on GX.

Free constructions and forgetful functors

Free objects are all examples of a left adjoint to a forgetful functor which assigns to an algebraic object its underlying set. These algebraic free functors have generally the same description as in the detailed description of the free group situation above.

Diagonal functors and limits

Products, fibred products, equalizers, and kernels are all examples of the categorical notion of a limit. Any limit functor is right adjoint to a corresponding diagonal functor (provided the category has the type of limits in question), and the counit of the adjunction provides the defining maps from the limit object (i.e. from the diagonal functor on the limit, in the functor category). Below are some specific examples.

The cartesian product of sets, the product of rings, the product of topological spaces etc. follow the same pattern; it can also be extended in a straightforward manner to more than just two factors. More generally, any type of limit is right adjoint to a diagonal functor.
A suitable variation of this example also shows that the kernel functors for vector spaces and for modules are right adjoints. Analogously, one can show that the cokernel functors for abelian groups, vector spaces and modules are left adjoints.

Colimits and diagonal functors

Coproducts, fibred coproducts, coequalizers, and cokernels are all examples of the categorical notion of a colimit. Any colimit functor is left adjoint to a corresponding diagonal functor (provided the category has the type of colimits in question), and the unit of the adjunction provides the defining maps into the colimit object. Below are some specific examples.

Analogous examples are given by the direct sum of vector spaces and modules, by the free product of groups and by the disjoint union of sets.

Further examples

Algebra

Topology

Posets

Every partially ordered set can be viewed as a category (with a single morphism from x to y if and only if xy). A pair of adjoint functors between two partially ordered sets is called a Galois connection (or, if it is contravariant, an antitone Galois connection). See that article for a number of examples: the case of Galois theory of course is a leading one. Any Galois connection gives rise to closure operators and to inverse order-preserving bijections between the corresponding closed elements.

As is the case for Galois groups, the real interest lies often in refining a correspondence to a duality (i.e. antitone order isomorphism). A treatment of Galois theory along these lines by Kaplansky was influential in the recognition of the general structure here.

The partial order case collapses the adjunction definitions quite noticeably, but can provide several themes:

Category theory

Categorical logic

The role of quantifiers in predicate logics is in forming propositions and also in expressing sophisticated predicates by closing formulas with possibly more variables. For example, consider a predicate with two open variables of sort and . Using a quantifier to close , we can form the set
of all elements of for which there is an to which it is -related, and which itself is characterized by the property . Set theoretic operations like the intersection of two sets directly corresponds to the conjunction of predicates. In categorical logic, a subfield of topos theory, quantifiers are identified with adjoints to the pullback functor. Such a realization can be seen in analogy to the discussion of propositional logic using set theory but, interestingly, the general definition make for a richer range of logics.
So consider an object in a category with pullbacks. Any morphism induces a functor
on the category that is the preorder of subobjects. It maps subobjects of (technically: monomorphism classes of ) to the pullback . If this functor has a left- or right adjoint, they are called and , respectively.[3] They both map from back to . Very roughly, given a domain to quantify a relation expressed via over, the functor/quantifier closes in and returns the thereby specified subset of .
Example: In , the category of sets and functions, the canonical subobjects are the subset (or rather their canonical injections). The pullback of an injection of a subset into along is characterized as the largest set which knows all about and the injection of into . It therefore turns out to be (in bijection with) the inverse image .
For , let us figure out the left adjoint, which is defined via
which here just means
.
Consider . We see . Conversely, If for an we also have , then clearly . So implies . We conclude that left adjoint to the inverse image functor is given by the direct image. Here is a characterization of this result, which matches more the logical interpretation: The image of under is the full set of 's, such that is non-empty. This works because it neglects exactly those which are in the complement of . So
Put this in analogy to our motivation .
The right adjoint to the inverse image functor is given (without doing the computation here) by
The subset of is characterized as the full set of 's with the property that the inverse image of with respect to is fully contained within . Note how the predicate determining the set is the same as above, except that is replaced by .
See also powerset.

Properties

Existence

Not every functor G : CD admits a left adjoint. If C is a complete category, then the functors with left adjoints can be characterized by the adjoint functor theorem of Peter J. Freyd: G has a left adjoint if and only if it is continuous and a certain smallness condition is satisfied: for every object Y of D there exists a family of morphisms

fi : YG(Xi)

where the indices i come from a set I, not a proper class, such that every morphism

h : YG(X)

can be written as

h = G(t) o fi

for some i in I and some morphism

t : XiX in C.

An analogous statement characterizes those functors with a right adjoint.

Uniqueness

If the functor F : CD has two right adjoints G and G′, then G and G′ are naturally isomorphic. The same is true for left adjoints.

Conversely, if F is left adjoint to G, and G is naturally isomorphic to G′ then F is also left adjoint to G′. More generally, if 〈F, G, ε, η〉 is an adjunction (with counit–unit (ε,η)) and

σ : FF
τ : GG

are natural isomorphisms then 〈F′, G′, ε′, η′〉 is an adjunction where

Here denotes vertical composition of natural transformations, and denotes horizontal composition.

Composition

Adjunctions can be composed in a natural fashion. Specifically, if 〈F, G, ε, η〉 is an adjunction between C and D and 〈F′, G′, ε′, η′〉 is an adjunction between D and E then the functor

is left adjoint to

More precisely, there is an adjunction between FF and G G′ with unit and counit given by the compositions:

This new adjunction is called the composition of the two given adjunctions.

One can then form a category whose objects are all small categories and whose morphisms are adjunctions.

Limit preservation

The most important property of adjoints is their continuity: every functor that has a left adjoint (and therefore is a right adjoint) is continuous (i.e. commutes with limits in the category theoretical sense); every functor that has a right adjoint (and therefore is a left adjoint) is cocontinuous (i.e. commutes with colimits).

Since many common constructions in mathematics are limits or colimits, this provides a wealth of information. For example:

Additivity

If C and D are preadditive categories and F : CD is an additive functor with a right adjoint G : CD, then G is also an additive functor and the hom-set bijections

are, in fact, isomorphisms of abelian groups. Dually, if G is additive with a left adjoint F, then F is also additive.

Moreover, if both C and D are additive categories (i.e. preadditive categories with all finite biproducts), then any pair of adjoint functors between them are automatically additive.

Relationships

Universal constructions

As stated earlier, an adjunction between categories C and D gives rise to a family of universal morphisms, one for each object in C and one for each object in D. Conversely, if there exists a universal morphism to a functor G : CD from every object of D, then G has a left adjoint.

However, universal constructions are more general than adjoint functors: a universal construction is like an optimization problem; it gives rise to an adjoint pair if and only if this problem has a solution for every object of D (equivalently, every object of C).

Equivalences of categories

If a functor F: CD is one half of an equivalence of categories then it is the left adjoint in an adjoint equivalence of categories, i.e. an adjunction whose unit and counit are isomorphisms.

Every adjunction 〈F, G, ε, η〉 extends an equivalence of certain subcategories. Define C1 as the full subcategory of C consisting of those objects X of C for which εX is an isomorphism, and define D1 as the full subcategory of D consisting of those objects Y of D for which ηY is an isomorphism. Then F and G can be restricted to D1 and C1 and yield inverse equivalences of these subcategories.

In a sense, then, adjoints are "generalized" inverses. Note however that a right inverse of F (i.e. a functor G such that FG is naturally isomorphic to 1D) need not be a right (or left) adjoint of F. Adjoints generalize two-sided inverses.

Monads

Every adjunction 〈F, G, ε, η〉 gives rise to an associated monadT, η, μ〉 in the category D. The functor

is given by T = GF. The unit of the monad

is just the unit η of the adjunction and the multiplication transformation

is given by μ = GεF. Dually, the triple 〈FG, ε, FηG〉 defines a comonad in C.

Every monad arises from some adjunction—in fact, typically from many adjunctions—in the above fashion. Two constructions, called the category of Eilenberg–Moore algebras and the Kleisli category are two extremal solutions to the problem of constructing an adjunction that gives rise to a given monad.

Notes

  1. arXiv.org: John C. Baez Higher-Dimensional Algebra II: 2-Hilbert Spaces.
  2. William Lawvere, Adjointness in foundations, Dialectica, 1969, available here. The notation is different nowadays; an easier introduction by Peter Smith in these lecture notes, which also attribute the concept to the article cited.
  3. Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 See page 58

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.