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