<<

. 12
( 60 .)



>>

The inverse simply restricts a group homomorphism from F A to G to the
basis A. Essentially the same statement is true for monoids instead of groups
(replace F A by the free monoid A— ) and also for the category of abelian groups,
with F A the free abelian group with basis A.
The bijection just mentioned is a natural isomorphism β of functors of two
variables, in other words a natural isomorphism from the functor HomGrp (F (’), ’)
to HomSet (’, U (’)). This means precisely that for all functions f : B ’ A and

all group homomorphisms g: G ’ H, ’

β(A, G) E
HomGrp (F A, G) HomSet (A, U G)
T T
HomGrp (F f, g) HomSet (f, U g) (1)

E HomSet (B, U H)
HomGrp (F B, H)
β(B, H)
commutes.
The free group functor and the underlying set functor are a typical pair of
“adjoint functors”. Formally, if A and D are categories and L: A ’ D and

R: D ’ A are functors, then L is left adjoint to R and R is right adjoint to L

if for every objects A of A and B of D there is an isomorphism

HomA (A, RB) ∼ HomD (LA, B)
=

which is natural in the sense of diagram 1. Informally, elements of RB de¬ned
on A are essentially the same as element of B de¬ned on LA.
If f : A ’ RB, the arrow g: LA ’ B corresponding to it under the natural
’ ’
isomorphism is called the transpose or adjoint transpose of f . The arrow f is
also called the transpose of g; usually there is no doubt which is meant, although
the word can indeed be ambiguous.

Unit and counit

In particular, if L is left adjoint to R and A is an object of A , then corre-
sponding to idLA in HomA (LA, LA) there is an arrow ·A: A ’ RLA; the arrows

·A form a natural transformation from the identity functor on A to R —¦ L. This
56 1 Categories
natural transformation · is the unit of the adjunction of L to R. A similar trick
also produces a natural transformation : L —¦ R ’ idD called the counit of the

adjunction. The unit and counit essentially determine the adjunction completely
(Exercise 15).

Examples

We give a number of examples here and some more in the exercises.

1. If A is a set, let 2A denote the category of subsets of A ordered by inclusion.
If f : A ’ B is a function, the direct image functor which assigns to each

A0 ⊆ A its image f! (A0 ) is left adjoint to the inverse image functor f ’1 : 2B
’ 2A ; see Exercise 6 of Section 1.2. It follows also from that exercise

that the f— de¬ned there is right adjoint to f ’1 . Observe that y ∈ f! (A0 )
(a statement without quanti¬ers) if and only if there exists an x ∈ A0
such that f (x) = y (a statement with an existential quanti¬er). Universal
quanti¬ers may also be introduced using — . In this way, quanti¬ers may be
introduced into the language of a topos. However we will not be doing that.
See Lambek and Scott [1984].
2. If A is a ¬xed set, the functor from Set to Set which takes any set B to B —A
is left adjoint to the functor which takes a set T to the set HomSet (A, T ) of
functions from A to T . In other words,

HomSet (B — A, T ) ∼ HomSet (B, HomSet (A, T ))
=

The counit of this adjunction is the map from HomSet (A, B) — A to B
which takes a pair (f, x) to its value f (x) and so is called the evaluation
map. Note the formal similarity between the evaluation map and the modus
ponens rule of logic.
3. Let A be an equationally de¬ned category of algebraic structures (You can
skip this example if you don™t know about equationally de¬ned theories.
They will be treated in detail later.) For example, a group is a set with one
nullary operation e (the unit element), one unary operation (which takes an
element to its inverse), and one binary operation (the group multiplication),
subiect to the equations
xe() = e()x = x
xx’1 = x’1 x = e()
and
(xy)z = x(yz)
1.9 Adjoint functors 57
which hold for all x, y, z in the group.
Such a category A has an underlying set functor U : A ’ Set and it can be

proved that U has a left adjoint F : Set ’ A . It follows from adjointness

(Exercise 16) that for any set X and any function g: X ’ U A where A is

any object of A , there is a unique arrow g : F X ’ A for which

·XE UFX
X
d
gd Ug
d
‚c
d
UA
commutes. Thus F X deserves to be called the “free A -structure on X”.
Exercises 1, 2, 3, 7 and 8 give concrete descriptions of the adjoints for
special cases of equationally de¬ned categories.

Lest the reader get the idea that all underlying set functors have adjoints,
we mention the category of ¬elds, whose underlying set functor does not have
an adjoint. An interesting case is that of torsion abelian groups. If we ¬x an
exponent d and look at all groups satisfying xd = 1, there is an adjoint that takes
a set S to the direct sum of S many copies of Z/dZ, but on the full category,
there is no adjoint.

Representability and adjointness

The statement that L is left adjoint to R immediately implies that for each
object A of A , the object LA of B represents the functor HomA (A, R(’)): B
’ Set. The universal element for this representation, which must be an element

of HomA (A, RLA), is the unit ·A. Dually, the object RB with universal element
A represents the contravariant functor Hom(L(’), B). The following theorem is
a strong converse to these facts.
[Pointwise construction of adjoints] Let A and B be categories.
Theorem 1.

(a) If R: B ’ A is a functor such that the functor HomA (A, R(’)) is repre-

sentable for every object A of A , then R has a left adjoint.
(b) If L: A ’ B is a functor such that HomB (L(’), B) is representable for

every object B of B, then L has a left adjoint.

With little more work, one can prove parametrized versions of these results.
58 1 Categories
Let A , B, and X be categories.
Theorem 2.

(a) If R: X —B ’ A is a functor such that the functor HomB (A, R(X, ’)): B

’ Set is representable for every objects A ∈ Ob(A ) and X ∈ Ob(X ), then

there is a unique functor L: A — X op ’ B such that


HomA (’, R(’, ’)) ∼ HomB (L(’, ’), ’)
=

as functors A op — X — B ’ Set.

(b) If L: A — X op ’ B is a functor such that HomB (L(’, X), B): A ’ Set
’ ’
is representable for all objects B ∈ Ob(B) and X ∈ Ob(X ), then there is
a unique functor R: X — B ’ A such that


HomA (’, R(’, ’)) ∼ HomB (L(’, ’), ’)
=

as functors A op — X — B ’ Set.


Proof. The two statements are dual, so we will prove the ¬rst. First, choose an
object function L: Ob(A ) — Ob(X ) ’ Ob(B) such that HomA (A, R(X, B)) ∼
’ =
HomB (L(A, X), B) for all A ∈ Ob(A ), X ∈ Ob(X ), and B ∈ Ob(B). Now we
want to make L into a functor. Choose arrows f : A ’ A and g: X ’ X. Now
’ ’
for any B ∈ Ob(B) we have a diagram

= E Hom (L(A , X ), B)
HomA (A , R(X , B)) B


HomA (f, R(g, B)) (2)
c
E HomB (L(A, X), B)
HomA (A, R(X, B)) ∼
=
There is thus a unique arrow φ(f, g, B): HomB (L(A , X ), B) ’ HomB (L(A, X), B)

that makes the square commute. Moreover, since both the isomorphisms and
HomA (f, R(g, B)) are natural with respect to B, we conclude that φ(f, g, B) is
as well. By the Yoneda lemma, there is a unique arrow we call L(f, g): L(A, X)
’ L(A , X ) such that φ(f, g, B) = HomB (L(f, g), B). If now we have f : A

’ A and g : X ’ X we can stack another diagram of shape 2 on top of that
’ ’
one to show that L(f, g) —¦ L(f , g ) = L(f —¦ f , g —¦ g). The fact that L preserves
identities is even easier.
One of the most important properties of adjoints is their limit preservation
properties.
1.9 Adjoint functors 59
Proposition 3. Let L: A ’ B be left adjoint to R: B ’ A . Then R
’ ’
preserves the limit of an any diagram in B that has a limit and L preserves the
colimit of any diagram in A that has a colimit.

Proof. This follows from Exercise 14 of Section 1.7, but a direct proof is short
and instructive: Suppose that D: I ’ B is a diagram and that B ’ D is a
’ ’
limit cone. Given a cone A ’ RD, the adjunction gives a cone LA ’ D by
’ ’
applying the adjunction to each element of the cone. The universality gives an
arrow LA ’ C and then the adjunction gives A ’ U C. We can summarize
’ ’
this argument as follows:

Cone(A, RD) ∼ Cone(LA, D) ∼ Hom(LA, B) ∼ Hom(A, RB)
= = =

We note that underlying functors in algebra tend to have left adjoints and
thereby preserve limits, but rarely have a right adjoint or preserve colimits.

Existence of adjoints

Freyd™s Adjoint Functor Theorem (Theorem 4 below) is a partial converse to
Corollary 3. To state it, we need a new idea.
Suppose R: D ’ C is a functor. R satis¬es the solution set condition if

for each object A of C there is a set S (the solution set for A) of pairs (y, B)
with y: A ’ RB in C with the property that for any arrow d: A ’ RD there
’ ’
is an element (y, B) of S and an arrow f : B ’ D for which

yE
A RB
d
dd Rf
d

dc
RD
commutes.
If C is small, then S can be taken to be the set of all pairs (y, B) with y: A
’ RB for all arrows y of C and objects B of D. (Then f can, for example, be

taken to be idD .) On the other hand, if R is already known to have a left adjoint
L then S can be taken to be the singleton set with B = LA and y = ·A.
If the singleton {(y, B)} is a solution set for R, y satis¬es the existence but
not necessarily the uniqueness property of the de¬nition of universal element for
the functor Hom(A, R(’)) (Section 1.5). In that case we will say that y is a
weak universal arrow for R and A. (A universal element of Hom(A, R(’)) is
called a universal arrow for R and A.)
60 1 Categories
Theorem 4. [Freyd] Let D be a category with all limits. Then a functor R: D
’ C has a left adjoint if and only if R preserves all limits and satis¬es the

solution set condition.
Proof. Let A be an object of C . In order to construct the left adjoint L, it is
enough by Theorem 1 and the de¬nition of representable functor (Section 1.5)
to construct a universal element for Hom(A, R(’)). We ¬rst construct an object
W A and a weak universal arrow ζA: A ’ RW A. Then we will use equalizers

cleverly to get uniqueness.
The construction of W A is reminiscent of the way one proves that a poset
with all infs and a maximum has all sups (to get the sup of a set, take the inf of
all the elements bigger than everything in the set). The equalizer construction is
not necessary for posets because uniqueness is automatic there.
W A is de¬ned to be the product indexed by all (y, B) ∈ S of the objects B.
W A comes equipped with a projection W A ’ B for each pair (y, B) ∈ S, and

R preserves the fact that W A is a product with these projections. The arrows y
collectively induce ζA: A ’ RW A. Given d: A ’ RD, let (y, B) ∈ S and h: B
’ ’
’ D be an arrow for which Rh —¦ y = d, and p the projection of W A onto B

indexed by (y, B). Then for f = h —¦ p, Rf —¦ ζA = d so that ζA is a weak universal

<<

. 12
( 60 .)



>>