that E±—¦(f i)x, j = E± —¦(f i )x , j . But naturality implies that E±—¦f i = f j —¦D±

and E± —¦ f i = f j —¦ D± , so this equation becomes f j —¦ D±x = f j —¦ D± x . Since

f j is monic, this means that D±x = D± x so that x, i = x , i .

1.11 Notes to Chapter I 71

Theorem 3. In the category of models of a ¬nitary equational theory, every

object is a ¬ltered colimit of ¬nitely presented objects.

Proof. We will do this for the category of groups. We could do abelian groups,

except it is too easy because a ¬nitely generated abelian groups is ¬nitely pre-

sented. So let G be a group. For each ¬nite set of elements of i ∈ G, let F i be the

free group generated by i. For each ¬nite set of relations j that are satis¬ed by

the elements of i, let D(ij) be F i modulo those relations. Make the set of pairs

ij into a graph in which there is a single arrow ij ’ i j if i ⊆ i and j ⊆ j .

’

This is obviously a poset, so write ij ¤ i j when there is such a map. If there

is, then the inclusion induces an inclusion F i ’ F j and since j ⊆ j , there is an

’

induced map (not necessarily injective) D(ij) ’ D(i j ). Since the union of two

’

¬nite sets is ¬nite and there is at most one path between any two nodes of the

graph, D is a ¬ltered diagram in the category of groups. It is left to the reader

to verify that G is its colimit.

1.11 Notes to Chapter I

Development of category theory

Categories, functors and natural transformations were invented by S. Eilen-

berg and S. Mac Lane (announced in “The general theory of natural equivalences”

[1945] in order to describe the connecting homomorphism and the long exact se-

ˇ

quence in Cech homology and cohomology. The problem was this: homology was

de¬ned in the ¬rst instance in terms of a cover. If the cover is simple, that is if

every non-empty intersection of a ¬nite subset of the cover is a contractible space

(as actually happens with the open star cover of a triangulated space), then that

homology in terms of the cover is the homology of the space and that is the end

ˇ

of the matter. What is done in Cech theory, in the absence of a simple cover, is to

form the direct limit of the homology groups over the set of all covers directed by

re¬nement. This works ¬ne for de¬ning the groups but gives no information on

how to de¬ne maps induced by, say, the inclusion of a subspace, not to mention

the connecting homomorphism. What is missing is the information that homol-

ogy is natural with respect to re¬nements of covers as well as to maps of spaces.

Fortunately, the required condition was essentially obvious and led directly to the

notion of natural transformation. Only, in order to de¬ne natural transformation,

one ¬rst had to de¬ne functor and in order to do that, categories.

The other leading examples of natural transformations were the inclusion of

a vector space into its second dual and the commutator quotient of a group.

72 1 Categories

Somewhat surprisingly, in view of the fact that the original motivation came

from algebraic topology, is the fact that the Hurewicz homomorphism from the

fundamental group of a space to the ¬rst homology group of that space was not

recognized to be an example until later.

Later, Steenrod would state that no paper had in¬‚uenced his thinking more

than “The general theory of natural equivalences”. He explained that although

he had been searching for an axiomatic treatment of homology for years and that

he of course knew that homology acted on maps (or vice versa, if you prefer) it

had never occurred to him to try to base his axiomatics on this fact.

The next decisive step came when Mac Lane [1950] discovered that it was

possible to describe the cartesian product in a category by means of a universal

mapping property. In fact, he described the direct sum in what was eventually

recognized as an additive category by means of two mapping properties, one

describing it as a product and the other describing it as a sum. Mac Lane also

tried to axiomatize the notion of Abelian category but that was not completely

successful. No matter, the universal mapping property described by Mac Lane

had shown that it was possible to use categories as an aid to understanding.

Later on, Grothendieck succeeded in giving axioms for Abelian categories [1957]

and to actually prove something with them”the existence of injectives in an

Abelian category with su¬cient higher exactness properties. Thus Grothendieck

demonstrated that categories could be a tool for actually doing mathematics

and from then on the development was rapid. The next important step was the

discovery of adjoint functors by Kan [1958] and their use as an e¬ective tool in

the study of the homootopy theory of abstract simplicial sets.

After that the mainstream of developments in category theory split into

those primarily concerned with Abelian categories (Lubkin [1960], Freyd [1964],

Mitchell [1964], which are interesting but tangential to our main concerns here,

and those connected with the theories of triples and toposes of which we have

more to say later.

Elements

Although the thrust of category theory has been to abstract away from the use

of arguments involving elements, various authors have reintroduced one form or

another of generalized element in order to make categorical arguments parallel to

familiar elementwise arguments; for example, Mac Lane [1971, V111.4] for Abelian

categories and Kock [1981, part II] for Cartesian closed categories. It is not clear

whether this is only a temporary expedient to allow older mathematicians to argue

in familiar ways or will always form a permanent part of the subject. Perhaps

1.11 Notes to Chapter I 73

elements will disappear if Lawyers succeeds in his goal of grounding mathematics,

both in theory and in practice, on arrows and their composition.

An altogether deeper development has been that of Mitchell [1972] and others

of the internal language of a topos (developed thoroughly in a more general setting

by Makkai and Reyes [1977]). This allows one to develop arguments in a topos

as if the objects were sets, speci¬cally including some use of quanti¬ers, but with

restricted rules of deduction.

Limits

Limits were originally taken over directed index sets”partially ordered sets

in which every pair of elements has a lower bound. They were quickly generalized

to arbitrary index categories. We have changed this to graphs to re¬‚ect actual

mathematical practice: index categories are usually de¬ned ad hoc and the com-

position of arrows is rarely made explicit. It is in fact totally irrelevant and our

replacement of index categories by index graphs re¬‚ects this fact. There is no

gain”or loss”in generality thereby, only an alignment of theory with practice.

2

Toposes

A topos is, from one point of view, a category with certain properties charac-

teristic of the category of sets. A topos is not merely a generalized set theory,

but the very elementary constructions to be made in this chapter are best under-

stood, at least at ¬rst, by looking at what the constructions mean in Set. From

another point of view, a topos is an abstraction of the category of sheaves over a

topological space. This latter aspect is described in detail in this chapter.

Other treatments of toposes and sheaves are given by Johnstone [1977], Mac Lane

and Moerdijk [1992] and McLarty [1993].

2.1 Basic Ideas about Toposes

De¬nition of topos

We will take two properties of the category of sets”the existence of all ¬nite

limits and the fact that one can always form the set of subsets of a given set”as

the de¬ning properties for toposes.

For a ¬xed object A of a category E with ¬nite limits, ’ — A is a functor from

E to itself; if f : B ’ B , then f — A is the arrow (f —¦ p1 , p2 ): B — A ’ B —A. By

’ ’

composition, we then have a contravariant functor Sub(’ — A): E ’ Set. The ’

power object of A (if it exists) is an object PA which represents Sub(’ — A),

so that HomE (’, PA) Sub(’ — A) naturally. This says precisely that for

any arrow f : B ’ B, the following diagram commutes, where φ is the natural

’

isomorphism.

U φ(A, B)

E

HomE (B, PA) Sub(B — A)

HomE (f, PA) Sub(f — A) (1)

c c

E Sub(B — A)

HomE (B , PA)

φ(A, B )

The de¬nition of PA says that the “elements” of PA de¬ned on B are es-

sentially the same as the subobjects of B — A. In Set, a map f from B to the

74

2.1 Basic Ideas about Toposes 75

powerset of A is the same as a relation from B to A (b is related to a if and

only if a ∈ f (b)), hence the same as a subset of B — A. When B is the terminal

object (any singleton in Set), the “elements” of PA de¬ned on B are the subsets

of A 1 — A; thus PA is in fact the powerset of A.

In general, if the category has a terminal object 1 and P(1) exists, then Sub

is represented by P(1), since 1 — A ∼ A. This object P(1) is studied in detail in

=

Section 2.3.

De¬nition. A category E is a topos if E has ¬nite limits and every object

of E has a power object.

We will assume that PA is given functionally on ObE (it is determined up

to isomorphism in any case). This means that for each object A of E , a de¬nite

object PA of E is given which has the required universal mapping property.

The de¬nition of toposes has surprisingly powerful consequences. (For ex-

ample, toposes have all ¬nite colimits.) Probably the best analogy elsewhere in

mathematics in which a couple of mild-sounding hypotheses pick out a very nar-

row and interesting class of examples is the way in which the Cauchy-Riemann

equations select the analytic functions from all smooth functions of a complex

variable.

The properties of toposes will be developed extensively in this Chapter and

in Chapters 5 and 6. However, the rest of this section and the next are devoted

to examples.

Examples of toposes

(i) The category Set is evidently a topos. As we have already pointed out, if

X is a set, we can take PX to be the set of all subsets of X, but that does not

determine a unique topos structure on Set since we have a choice of φ in diagram

(1). The natural choice is to let φ: Hom(1, PB) ’ Sub(B) be the identity map

’

(thinking of an arrow from 1 to PB as an element of PB), but we could be

perverse and let φ of an element of the powerset be its complement.

(ii) To see a more interesting example, let G be a group and let G-Set be

the category of all sets on which G acts. The morphisms are equivariant G

homomorphisms. The existence of ¬nite (in fact, all) limits is an easy exercise.

They are calculated “pointwise”. If X is a G-set, let PX denote the set of all

subsets of X with G action given by gX0 = {gx | x ∈ X0 }. Note that a global

element of PX is a G-invariant subset of X.

Actually, the category of actions by a given monoid, with equivariant maps,

is a topos. That will follow from the discussion of functor categories below, since

76 2 Toposes

such a category is the same as a Set-valued functor category from a monoid

regarded as a category with one object.

Functor categories

An important example of toposes are Set-valued functor categories. In order to

prove that these categories are toposes, a number of elementary facts about them

are needed. A guiding principle in this development is the fact that Func(C , D)

inherits most of its properties from D (Exercise 25 of Section 1.7).

In this section, C is a ¬xed small category and E = Func(C op , Set). We will

outline the proof that E is a topos. Of course, everything we say in this section

is true of Func(C , Set), but because of the applications we prefer to state it this

way.

Each object C of C determines an evaluation map »C: E ’ Set, where

’

»C(F ) = F C and for γ: F ’ G, »C(γ) = γC.

’

Proposition 1. For each object C of C , the evaluation preserves all limits and

colimits. I.e.,“limits and colimits in E are computed pointwise”. In particular,

E is complete and cocomplete.

In other words, if D: I ’ E is a diagram in E , then (lim D)(C) = lim(D(C)).

’

The proof is in Exercise 25 of Section 1.7.

For a ¬xed object E, the functor ’ — E: E ’ E commutes with

Corollary 2. ’

all colimits.

Proof. The property claimed for this functor is valid when E = Set by Exercise 6,

and the Proposition allows one to extend it to an arbitrary functor category.

The fact that Sub is representable in a topos (by P(1)) means that it takes

colimits to limits. (Exercise 14 of Section 1.7). In particular, Sub( Ai ) =

Sub(Ai ) and if

p1

’ ’ B ’c C

’’

A ’’ ’’ (2)

’’

p2

is a coequalizer in a topos, then

Sub p1 Sub c

← ’ ’ ’ Sub(B) ← ’ ’ Sub(C)

’’’

Sub(A) ← ’ ’ ’ ’’’ (3)

’’’

Sub p2

is an equalizer. The ¬rst is easy to see in Set, but a direct proof of the second fact

in Set, not using the fact that Sub is representable, is surprisingly unintuitive.

As a step toward proving that E is a topos, we prove the fact just mentioned

for E .

2.1 Basic Ideas about Toposes 77

If D: I ’ E is a diagram in E , then

Proposition 3. ’

Sub(colim D) lim(Sub(D))

Proof. We use repeatedly the fact that the result is true in Set because there

Sub is representable by the two-element set. Let F = colim F D. For an object

i of I , the cocone F Di ’ F gives a cone Sub(F ) ’ Sub(F Di) which in turn

’ ’

gives Sub(F ) ’ lim Sub(F Di). Now to construct an arrow going the other way,

’

let EDi ⊆ F Di be a compatible family of subobjects, meaning that whenever i

’j

’

E F Dj

F Di

T T

E Edj

Edi

is a pullback. Let E = colim EDi. Since colimits preserve monos (by Propo-

sition 1, since they do so in Set), E is a subfunctor of F . This gives a map

lim Sub(F Di) ’ Sub(F ). Finally, to see that both composites are the identity,

’

it su¬ces to see that all those constructions are identical to the ones carried out

in SetOb(C ) , for which the result follows from Proposition 1 since it is true in Set.

E is a topos.

Theorem 4.

Proof. Finite limits, indeed all limits, exist by Proposition 1. As for P, for a

functor E, let PE be de¬ned by letting PE(A) be the set of subfunctors of

Hom(’, A) — E. It is straightforward to verify that PE is a functor.

We must show that subfunctors of F — E are in natural one to one corre-