HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, specifically
category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
, adjunction is a relationship that two
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
s may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are known as adjoint functors, one being the left adjoint and the other the right adjoint. Pairs of adjoint functors are ubiquitous in mathematics and often arise from constructions of "optimal solutions" to certain problems (i.e., constructions of objects having a certain
universal property In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
), such as the construction of a free group on a set in algebra, or the construction of the Stone–Čech compactification of a
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
in topology. By definition, an adjunction between categories \mathcal and \mathcal is a pair of functors (assumed to be covariant) :F: \mathcal \rightarrow \mathcal   and   G: \mathcal \rightarrow \mathcal and, for all objects X in \mathcal and Y in \mathcal a
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
between the respective morphism sets :\mathrm_(FY,X) \cong \mathrm_(Y,GX) such that this family of bijections is
natural Nature, in the broadest sense, is the physical world or universe. "Nature" can refer to the phenomena of the physical world, and also to life in general. The study of nature is a large, if not the only, part of science. Although humans ar ...
in X and Y. Naturality here means that there are natural isomorphisms between the pair of functors \mathcal(F-,X) : \mathcal \to \mathrm and \mathcal(-,GX) : \mathcal \to \mathrm for a fixed X in \mathcal, and also the pair of functors \mathcal(FY,-) : \mathcal \to \mathrm and \mathcal(Y,G-) : \mathcal \to \mathrm for a fixed Y in \mathcal. The functor F is called a left adjoint functor or left adjoint to G, while G is called a right adjoint functor or right adjoint to F. An adjunction between categories \mathcal and \mathcal is somewhat akin to a "weak form" of an equivalence between \mathcal and \mathcal, and indeed every equivalence is an adjunction. In many situations, an adjunction can be "upgraded" to an equivalence, by a suitable natural modification of the involved categories and functors.


Terminology and notation

The terms '' adjoint'' and '' adjunct'' are both used, and are
cognate In historical linguistics, cognates or lexical cognates are sets of words in different languages that have been inherited in direct descent from an etymological ancestor in a common parent language. Because language change can have radical ef ...
s: one is taken directly from Latin, the other from Latin via French. In the classic text ''Categories for the working mathematician'', Mac Lane makes a distinction between the two. Given a family : \varphi_: \mathrm_(FY,X) \cong \mathrm_(Y,GX) of hom-set bijections, we call \varphi an adjunction or an adjunction between F and G . If f is an arrow in \mathrm_(FY,X) , \varphi f is the right adjunct of f (p. 81). The functor 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.) In general, the phrases " F is a left adjoint" and " F has a right adjoint" are equivalent. We call F a left adjoint because it is applied to the left argument of \mathrm_, and G a right adjoint because it is applied to the right argument of \mathrm_. If ''F'' is left adjoint to ''G'', we also write :F\dashv G. The terminology comes from the
Hilbert space In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
idea of adjoint operators T, U with \langle Ty,x\rangle = \langle y,Ux\rangle, which is formally similar to the above relation between hom-sets. The analogy to adjoint maps of Hilbert spaces can be made precise in certain contexts.


Introduction and Motivation

Common mathematical constructions are very often adjoint functors. Consequently, general theorems about left/right adjoint functors encode the details of many useful and otherwise non-trivial results. Such general theorems include the equivalence of the various definitions of adjoint functors, the uniqueness of a right adjoint for a given left adjoint, the fact that left/right adjoint functors respectively preserve colimits/limits (which are also found in every area of mathematics), and the general adjoint functor theorems giving conditions under which a given functor is a left/right adjoint.


Solutions to optimization problems

In a sense, 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 In algebra, ring theory is the study of rings—algebraic structures in which addition and multiplication are defined and have similar properties to those operations defined for the integers. Ring theory studies the structure of rings, their r ...
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 In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
, and is ''formulaic'' if it defines a
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
. Universal properties come in two types: initial properties and terminal properties. Since these are dual 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'', so that the problem at hand corresponds to finding an
initial object In category theory, a branch of mathematics, an initial object of a category is an object in such that for every object in , there exists precisely one morphism . The dual notion is that of a terminal object (also called terminal element): ...
of ''E''. This has an advantage that the ''optimization''—the sense that the process finds the ''most efficient'' solution—means something rigorous and recognisable, rather like the attainment of a
supremum In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest ...
. 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. Back to our example: take the given rng ''R'', and make a category ''E'' whose ''objects'' are rng homomorphisms ''R'' → ''S'', with ''S'' a ring having a multiplicative identity. The ''morphisms'' in ''E'' between ''R'' → ''S''1 and ''R'' → ''S''2 are commutative triangles of the form (''R'' → ''S''1, ''R'' → ''S''2, ''S''1 → ''S''2) where S1 → S2 is a ring map (which preserves the identity). (Note that this is precisely the definition of the
comma category In mathematics, a comma category (a special case being a slice category) is a construction in category theory. It provides another way of looking at morphisms: instead of simply relating objects of a category to one another, morphisms become obj ...
of ''R'' over the inclusion of unitary rings into rng.) The existence of a morphism between ''R'' → ''S''1 and ''R'' → ''S''2 implies that ''S''1 is at least as efficient a solution as ''S''2 to our problem: ''S''2 can have more adjoined elements and/or more relations not imposed by axioms than ''S''1. Therefore, the assertion that an object ''R'' → ''R*'' 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''. More explicitly: Let ''F'' denote the above process of adjoining an identity to a rng, so ''F''(''R'')=''R*''. Let ''G'' denote the process of “forgetting″ whether a ring ''S'' has an identity and considering it simply as a rng, so essentially ''G''(''S'')=''S''. Then ''F'' is the ''left adjoint functor'' of ''G''. Note however that we haven't actually constructed ''R*'' yet; it is an important and not altogether trivial algebraic fact that such a left adjoint functor ''R'' → ''R*'' actually exists.


Symmetry of optimization problems

It is also possible to ''start'' with the functor ''F'', and pose 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 gives the intuition behind the fact that adjoint functors occur in pairs: if ''F'' is left adjoint to ''G'', then ''G'' is right adjoint to ''F''.


Formal definitions

There are various equivalent definitions for adjoint functors: * The definitions via universal morphisms are easy to state, and require minimal verifications when constructing an adjoint functor or proving two functors are adjoint. They are also the most analogous to our intuition involving optimizations. * The definition via hom-sets makes symmetry the most apparent, and is the reason for using the word ''adjoint''. * The definition via counit–unit adjunction is convenient for proofs about functors which are known to be adjoint, because they provide formulas that can be directly manipulated. The equivalency of these definitions is quite useful. Adjoint functors arise everywhere, in all areas of mathematics. Since the structure in any of these definitions gives rise to the structures in the others, switching between them makes implicit use of many details that would otherwise have to be repeated separately in every subject area.


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'' : ''D'' → ''C'' can be thought of as "living" where its outputs are, in ''C'').


Definition via universal morphisms

By definition, a functor F: D \to C is a left adjoint functor if for each object X in C there exists a
universal morphism In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently f ...
from F to X. Spelled out, this means that for each object X in C there exists an object G(X) in D and a morphism \epsilon_X: F(G(X)) \to X such that for every object Y in D and every morphism f: F(Y) \to X there exists a unique morphism g: Y \to G(X) with \epsilon_X \circ F(g) = f. The latter equation is expressed by the following
commutative diagram 350px, The commutative diagram used in the proof of the five lemma. In mathematics, and especially in category theory, a commutative diagram is a diagram such that all directed paths in the diagram with the same start and endpoints lead to the s ...
: In this situation, one can show that G can be turned into a functor G : C \to D in a unique way such that \epsilon_X \circ F(G(f)) = f \circ \epsilon_ for all morphisms f: X' \to X in C; F is then called a left adjoint to G. Similarly, we may define right-adjoint functors. A functor G: C \to D is a right adjoint functor if for each object Y in D, there exists a
universal morphism In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently f ...
from Y to G. Spelled out, this means that for each object Y in D, there exists an object F(Y) in C and a morphism \eta_Y: Y \to G(F(Y)) such that for every object X in C and every morphism g: Y \to G(X) there exists a unique morphism f: F(Y) \to X with G(f) \circ \eta_Y = g. Again, this F can be uniquely turned into a functor F: D \to C such that G(F(g)) \circ \eta_Y = \eta_ \circ g for g: Y \to Y' a morphism in D; G is then called a right adjoint to F. It is true, as the terminology implies, that F is left adjoint to G if and only if G is right adjoint to F. These 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.


Definition via Hom-set adjunction

A
hom-set In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
adjunction between two categories ''C'' and ''D'' consists of two
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
s ''F'' : ''D'' → ''C'' and and a
natural isomorphism In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
:\Phi:\mathrm_C(F-,-) \to \mathrm_D(-,G-). This specifies a family of bijections :\Phi_:\mathrm_C(FY,X) \to \mathrm_D(Y,GX) for all objects ''X'' in ''C'' and ''Y'' in ''D''. In this situation, ''F'' is left adjoint to ''G'' and ''G'' is right adjoint to ''F'' . This definition is a logical compromise in that it is 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 and as functors. In fact, they are both bifunctors from to Set (the
category of sets In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition o ...
). For details, see the article on
hom functor In mathematics, specifically in category theory, hom-sets (i.e. sets of morphisms between objects) give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applications in category theory and ...
s. Explicitly, the naturality of Φ means that for all
morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
s in ''C'' and all morphisms in ''D'' the following diagram commutes: The vertical arrows in this diagram are those induced by composition. Formally, Hom(''Fg'', ''f'') : HomC(''FY'', ''X'') → HomC(''FY′'', ''X′'') is given by ''h'' → ''f o h o Fg'' for each ''h'' in HomC(''FY'', ''X''). Hom(''g'', ''Gf'') is similar.


Definition via counit–unit adjunction

A counit–unit adjunction between two categories ''C'' and ''D'' consists of two
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
s ''F'' : ''D'' → ''C'' and ''G'' : ''C'' → ''D'' and two
natural transformation In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
s :\begin \varepsilon &: FG \to 1_ \\ \eta &: 1_ \to GF\end respectively called the counit and the unit of the adjunction (terminology from
universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular groups as the object of study ...
), such that the compositions :F\xrightarrowFGF\xrightarrowF :G\xrightarrowGFG\xrightarrowG are the identity transformations 1''F'' and 1''G'' 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  (\varepsilon,\eta):F\dashv G , or simply  F\dashv G . In equation form, the above conditions on (''ε'',''η'') are the counit–unit equations :\begin 1_F &= \varepsilon F\circ F\eta\\ 1_G &= G\varepsilon \circ \eta G \end which mean that for each ''X'' in ''C'' and each ''Y'' in ''D'', :\begin 1_ &= \varepsilon_\circ F(\eta_Y) \\ 1_ &= G(\varepsilon_X)\circ\eta_ \end. Note that 1_ denotes the identify functor on the category \mathcal C, 1_F denotes the identity natural transformation from the functor ''F'' to itself, and 1_ denotes the identity morphism of the object ''FY''. These equations are useful in reducing proofs about adjoint functors to algebraic manipulations. They are sometimes called the ''triangle identities'', or sometimes 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 1=\varepsilon\circ\eta 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.


History

The idea of adjoint functors was introduced by Daniel Kan in 1958. Like many of the concepts in category theory, it was suggested by the needs of
homological algebra Homological algebra is the branch of mathematics that studies homology in a general algebraic setting. It is a relatively young discipline, whose origins can be traced to investigations in combinatorial topology (a precursor to algebraic topolo ...
, 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 group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is comm ...
s, where ''F'' was the functor - \otimes A (i.e. take the
tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
with ''A''), and ''G'' was the functor hom(''A'',–) (this is now known as the tensor-hom adjunction). The use of the ''equals'' sign is an
abuse of notation In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not entirely formally correct, but which might help simplify the exposition or suggest the correct intuition (while possibly minimizing errors a ...
; 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 In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
.


Ubiquity

If one starts looking for these adjoint pairs of functors, they turn out to be very common in
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
, 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 Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg. Early life and education Mac Lane was born in Norwich, Connecticut, near where his family lived in Taftville ...
, 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 Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defi ...
,
homological algebra Homological algebra is the branch of mathematics that studies homology in a general algebraic setting. It is a relatively young discipline, whose origins can be traced to investigations in combinatorial topology (a precursor to algebraic topolo ...
and finally
algebraic geometry Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
. 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 algebraic geometry, a branch of mathematics, Serre duality is a duality for the coherent sheaf cohomology of algebraic varieties, proved by Jean-Pierre Serre. The basic version applies to vector bundles on a smooth projective variety, but Al ...
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 group In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
s is a common and illuminating example. Let ''F'' :
Set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
Grp be the functor assigning to each set ''Y'' the
free group In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
generated by the elements of ''Y'', and let ''G'' : Grp → Set be the
forgetful functor In mathematics, in the area of category theory, a forgetful functor (also known as a stripping functor) 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given sign ...
, which assigns to each group ''X'' its underlying set. Then ''F'' is left adjoint to ''G'': Initial morphisms. For each set ''Y'', the set ''GFY'' is just the underlying set of the free group ''FY'' generated by ''Y''. Let  \eta_Y:Y\to GFY  be the set map given by "inclusion of generators". This is an initial morphism from ''Y'' to ''G'', because any set map from ''Y'' to the underlying set ''GW'' of some group ''W'' will factor through  \eta_Y:Y\to GFY  via a unique group homomorphism from ''FY'' to ''W''. This is precisely the universal property of the free group on ''Y''. Terminal morphisms. For each group ''X'', the group ''FGX'' is the free group generated freely by ''GX'', the elements of ''X''. Let  \varepsilon_X:FGX\to X  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  (GX,\varepsilon_X)  is a terminal morphism from ''F'' to ''X'', because any group homomorphism from a free group ''FZ'' to ''X'' will factor through  \varepsilon_X:FGX\to X  via a unique set map from ''Z'' to ''GX''. This means that (''F'',''G'') is an adjoint pair. Hom-set adjunction. Group homomorphisms 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, another restatement of the universal property of free groups. 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  (\varepsilon,\eta):F\dashv G  is as follows: The first counit–unit equation  1_F = \varepsilon F\circ F\eta  says that for each set ''Y'' the composition :FY\xrightarrowFGFY\xrightarrowFY 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  F(\eta_Y)  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  \varepsilon_  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  1_G = G\varepsilon \circ \eta G  says that for each group ''X'' the composition : GX\xrightarrowGFGX\xrightarrowGX  should be the identity. The intermediate set ''GFGX'' is just the underlying set of ''FGX''. The arrow  \eta_  is the "inclusion of generators" set map from the set ''GX'' to the set ''GFGX''. The arrow  G(\varepsilon_X)  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 object In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. Informally, a free object over a set ''A'' can be thought of as being a "generic" algebraic structure over ''A'': the only equations that hold between eleme ...
s are all examples of a left adjoint to a
forgetful functor In mathematics, in the area of category theory, a forgetful functor (also known as a stripping functor) 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given sign ...
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 Limit or Limits may refer to: Arts and media * ''Limit'' (manga), a manga by Keiko Suenobu * ''Limit'' (film), a South Korean film * Limit (music), a way to characterize harmony * "Limit" (song), a 2016 single by Luna Sea * "Limits", a 2019 ...
. 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. * Products Let Π : Grp2 → Grp the functor which assigns to each pair (''X''1, ''X2'') the product group ''X''1×''X''2, and let Δ : Grp → Grp2 be the diagonal functor which assigns to every group ''X'' the pair (''X'', ''X'') in the product category Grp2. The universal property of the product group shows that Π is right-adjoint to Δ. The counit of this adjunction is the defining pair of projection maps from ''X''1×''X''2 to ''X''1 and ''X''2 which define the limit, and the unit is the ''diagonal inclusion'' of a group X into ''X''×''X'' (mapping x to (x,x)). : The
cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\t ...
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. * Kernels. Consider the category ''D'' of homomorphisms of abelian groups. If ''f''1 : ''A''1 → ''B''1 and ''f''2 : ''A''2 → ''B''2 are two objects of ''D'', then a morphism from ''f''1 to ''f''2 is a pair (''g''''A'', ''g''''B'') of morphisms such that ''g''''B''''f''1 = ''f''2''g''''A''. Let ''G'' : ''D'' → Ab be the functor which assigns to each homomorphism its kernel and let ''F'' : Ab → ''D'' be the functor which maps the group ''A'' to the homomorphism ''A'' → 0. Then ''G'' is right adjoint to ''F'', which expresses the universal property of kernels. The counit of this adjunction is the defining embedding of a homomorphism's kernel into the homomorphism's domain, and the unit is the morphism identifying a group ''A'' with the kernel of the homomorphism ''A'' → 0. : 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

Coproduct In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coproduc ...
s, fibred coproducts, coequalizers, and
cokernel The cokernel of a linear mapping of vector spaces is the quotient space of the codomain of by the image of . The dimension of the cokernel is called the ''corank'' of . Cokernels are dual to the kernels of category theory, hence the nam ...
s 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. * Coproducts. If ''F'' : Ab2 → Ab assigns to every pair (''X''1, ''X''2) of abelian groups their
direct sum The direct sum is an operation between structures in abstract algebra, a branch of mathematics. It is defined differently, but analogously, for different kinds of structures. To see how the direct sum is used in abstract algebra, consider a mor ...
, and if ''G'' : Ab → Ab2 is the functor which assigns to every abelian group ''Y'' the pair (''Y'', ''Y''), then ''F'' is left adjoint to ''G'', again a consequence of the universal property of direct sums. The unit of this adjoint pair is the defining pair of inclusion maps from ''X''1 and ''X''2 into the direct sum, and the counit is the additive map from the direct sum of (''X'',''X'') to back to ''X'' (sending an element (''a'',''b'') of the direct sum to the element ''a''+''b'' of ''X''). : Analogous examples are given by the
direct sum The direct sum is an operation between structures in abstract algebra, a branch of mathematics. It is defined differently, but analogously, for different kinds of structures. To see how the direct sum is used in abstract algebra, consider a mor ...
of
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
s and
modules Broadly speaking, modularity is the degree to which a system's components may be separated and recombined, often with the benefit of flexibility and variety in use. The concept of modularity is used primarily to reduce complexity by breaking a s ...
, by the
free product In mathematics, specifically group theory, the free product is an operation that takes two groups ''G'' and ''H'' and constructs a new The result contains both ''G'' and ''H'' as subgroups, is generated by the elements of these subgroups, and is ...
of groups and by the disjoint union of sets.


Further examples


Algebra

* Adjoining an identity to a rng. This example was discussed in the motivation section above. Given a rng ''R'', a multiplicative identity element can be added by taking ''R''xZ and defining a Z-bilinear product with (r,0)(0,1) = (0,1)(r,0) = (r,0), (r,0)(s,0) = (rs,0), (0,1)(0,1) = (0,1). This constructs a left adjoint to the functor taking a ring to the underlying rng. * Adjoining an identity to a
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
. Similarly, given a semigroup ''S'', we can add an identity element and obtain a
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
by taking the
disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ( ...
''S'' \sqcup and defining a binary operation on it such that it extends the operation on ''S'' and 1 is an identity element. This construction gives a functor that is a left adjoint to the functor taking a monoid to the underlying semigroup. * Ring extensions. Suppose ''R'' and ''S'' are rings, and ρ : ''R'' → ''S'' is a
ring homomorphism In ring theory, a branch of abstract algebra, a ring homomorphism is a structure-preserving function between two rings. More explicitly, if ''R'' and ''S'' are rings, then a ring homomorphism is a function such that ''f'' is: :addition preser ...
. Then ''S'' can be seen as a (left) ''R''-module, and the
tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
with ''S'' yields a functor ''F'' : ''R''-Mod → ''S''-Mod. Then ''F'' is left adjoint to the forgetful functor ''G'' : ''S''-Mod → ''R''-Mod. * Tensor products. If ''R'' is a ring and ''M'' is a right ''R''-module, then the tensor product with ''M'' yields a functor ''F'' : ''R''-Mod → Ab. The functor ''G'' : Ab → ''R''-Mod, defined by ''G''(''A'') = homZ(''M'',''A'') for every abelian group ''A'', is a right adjoint to ''F''. * From monoids and groups to rings. The integral monoid ring construction gives a functor from
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoid ...
s to rings. This functor is left adjoint to the functor that associates to a given ring its underlying multiplicative monoid. Similarly, the integral group ring construction yields a functor from
groups A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
to rings, left adjoint to the functor that assigns to a given ring its
group of units In algebra, a unit of a ring is an invertible element for the multiplication of the ring. That is, an element of a ring is a unit if there exists in such that vu = uv = 1, where is the multiplicative identity; the element is unique for thi ...
. One can also start with a field ''K'' and consider the category of ''K''-
algebras In mathematics, an algebra over a field (often simply called an algebra) is a vector space equipped with a bilinear product. Thus, an algebra is an algebraic structure consisting of a set together with operations of multiplication and addition ...
instead of the category of rings, to get the monoid and group rings over ''K''. * Field of fractions. Consider the category Domm of integral domains with injective morphisms. The forgetful functor Field → Domm from fields has a left adjoint—it assigns to every integral domain its
field of fractions In abstract algebra, the field of fractions of an integral domain is the smallest field in which it can be embedded. The construction of the field of fractions is modeled on the relationship between the integral domain of integers and the field ...
. * Polynomial rings. Let Ring* be the category of pointed commutative rings with unity (pairs (A,a) where A is a ring, a ∈ A and morphisms preserve the distinguished elements). The forgetful functor G:Ring* → Ring has a left adjoint – it assigns to every ring R the pair (R x) where R is the
polynomial ring In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables ...
with coefficients from R. * Abelianization. Consider the inclusion functor ''G'' : Ab → Grp from the
category of abelian groups In mathematics, the category Ab has the abelian groups as objects and group homomorphisms as morphisms. This is the prototype of an abelian category: indeed, every small abelian category can be embedded in Ab. Properties The zero object of ...
to category of groups. It has a left adjoint called
abelianization In mathematics, more specifically in abstract algebra, the commutator subgroup or derived subgroup of a group is the subgroup generated by all the commutators of the group. The commutator subgroup is important because it is the smallest normal ...
which assigns to every group ''G'' the quotient group ''G''ab=''G''/ 'G'',''G'' * The Grothendieck group. In K-theory, the point of departure is to observe that the category of
vector bundle In mathematics, a vector bundle is a topological construction that makes precise the idea of a family of vector spaces parameterized by another space X (for example X could be a topological space, a manifold, or an algebraic variety): to every p ...
s on a
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
has a commutative monoid structure under
direct sum The direct sum is an operation between structures in abstract algebra, a branch of mathematics. It is defined differently, but analogously, for different kinds of structures. To see how the direct sum is used in abstract algebra, consider a mor ...
. One may make an
abelian group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is comm ...
out of this monoid, the
Grothendieck group In mathematics, the Grothendieck group, or group of differences, of a commutative monoid is a certain abelian group. This abelian group is constructed from in the most universal way, in the sense that any abelian group containing a homomorphic ...
, by formally adding an additive inverse for each bundle (or equivalence class). Alternatively one can observe that the functor that for each group takes the underlying monoid (ignoring inverses) has a left adjoint. This is a once-for-all construction, in line with the third section discussion above. That is, one can imitate the construction of
negative number In mathematics, a negative number represents an opposite. In the real number system, a negative number is a number that is less than zero. Negative numbers are often used to represent the magnitude of a loss or deficiency. A debt that is owed ma ...
s; but there is the other option of an
existence theorem In mathematics, an existence theorem is a theorem which asserts the existence of a certain object. It might be a statement which begins with the phrase " there exist(s)", or it might be a universal statement whose last quantifier is existential ...
. For the case of finitary algebraic structures, the existence by itself can be referred to
universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular groups as the object of study ...
, or
model theory In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (math ...
; naturally there is also a proof adapted to category theory, too. * Frobenius reciprocity in the representation theory of groups: see
induced representation In group theory, the induced representation is a representation of a group, , which is constructed using a known representation of a subgroup . Given a representation of '','' the induced representation is, in a sense, the "most general" represe ...
. This example foreshadowed the general theory by about half a century.


Topology

* A functor with a left and a right adjoint. Let ''G'' be the functor from
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
s to sets that associates to every topological space its underlying set (forgetting the topology, that is). ''G'' has a left adjoint ''F'', creating the
discrete space In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are ''isolated'' from each other in a certain sense. The discrete topology is the finest top ...
on a set ''Y'', and a right adjoint ''H'' creating the
trivial topology In topology, a topological space with the trivial topology is one where the only open sets are the empty set and the entire space. Such spaces are commonly called indiscrete, anti-discrete, concrete or codiscrete. Intuitively, this has the conseque ...
on ''Y''. * Suspensions and loop spaces. Given
topological spaces In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called point ...
''X'' and ''Y'', the space 'SX'', ''Y''of
homotopy classes In topology, a branch of mathematics, two continuous functions from one topological space to another are called homotopic (from grc, ὁμός "same, similar" and "place") if one can be "continuously deformed" into the other, such a defor ...
of maps from the suspension ''SX'' of ''X'' to ''Y'' is naturally isomorphic to the space 'X'', Ω''Y''of homotopy classes of maps from ''X'' to the
loop space In topology, a branch of mathematics, the loop space Ω''X'' of a pointed topological space ''X'' is the space of (based) loops in ''X'', i.e. continuous pointed maps from the pointed circle ''S''1 to ''X'', equipped with the compact-open topol ...
Ω''Y'' of ''Y''. The suspension functor is therefore left adjoint to the loop space functor in the
homotopy category In mathematics, the homotopy category is a category built from the category of topological spaces which in a sense identifies two spaces that have the same shape. The phrase is in fact used for two different (but related) categories, as discussed be ...
, an important fact in
homotopy theory In mathematics, homotopy theory is a systematic study of situations in which maps can come with homotopies between them. It originated as a topic in algebraic topology but nowadays is studied as an independent discipline. Besides algebraic topolo ...
. * Stone–Čech compactification. Let KHaus be the category of
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in Britis ...
Hausdorff space In topology and related branches of mathematics, a Hausdorff space ( , ), separated space or T2 space is a topological space where, for any two distinct points, there exist neighbourhoods of each which are disjoint from each other. Of the ma ...
s and ''G'' : KHaus → Top be the inclusion functor to the category of
topological spaces In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called point ...
. Then ''G'' has a left adjoint ''F'' : Top → KHaus, the Stone–Čech compactification. The unit of this adjoint pair yields a
continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous g ...
map from every topological space ''X'' into its Stone–Čech compactification. * Direct and inverse images of sheaves. Every
continuous map In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in valu ...
''f'' : ''X'' → ''Y'' between
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called poin ...
s induces a functor ''f'' from the category of sheaves (of sets, or abelian groups, or rings...) on ''X'' to the corresponding category of sheaves on ''Y'', the ''
direct image functor In mathematics, the direct image functor is a construction in sheaf theory that generalizes the global sections functor to the relative case. It is of fundamental importance in topology and algebraic geometry. Given a sheaf ''F'' defined on a to ...
''. It also induces a functor ''f'' −1 from the category of sheaves of abelian groups on ''Y'' to the category of sheaves of abelian groups on ''X'', the '' inverse image functor''. ''f'' −1 is left adjoint to ''f''. Here a more subtle point is that the left adjoint for coherent sheaves will differ from that for sheaves (of sets). * Soberification. The article on
Stone duality In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they f ...
describes an adjunction between the category of topological spaces and the category of sober spaces that is known as soberification. Notably, the article also contains a detailed description of another adjunction that prepares the way for the famous duality of sober spaces and spatial locales, exploited in
pointless topology In mathematics, pointless topology, also called point-free topology (or pointfree topology) and locale theory, is an approach to topology that avoids mentioning points, and in which the lattices of open sets are the primitive notions. In this appr ...
.


Posets

Every
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
can be viewed as a category (where the elements of the poset become the category's objects and we have a single morphism from ''x'' to ''y'' if and only if ''x'' ≤ ''y''). A pair of adjoint functors between two partially ordered sets is called a
Galois connection In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the funda ...
(or, if it is contravariant, an ''antitone'' Galois connection). See that article for a number of examples: the case of
Galois theory In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
of course is a leading one. Any Galois connection gives rise to
closure operator In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S : Closure operators are de ...
s 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: * adjunctions may not be dualities or isomorphisms, but are candidates for upgrading to that status * closure operators may indicate the presence of adjunctions, as corresponding monads (cf. the
Kuratowski closure axioms In topology and related branches of mathematics, the Kuratowski closure axioms are a set of axioms that can be used to define a topological structure on a set. They are equivalent to the more commonly used open set definition. They were first forma ...
) * a very general comment of
William Lawvere Francis William Lawvere (; born February 9, 1937) is a mathematician known for his work in category theory, topos theory and the philosophy of mathematics. Biography Lawvere studied continuum mechanics as an undergraduate with Clifford Truesdell ...
is that ''syntax and semantics'' are adjoint: take ''C'' to be the set of all logical theories (axiomatizations), and ''D'' the power set of the set of all mathematical structures. For a theory ''T'' in ''C'', let ''G''(''T'') be the set of all structures that satisfy the axioms ''T''; for a set of mathematical structures ''S'', let ''F''(''S'') be the minimal axiomatization of ''S''. We can then say that ''S'' is a subset of ''G''(''T'') if and only if ''F''(''S'') logically implies ''T'': the "semantics functor" ''G'' is right adjoint to the "syntax functor" ''F''. * division is (in general) the attempt to ''invert'' multiplication, but in situations where this is not possible, we often attempt to construct an ''adjoint'' instead: the ideal quotient is adjoint to the multiplication by ring ideals, and the implication in
propositional logic Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
is adjoint to
logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...
.


Category theory

* Equivalences. If ''F'' : ''D'' → ''C'' is an
equivalence of categories In category theory, a branch of abstract mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences fr ...
, then we have an inverse equivalence ''G'' : ''C'' → ''D'', and the two functors ''F'' and ''G'' form an adjoint pair. The unit and counit are natural isomorphisms in this case. * A series of adjunctions. The functor π0 which assigns to a category its set of connected components is left-adjoint to the functor ''D'' which assigns to a set the discrete category on that set. Moreover, ''D'' is left-adjoint to the object functor ''U'' which assigns to each category its set of objects, and finally ''U'' is left-adjoint to ''A'' which assigns to each set the indiscrete category on that set. * Exponential object. In a cartesian closed category the endofunctor ''C'' → ''C'' given by –×''A'' has a right adjoint –''A''. This pair is often referred to as
currying In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function f tha ...
and uncurrying; in many special cases, they are also continuous and form a homeomorphism.


Categorical logic

* Quantification. If \phi_Y is a unary predicate expressing some property, then a sufficiently strong set theory may prove the existence of the set Y=\ of terms that fulfill the property. A proper subset T\subset Y and the associated injection of T into Y is characterized by a predicate \phi_T(y)=\phi_Y(y)\land\varphi(y) expressing a strictly more restrictive property. :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 \psi_f with two open variables of sort X and Y. Using a quantifier to close X, we can form the set ::\ :of all elements y of Y for which there is an x to which it is \psi_f-related, and which itself is characterized by the property \phi_. Set theoretic operations like the intersection \cap of two sets directly corresponds to the conjunction \land of predicates. In categorical logic, a subfield of
topos theory In mathematics, a topos (, ; plural topoi or , or toposes) is a category that behaves like the category of sheaves of sets on a topological space (or more generally: on a site). Topoi behave much like the category of sets and possess a notio ...
, 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 the general definition make for a richer range of logics. :So consider an object Y in a category with pullbacks. Any morphism f:X\to Y induces a functor ::f^ : \text(Y) \longrightarrow \text(X) :on the category that is the preorder of subobjects. It maps subobjects T of Y (technically: monomorphism classes of T\to Y) to the pullback X\times_Y T. If this functor has a left- or right adjoint, they are called \exists_f and \forall_f, respectively. Mac Lane, Saunders; Moerdijk, Ieke (1992) ''Sheaves in Geometry and Logic'', Springer-Verlag. ''See page 58'' They both map from \text(X) back to \text(Y). Very roughly, given a domain S\subset X to quantify a relation expressed via f over, the functor/quantifier closes X in X\times_Y T and returns the thereby specified subset of Y. : Example: In \operatorname, the category of sets and functions, the canonical subobjects are the subset (or rather their canonical injections). The pullback f^T=X\times_Y T of an injection of a subset T into Y along f is characterized as the largest set which knows all about f and the injection of T into Y. It therefore turns out to be (in bijection with) the inverse image f^ subseteq X. :For S \subseteq X, let us figure out the left adjoint, which is defined via ::(\exists_f S,T) \cong (S,f^T), :which here just means ::\exists_f S\subseteq T \leftrightarrow S\subseteq f^ /math>. :Consider f \subseteq T . We see S\subseteq f^ [S\subseteq f^ /math>. Conversely, If for an x\in S we also have x\in f^ /math>, then clearly f(x)\in T . So S \subseteq f^[T] implies f \subseteq T . We conclude that left adjoint to the inverse image functor f^ is given by the direct image. Here is a characterization of this result, which matches more the logical interpretation: The image of S under \exists_f is the full set of y's, such that f^ \cap S is non-empty. This works because it neglects exactly those y\in Y which are in the complement of f /math>. So :: \exists_f S = \ = f :Put this in analogy to our motivation \. :The right adjoint to the inverse image functor is given (without doing the computation here) by :: \forall_f S = \. : The subset \forall_f S of Y is characterized as the full set of y's with the property that the inverse image of \ with respect to f is fully contained within S. Note how the predicate determining the set is the same as above, except that \exists is replaced by \forall. :''See also
powerset In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
.''


Probability

The twin fact in probability can be understood as an adjunction: that expectation commutes with affine transform, and that the expectation is in some sense the best ''solution'' to the problem of finding a real-valued approximation to a distribution on the real numbers. Define a category based on \R, with objects being the real numbers, and the morphisms being "affine functions evaluated at a point". That is, for any affine function f(x) = ax + b and any real number r, define a morphism (r, f): r \to f(r). Define a category based on M(\R), the set of probability distribution on \R with finite expectation. Define morphisms on M(\R) as "affine functions evaluated at a distribution". That is, for any affine function f(x) = ax + b and any \mu\in M(\R), define a morphism (\mu, f): r \to \mu\circ f^. Then, the Dirac delta measure defines a functor: \delta: x\mapsto \delta_x, and the expectation defines another functor \mathbb E: \mu \mapsto \mathbb E mu/math>, and they are adjoint: \mathbb E \dashv \delta. (Somewhat disconcertingly, \mathbb E is the left adjoint, even though \mathbb E is "forgetful" and \delta is "free".)


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 *A
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
''F'' : ''D'' → ''C'' called the left adjoint *A functor ''G'' : ''C'' → ''D'' called the right adjoint *A
natural isomorphism In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
Φ : hom''C''(''F''–,–) → hom''D''(–,''G''–) *A
natural transformation In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
ε : ''FG'' → 1''C'' called the counit *A natural transformation η : 1''D'' → ''GF'' called the unit An equivalent formulation, where ''X'' denotes any object of ''C'' and ''Y'' denotes any object of ''D'', is as follows: ::For every ''C''-morphism ''f'' : ''FY'' → ''X'', there is a unique ''D''-morphism Φ''Y'', ''X''(''f'') = ''g'' : ''Y'' → ''GX'' such that the diagrams below commute, and for every ''D''-morphism ''g'' : ''Y'' → ''GX'', there is a unique ''C''-morphism Φ−1''Y'', ''X''(''g'') = ''f'' : ''FY'' → ''X'' in ''C'' such that the diagrams below commute: From this assertion, one can recover that: *The transformations ε, η, and Φ are related by the equations :\begin f = \Phi_^(g) &= \varepsilon_X\circ F(g) & \in & \, \, \mathrm_C(F(Y),X)\\ g = \Phi_(f) &= G(f)\circ \eta_Y & \in & \, \, \mathrm_D(Y,G(X))\\ \Phi_^(1_) &= \varepsilon_X & \in & \, \, \mathrm_C(FG(X),X)\\ \Phi_(1_) &= \eta_Y & \in & \, \, \mathrm_D(Y,GF(Y))\\ \end *The transformations ε, η satisfy the counit–unit equations :\begin 1_ &= \varepsilon_ \circ F(\eta_Y)\\ 1_ &= G(\varepsilon_X) \circ \eta_ \end *Each pair (''GX'', ε''X'') is a terminal morphism from ''F'' to ''X'' in ''C'' *Each pair (''FY'', η''Y'') is an initial morphism from ''Y'' to ''G'' in ''D'' 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. The equivalence of these situations is demonstrated below.


Universal morphisms induce hom-set adjunction

Given a right adjoint functor ''G'' : ''C'' → ''D''; in the sense of initial morphisms, one may construct the induced hom-set adjunction by doing the following steps. * Construct a functor ''F'' : ''D'' → ''C'' and a natural transformation η. ** For each object ''Y'' in ''D'', choose an initial morphism (''F''(''Y''), η''Y'') from ''Y'' to ''G'', so that η''Y'' : ''Y'' → ''G''(''F''(''Y'')). We have the map of ''F'' on objects and the family of morphisms η. ** For each ''f'' : ''Y''0 → ''Y''1, as (''F''(''Y''0), η''Y''0) is an initial morphism, then factorize η''Y''1 o ''f'' with η''Y''0 and get ''F''(''f'') : ''F''(''Y''0) → ''F''(''Y''1). This is the map of ''F'' on morphisms. ** The commuting diagram of that factorization implies the commuting diagram of natural transformations, so η : 1''D'' → ''G'' o ''F'' is a
natural transformation In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
. ** Uniqueness of that factorization and that ''G'' is a functor implies that the map of ''F'' on morphisms preserves compositions and identities. * Construct a natural isomorphism Φ : hom''C''(''F''-,-) → hom''D''(-,''G''-). ** For each object ''X'' in ''C'', each object ''Y'' in ''D'', as (''F''(''Y''), η''Y'') is an initial morphism, then Φ''Y'', ''X'' is a bijection, where Φ''Y'', ''X''(''f'' : ''F''(''Y'') → ''X'') = ''G''(''f'') o η''Y''. ** η is a natural transformation, ''G'' is a functor, then for any objects ''X''0, ''X''1 in ''C'', any objects ''Y''0, ''Y''1 in ''D'', any ''x'' : ''X''0 → ''X''1, any ''y'' : ''Y''1 → ''Y''0, we have Φ''Y''1, ''X''1(''x'' o ''f'' o ''F''(''y'')) = G(x) o ''G''(''f'') o ''G''(''F''(''y'')) o η''Y''1 = ''G''(''x'') o ''G''(''f'') o η''Y''0 o ''y'' = ''G''(''x'') o Φ''Y''0, ''X''0(''f'') o ''y'', and then Φ is natural in both arguments. 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'' : ''D'' → ''C'', ''G'' : ''C'' → ''D'', and a counit–unit adjunction (ε, η) : ''F'' \dashv ''G'', we can construct a hom-set adjunction by finding the natural transformation Φ : hom''C''(''F''-,-) → hom''D''(-,''G''-) in the following steps: *For each ''f'' : ''FY'' → ''X'' and each ''g'' : ''Y'' → ''GX'', define :\begin\Phi_(f) = G(f)\circ \eta_Y\\ \Psi_(g) = \varepsilon_X\circ F(g)\end :The transformations Φ and Ψ are natural because η and ε are natural. *Using, in order, that ''F'' is a functor, that ε is natural, and the counit–unit equation 1''FY'' = ε''FY'' o ''F''(η''Y''), we obtain :\begin \Psi\Phi f &= \varepsilon_X\circ FG(f)\circ F(\eta_Y) \\ &= f\circ \varepsilon_\circ F(\eta_Y) \\ &= f\circ 1_ = f\end :hence ΨΦ is the identity transformation. *Dually, using that ''G'' is a functor, that η is natural, and the counit–unit equation 1''GX'' = ''G''(ε''X'') o η''GX'', we obtain :\begin \Phi\Psi g &= G(\varepsilon_X)\circ GF(g)\circ\eta_Y \\ &= G(\varepsilon_X)\circ\eta_\circ g \\ &= 1_\circ g = g\end :hence ΦΨ is the identity transformation. Thus Φ is a natural isomorphism with inverse Φ−1 = Ψ.


Hom-set adjunction induces all of the above

Given functors ''F'' : ''D'' → ''C'', ''G'' : ''C'' → ''D'', and a hom-set adjunction Φ : hom''C''(''F''-,-) → hom''D''(-,''G''-), one can construct a counit–unit adjunction :(\varepsilon,\eta):F\dashv G , which defines families of initial and terminal morphisms, in the following steps: *Let  \varepsilon_X=\Phi_^(1_)\in\mathrm_C(FGX,X)  for each ''X'' in ''C'', where  1_\in\mathrm_D(GX,GX)  is the identity morphism. *Let  \eta_Y=\Phi_(1_)\in\mathrm_D(Y,GFY)  for each ''Y'' in ''D'', where  1_\in\mathrm_C(FY,FY)  is the identity morphism. *The bijectivity and naturality of Φ imply that each (''GX'', ε''X'') is a terminal morphism from ''F'' to ''X'' in ''C'', and each (''FY'', η''Y'') is an initial morphism from ''Y'' to ''G'' in ''D''. *The naturality of Φ implies the naturality of ε and η, and the two formulas :\begin\Phi_(f) = G(f)\circ \eta_Y\\ \Phi_^(g) = \varepsilon_X\circ F(g)\end :for each ''f'': ''FY'' → ''X'' and ''g'': ''Y'' → ''GX'' (which completely determine Φ). *Substituting ''FY'' for ''X'' and η''Y'' = Φ''Y'', ''FY''(1''FY'') for ''g'' in the second formula gives the first counit–unit equation :1_ = \varepsilon_\circ F(\eta_Y), :and substituting ''GX'' for ''Y'' and εX = Φ−1''GX, X''(1''GX'') for ''f'' in the first formula gives the second counit–unit equation :1_ = G(\varepsilon_X)\circ\eta_.


Properties


Existence

Not every functor ''G'' : ''C'' → ''D'' admits a left adjoint. If ''C'' is a
complete category In mathematics, a complete category is a category in which all small limits exist. That is, a category ''C'' is complete if every diagram ''F'' : ''J'' → ''C'' (where ''J'' is small) has a limit in ''C''. Dually, a cocomplete category is one in ...
, then the functors with left adjoints can be characterized by the adjoint functor theorem of
Peter J. Freyd Peter John Freyd (; born February 5, 1936) is an American mathematician, a professor at the University of Pennsylvania, known for work in category theory and for founding the False Memory Syndrome Foundation. Mathematics Freyd obtained his Ph ...
: ''G'' has a left adjoint if and only if it is
continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous g ...
and a certain smallness condition is satisfied: for every object ''Y'' of ''D'' there exists a family of morphisms :''f''''i'' : ''Y'' → ''G''(''X''''i'') where the indices ''i'' come from a ''set'' , not a ''
proper class Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map f ...
'', such that every morphism :''h'' : ''Y'' → ''G''(''X'') can be written as :''h'' = ''G''(''t'') ∘ ''f''''i'' for some ''i'' in and some morphism :''t'' : ''X''''i'' → ''X'' ∈ ''C''. An analogous statement characterizes those functors with a right adjoint. An important special case is that of locally presentable categories. If F : C \to D is a functor between locally presentable categories, then * ''F'' has a right adjoint if and only if ''F'' preserves small colimits * ''F'' has a left adjoint if and only if ''F'' preserves small limits and is an accessible functor


Uniqueness

If the functor ''F'' : ''D'' → ''C'' has two right adjoints ''G'' and ''G''′, then ''G'' and ''G''′ are
naturally isomorphic In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
. 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 :σ : ''F'' → ''F''′ :τ : ''G'' → ''G''′ are natural isomorphisms then 〈''F''′, ''G''′, ε′, η′〉 is an adjunction where :\begin \eta' &= (\tau\ast\sigma)\circ\eta \\ \varepsilon' &= \varepsilon\circ(\sigma^\ast\tau^). \end Here \circ denotes vertical composition of natural transformations, and \ast 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 :F \circ F' : E \rightarrow C is left adjoint to :G' \circ G : C \to E. More precisely, there is an adjunction between ''F F and ''G' G'' with unit and counit given respectively by the compositions: :\begin &1_ \xrightarrow G' F' \xrightarrow G' G F F' \\ &F F' G' G \xrightarrow F G \xrightarrow 1_. \end This new adjunction is called the composition of the two given adjunctions. Since there is also a natural way to define an identity adjunction between a category ''C'' and itself, 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 In category theory, a branch of mathematics, the abstract notion of a limit captures the essential properties of universal constructions such as products, pullbacks and inverse limits. The dual notion of a colimit generalizes constructions s ...
). Since many common constructions in mathematics are limits or colimits, this provides a wealth of information. For example: * applying a right adjoint functor to a product of objects yields the product of the images; * applying a left adjoint functor to a
coproduct In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coproduc ...
of objects yields the coproduct of the images; * every right adjoint functor between two abelian categories is left exact; * every left adjoint functor between two abelian categories is right exact.


Additivity

If ''C'' and ''D'' are preadditive categories and ''F'' : ''D'' → ''C'' is an additive functor with a right adjoint ''G'' : ''C'' → ''D'', then ''G'' is also an additive functor and the hom-set bijections :\Phi_ : \mathrm_(FY,X) \cong \mathrm_(Y,GX) 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
biproduct In category theory and its applications to mathematics, a biproduct of a finite collection of objects, in a category with zero objects, is both a product and a coproduct. In a preadditive category the notions of product and coproduct coincide fo ...
s), 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 morphism In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently f ...
s, one for each object in ''C'' and one for each object in ''D''. Conversely, if there exists a universal morphism to a functor ''G'' : ''C'' → ''D'' 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'' : ''D'' → ''C'' is one half of an
equivalence of categories In category theory, a branch of abstract mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences fr ...
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 ''C''1 as the full subcategory of ''C'' consisting of those objects ''X'' of ''C'' for which ε''X'' is an isomorphism, and define ''D''1 as the
full subcategory In mathematics, specifically category theory, a subcategory of a category ''C'' is a category ''S'' whose objects are objects in ''C'' and whose morphisms are morphisms in ''C'' with the same identities and composition of morphisms. Intuitively, ...
of ''D'' consisting of those objects ''Y'' of ''D'' for which η''Y'' is an isomorphism. Then ''F'' and ''G'' can be restricted to ''D''1 and ''C''1 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 1''D'') 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
monad Monad may refer to: Philosophy * Monad (philosophy), a term meaning "unit" **Monism, the concept of "one essence" in the metaphysical and theological theory ** Monad (Gnosticism), the most primal aspect of God in Gnosticism * ''Great Monad'', a ...
〈''T'', η, μ〉 in the category ''D''. The functor :T : \mathcal \to \mathcal is given by ''T'' = ''GF''. The unit of the monad :\eta : 1_ \to T is just the unit η of the adjunction and the multiplication transformation :\mu : T^2 \to T\, is given by μ = ''G''ε''F''. Dually, the triple 〈''FG'', ε, ''F''η''G''〉 defines a
comonad In category theory, a branch of mathematics, a monad (also triple, triad, standard construction and fundamental construction) is a monoid in the category of endofunctors. An endofunctor is a functor mapping a category to itself, and a monad is ...
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


References

* *


External links

* – seven short lectures on adjunctions by
Eugenia Cheng Eugenia Loh-Gene Cheng is a British mathematician and concert pianist. Her mathematical interests include higher category theory, and as a pianist she specialises in lieder and art song. She is also passionate about explaining mathematics to no ...
of The Catsters
WildCats
is a category theory package for
Mathematica Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimiza ...
. Manipulation and visualization of objects,
morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
s, categories,
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
s,
natural transformation In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
s, universal properties. {{DEFAULTSORT:Adjoint Functors