<< Предыдущая стр. 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 .
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 стр.)ОГЛАВЛЕНИЕ Следующая >>