Adjunctions

Adjoints

For a fixed field , consider the functors

is the forgetful functor which takes the vector field to the corresponding set of vectors, while takes to a basis. For set , is the finite formal set of linear combinations , with scalar coefficents , and . For vector space , extends to , and hence there is a bijection

Setting , naturality in are obtained from the following diagram:

As another example, consider the free category over a small graph , , and given by; it is related to the forgetful functor since extends to . Moreover is a natural isomorphism:

In the category of small sets, the function , a function of two variables, can be considered as , a function of one variable, so that the following bijection holds:

For modules in a commutative ring , a similar bijection holds:

The adjuction from category to category , where are functors, is given by the triple

while is a function such that:

Here, is the bifunctor:

For all , it satisfies the diagrams:

Here, .

An adjunction can also be described without talking about hom-sets, directly in terms of arrows. There is a bijection which assigns to each of the arrows arrows , the right adjunct of , in such a way that the natural compositions hold:

is said to be right adjoint for , and is the left adjoint for .

Every adjunction yields a universal arrow. Call the hom-set that contains the identity the -image of . is a universal arrow by Yoneda's proposition:

The adjunction gives such a universal arrow for every object . The function is an NT . We obtain the following diagrams:

where and .

The bijection can be expressed as:

and we obtain:

To summarize, every adjunction determines:

  1. A natural transform such that for each object , the arrow is universal from to , and right adjunct is detemined by
  2. Dually, another natural transform such that every arrow is universal from to , and left adjunct is determined by

Moreover, the following composites are identities:

is termed unit and is termed counit of the adjunction.

The adjunct is completely determined by one of the following items:

  1. Functors and NT such that every is universal. Then, .
  2. Functor , object , and universal arrow , from to . Then, functor has object function and, on arrow , by .
  3. Functors , and NT such that every is universal. Then, .
  4. Functor , object , and universal arrow , from to .
  5. Functors and NTs and .

Due to (v), we can also write the adjunct as .

To prove (i), or its dual (iii), notice:

To prove (ii), or its dual (iv), notice:

To prove (v), given , define:

by for all , and for all . Since is a functor and an NT, we have:

Now, since , is identity. Dually, is also identity, and therefore, is a bijection with inverse . It is clearly natural, and hence an adjunction.

The result is very useful; for instance, (iii) and (iv) let us construct an adjuction whenever we have a universal arrow from or to all objects in a category. For example, has finite products when for each pair , when there is a universal arrow to . From the result, we conclude that the function giving a product object is actually a functor , and this functor is right adjoint to :

Using the definition of arrows in , we get:

The counit of this adjuction is ; it is thus just projections of the product. The adjunction sends the pair to the pair ; this is the way in which the adjuction is determined by the counit .

Similarly, if the category has coproducts , they define the coproduct functor which is left adjoint to :

Similar arguments hold for limits. Proving universality is an easy way of showing that adjoints exist.

Part (v) describes all adjunctions by two simple identities:

Any two left adjoints of the are naturally isomorphic. This follows immediately from the fact that universal arrows are unique upto isomorphism.

A functor is said to have a left adjoint iff for every , the functor is representable as a functor of . If is a representation of this functor, then is the object function of the left adjoint of , for which is natural in and gives the adjunction. This is simply a restatement of (ii).

If additive functor between -categories has left adjoint , then is additive, and the adjunction bijections

are isomorphisms of abelian groups for all . This can be shown as follows. If is the unit of the adjunction, then may be written as for any . If also , additivity of gives:

Therefore is a morphism of abelian groups. Next, take in . Since is nautural,

On the other hand, since is additive,

The equality of these two results, along with the universal property of show that . Hence is additive. Dually, right adjoint of an additive functor is additive.

Reflective subcategories

Let be the NT induced by the arrow of . Then is monic iff is epi, and is epi iff is a split monic. Note that is the bijection given by the Yoneda lemma. Observe that for functors , the NT is epi in iff every component is epi in for . To show this, notice that for , . Hence the first result is just the definition of an epi . If is epi, there is an such that , so has a left inverse. The converse is immediate. Now apply Yoneda lemma to the NT:

It is determined by the image of , which is exactly the definition of counit . But is an isomorphism, hence this NT is monic or epi, respectively, whenver is injective or surjective; i.e. when is full or faithful.

For an adjunction , is faithful iff every component of the counit is epi, and is full iff every is split monic. Hence, is full and faithful iff each is an isomorphism . This follows immediately from the last result.

A subcategory of is reflective in when the inclusion function has left adjoint . The functor may be called a reflector, and the adjunction a reflection of in subcategory . Since the inclusion functor is always faithful, the counit of the reflection is always epi. A reflection can be described in terms of the composite functor ; indeed is reflective in iff there is a functor with values in the subcategory and a bijection of sets:

natural in . A reflection can also be described in terms of universal arrows: is reflective iff to each , there is an object of the subcategory , and the arrow such that every arrow has the form for of . is then the object function of a functor with values in . If a full subcategory is reflective in , then each object is isommorphic to , and hence for all . Dually, is coreflective in when the inclusion functor has right adjoint.

As an example, is reflective in , for if is the usual factor-commutator group of group , then for abelian, and is full in . As another example, consider the category of metric spaces with arrows uniformly continuous functions. The full subcategory of complete metric spaces is reflective; the reflector sends each metric space to its completion. As a third example, consider the category of all completely regular Hausdorff spaces with arrows continuous functions. The full subcategory of this category is reflective; the reflector sends each completely regular space to its Stone-Čech compatification.

A coreflective subcategory of is the full subcategory of all torsion abelian groups; the coreflector sends each abelian group to the subgroup of all elements of finite order in .

Equivalence of categories

A functor is an isomorphism of categories when there is a functor such that and . In this case, the identity NTs and make into an adjunction. In other words, the two-sided inverse of a functor is a left-adjoint of ; is also a right-adjoint of .

In any category , the skeleton of is any full subcategory , such that every object of is isomorphic to exactly one object in . Then is equivalent to , and any functor is an equivalence of categories, for we can select to each an isomorphism , with an object of . We can then make a functor in exactly one way, so that will become a natural isomorphism . Moreover, , so is indeed an equivalence. This discussion can be summarized as: A category is equivalent to any of its skeletons. As an example, the category of all finite sets has as a skeleton the full subcategory with objects all finite ordinals. A category is called skeletal when any two isomorphic objects are identical; i.e. when a category is its own skeleton.

An adjoint equivalence of categories is an adjoint such that both units and counits are the natural isomorphisms . Then are also identities, and the triangular identities and can be written as and . These state that are adjunctions with unit and counit . Thus, in an adjoint equivalence , the functor is left adjoint of with unit , and is right adjoint of at the same time, with unit .

The following properties about functor are equivalent:

  1. is an equivalence of categories.
  2. is part of the adjoint equivalence .
  3. is full and faithful, and each object is isomorphic to for some object .

Trivially, (b) implies (a). To prove that (a) implies (c), note that shows that each has the form for an . The natural isomorphism gives for each the commutative diagram:

It follows that is faithful. Symmetrically, proves that is faithful. To show that is full, consider any , and set . Then the above square commutes when is replaced by , so . Since is faithful, and , it implies that is full. To prove that (c) implies (b), we must construct from a left adjoint . For each , choose some object and the isomorphism :

For every arrow , the composite has the form because is full; this is unique because is faithful. In other words, , for unique , so is universal from to . Therefore, can be made a functor in exactly one way so is natural, and then is left adjoint of with unit the isomorphism . As with any adjunction, by putting in the above diagram. Thus, is invertible. Since is full and faithful, the counit is also invertible. Therefore, is an adjunction equivalence.

If is a full subcategory of and every is isomorphic to some object of , then the insertion is an equivalence and is part of the adjoint equivalence with counit identity. Therefore is reflective in . To show this, in the previous result, let be a full subcategory of and is the insertion. For objects , we can choose , and the identity. Then and hence for all , completing the proof.

Duality theorems in functional analysis are often instances of equivalences. For example, let be the category of compact topological abelian groups, and let assign to every such group its character group , consisting of all continuous homomorphisms . The Pontrjagin duality theorem asserts that is an equivalence of categories. Similarly, the Gelfand-Naimark theorem states that the functor that assigns to each compact Hausdorff space its abelian -algebra of continuous complex-valued functions is an equivalence of categories.

Adjunctions for preorders

Preorders may be regarded as categories, with functors all order-preserving functions. Then order-reversing function from to is the functor .

Let be two preorders and and be two order-preserving functions. Then , regarded as a functor, is left-adjoint to iff for all :

A pair of order-preserving functions satisfying this is called the Galios connection from to . When this is the case, there is exactly one adjunction making the left adjoint of . For all , and ; hence also:

To prove this, notice that becomes a category when there is exactly one arrow whenver . Thus, the first condition states that there is a bijection . Since each hom-set has exactly one element, this bijection is natural. The unit of the adjunction is the inequality and the counit is . Thus, the second condition is the triangular identity connecting unit and counit. In the convenient case when are posets, these conditions become .

As a fundamental example, consider the group acting on a set , by for all . Take , the powersets. Let , ; in other words, is the subgroup of which fixes all points and is the set of fixed points of automorphisms of . Then, in , iff for all , which in turn only holds if in . Therefore, form an adjoint pair or Galios connection.

As another example, consider sets and powersets . For each function , the direct image is order-preserving, and is hence is the corresponding functor. The inverse image is also order preserving, and hence is the corresponding functor. Hence, the direct image is left-adjoint to the inverse image .

As yet another example, consider Boolean algebras. Let be a category. The diagonal functor has right adjoint , with , and left adjoint , with . If is a fixed subset of , intersection with is the functor . Since if , where is the complement of in , right adjoint of is . Thus, construction of suitable adjoints leads to . Now, let be a projection from sets . Each subset determines subsets of by:

They arise from by applying universal and existential quantifiers. Also, is the direct image of under projection . Now, for all subsets , we have:

This states that inverse image operation has left adjoint and right adjoint . In this sense, both quantifiers and can be interpreted as adjoints. This also has the following geometric interpretation: is the cylinder over the base , is the projection of onto base , is the largest subset such that the cylinder is contained wholly within .

Cartesian closed categories

To assert that a category has finite products and coproducts is to say that the category has products, terminal, initial, and coproducts; thus the functors and have both left and right adjoints. Indeed, left adjoints give initial object and coproduct, while right adjoints give terminal object and product.

A category is termed cartesian closed if the following functors have specified right adjoints:

These right adjoints are:

To specify the first is to specify the terminal object . To specify the second is to specify, for each pair of objects , the product object along with projections : the projections consistite the counit of the adjunction, and is a bifunctor. The third specifies , a right adjoint with bijection:

natural in and . By the parameter theorem, is the object functor of bifunctor . Specifying the adjunction amounts to specifying specifying for all , the arrow:

which is natural in , and universal from to . We call this the evaluation map. It amounts to ordinary evaluation in the following cases:

  1. is a cartesian closed category with .
  2. is a cartesian closed category with the functor category.

A closely related example of adjunctions is the functor:

which has right adjoint ; the adjunct is determined by counit given by the evaluation.

Transformations of adjoints

Next, we turn our attention to maps between adjunctions. Given two adjunctions:

we define the map between the two adjunctions by two functors and such that the following squares commute:

and such that the diagram of adjunctions and hom-sets commutes for all :

Here, is the map given by the functor applied to each .

The above condition is equivalent to and . To prove this, set and chase around the commutative diagram to get the units , and the equality:

where . Conversely, given the identity of the NTs, the definition of adjunctions by their units gives the required result. The case of counits is dual to this case.

Next, consider two adjunctions between the same two categories:

The following two NTs are said to be conjugate when the diagram commutes for every pair of objects :

Given the above two adjunctions, the NTs are said to be conjugate iff the following diagrams commute:

Also, given the NT , there is a unique such that is conjugate. To prove this, consider with :

Start with the identity arrow on the top right, use the description of by unit and counit, and chase the diagram around as follows:

This yields and its dual. A slightly different chase yields and its dual:

Next, suppose are not given. Then, applying Yoneda lemma to yields a unique family of arrows for which commutes, and this family is an NT. Since each is universal from to , there is also a unique family of arrows such that commutes. Since implies , ; in other words, if makes commute, it also makes commute. Therefore implies . Given , there is immediately a unique NT for which commutes; since implies , . Hence solutions of of are necessarily natural; moreover implies , completing the proof.

The vertical compositions of:

are given by

For two given categories , we have a new category , the category of adjunctions from to ; its objects are adjunctions and arrows are conjugate pairs with composition just noted. There are also two forgetful functors to the ordinary functor categories:

A typical example is for :

If is a function between the two sets, then is a NT of functors . Its conjugate is the NT ; this is in the reverse direction as is covariant in and contravariant in . We may call the above an adjuction with parameter .

Given a bifunctor , assume for each , that has a right adjoint via the adjunction:

natural in and . Then, there is a unique way to assign to each arrow of , and each object , an arrow of so that becomes a bifunctor for which the bijection of the adjunction is natural in . This assignment of arrows to may also be described as the unique way to make an NT conjugate to . To prove this, first notice that the bijection implies the following commutative diagram:

This states precisely that must be chosen as the conjugate to . By the previous result, there is a unique choice of to realize this - the condition for conjugacy may be expressed in any of the five ways previously stated. For a second arrow , the uniqueness of choice of conjugates shows for that , so is a functor and is a bifunctor, as required. Dually, given a bifunctor , where each has right adjoint , there is a unique way to make a bifunctor .

Composition of adjoints

Two adjunctions compose to give a single adjunction as follows. Given two adjunctions:

the composite functors yield the adjunction:

We prove it by noticing that, with hom-sets, the two given adjunctions yield a composite isomorphism, natural for all :

This makes the composite left adjoint to . Setting , and applying these two isomorphisms to the identity , we find that the unit of composite adjunction is , so is , as asserted. The dual argument yields counit , as required.

Using this composition, we may form a category , whose objects are small categories , and whose arrows are adjunctions composed as above; the identity arrow is . This category has additional structure; each hom-set may be regarded as a category; the category of adjunctions has already been described. Its objects are these adjunctions, and arrows are conjugate pairs under "vertical" composition.

Given two conjugate pairs:

The "horizontal" composite NTs yield a conjugate pair , of NTs for the conjugate adjunction. The proof may be visualized by the commutative diagram of hom-sets:

Moreover, this operation of horizontal composition is a bifunctor:

This means that is a two-dimensional category as is .

Subsets and characteristic functions

The characteristic function of a subset is the two-valued function on with values:

Put differently, is the simplest non-trivial subset. An arbitrary subset can be mapped into this simple subset by , as defined. This produces the pullback map:

These appear in probability theory; in logic, are "truth values", and "truth" is represented by . The monomorphism is termed subobject classifier for the category of sets. A subobject classifier for the category with terminal object is defined to be , such that every monomorphism in is a pullback of in a unique way. In other words, for each , there exists a pullback square:

The top horizontal arrow is the unique map to terminal object , and the lower horizontal arrow acts as the characteristic function of subobject , while the universal morphism may be called "truth".

For example, take to be a category of functions . Here a monomorphism is a function between a pair of subsets and , such that for all . This means that the following diagram commutes:

In this case, there are three types of elements in : those , those , but with , and those . We may then define a characteristic function with three values by setting:

Again, this prescription provides a pullback map:

of objects and in the category of functions, whose function is given by . Thus, the inclusion is the subobject classifier for the category of functions.

As an example, consider the arrow category as a category with two objects and , and only one non-identity arrow . Thus, an ordinary function is the same thing as a functor . Hence, we have constructed above the functor category for .

Categories like sets

An elementary topos is defined to be a category with the following properties:

  1. has all finite limits.
  2. has a subobject classifier.
  3. is cartesian closed.

Requiring to be cartesian closed means requring each functor "product with b" (i.e. ) has for each a right adjoint so that:

In other words, has exponentials.

The category of all small sets is a topos, as is , the set of all contravariant functors on small category . Such a functor is called a presheaf. This is a reference to topology where is the set of all open subsets of topological space ; in this case, presheaf assigns to each a set , with functorial properties for continuous maps . If is the set of continuous real-valued functions on , it is said to be a sheaf. A topological structure is essentially described by its topos of sheaves of . Various logical properties are reflected in subobject classifiers of a topos. Suitable toposes can replace the category of sets as a foundation for mathematics.