natural transformation. Although these two notions are semantically distinct,

they are syntactically identical; much progress in mathematics comes about from

muddying such distinctions.

Our most signi¬cant departures from standard terminology are the adoption

of Freyd™s use of “exact” to denote a category which has all ¬nite limits and

colimits or for a functor which preserves them and the use of “sketch” in a sense

di¬erent from that of Ehresmann. Our sketches convey the same information

while being conceptually closer to naive theories.

There are two di¬erent categories of toposes: one in which the geometric

aspect is in the ascendent and the other in which the logic is predominant. The

distinction is analogous to the one between the categories of complete Heyting

algebras and that of locales. Thinking of toposes as models of a theory emphasizes

the second aspect and that is the point of view we adopt. In particular, we use the

term “subtopos” for a subcategory of a topos which is a topos, which is di¬erent

from the geometric usage in which the right adjoint is supposed an embedding.

Historical notes

At the end of many of the chapters we have added historical notes. It should

be understood that these are not History as that term is understood by the

historian. They are at best the raw material of history.

At the end of the ¬rst draft we made some not very systematic attempts to

verify the accuracy of the historical notes. We discovered that our notes were

divided into two classes: those describing events that one of us had directly partic-

ipated in and those that were wrong! The latter were what one might conjecture

on the basis of the written record, and we discovered that the written record is

invariably misleading. Our notes now make only statements we could verify from

xi

the participants. Thus they are incomplete, but we have some con¬dence that

those that remain have some relation to the actual events.

What is expected from the reader

We assume that the reader is familiar with concepts typically developed in

¬rst-year graduate courses, such as group, ring, topological space, and so on.

The elementary facts about sheaves which are needed are developed in the book.

The reader who is familiar with the elements of category theory including adjoint

functors can skip nearly all of Chapter 1; he may need to learn the element

notation introduced in Section 1.4 and the square bracket notation de¬ned in

Sections 1.6 and 1.7.

Most of the exercises provide examples or develop the theory further. We

have mostly avoided including exercises asking for routine veri¬cations or giving

trivial examples. On the other hand, most routine veri¬cations are omitted from

the text; usually, in a proof, the basic construction is given and the veri¬cation

that it works is left to the reader (but the ¬rst time a veri¬cation of a given

type is used it is given in more detail). This means that if you want to gain a

thorough understanding of the material, you should be prepared to stop every

few sentences (or even every sentence) and verify the claims made there in detail.

You should be warned that a statement such as, “It is easy to see...” does not

mean it is necessarily easy to see without pencil and paper!

Acknowledgments

We are grateful to Barry Jay, Peter Johnstone, Anders Linn´r, John A. Power

e

and Philip Scott for reading portions of the manuscript and making many correc-

tions and suggestions for changes; we are particularly grateful to Barry Jay, who

up to two weeks before the ¬nal printout was still ¬nding many obscurities and ty-

poes and some genuine mathematical errors. We have bene¬ted from stimulating

and informative discussions with many people including, but not limited to Marta

Bunge, Radu Diaconescu, John W. Duskin, Michael Fourman, Peter Freyd, John

Gray, Barry Jay, Peter Johnstone, Andr´ Joyal, Joachim Lambek, F. William

e

Lawvere, Colin McLarty, Michael Makkai and Myles Tierney. We would like to

give especial thanks to Roberto Minio who expended enormous e¬ort in turn-

ing a string of several million zeroes and ones into the text you see before you;

John Aronis also helped in this endeavor, which took place at Carnegie-Mellon

University with the encouragement and cooperation of Dana Scott.

We are also grateful to Beno Eckmann, who brought us together at the

Forschungsinstitut f¨r Mathematik, ETH Z¨rich. If Eilenberg and Mac Lane

u u

xii

were the fathers of categorical algebra, Eckmann was in a very real sense the

godfather. Many of the most important developments in categorical algebra and

categorical logic took place in the o¬ces of the Forschungsinstitut, which was

then on Zehnderweg.

Portions of this book were written while both authors were on sabbatical

leave from their respective institutions. The ¬rst author was supported during

the writing by grants from the National Science and Engineering Research Coun-

´

cil, by a team grant from the Minist`re de l™Education du Qu´bec and by a grant

e e

´

to the Groupe Interuniversitaire en Etudes Cat´gories, also from the Minist`re de

e e

´

l™Education du Qu´bec. The second author was partially supported by DOE con-

e

tract DE-AC01-80RA5256. In addition we received considerable free computing

time from the McGill University Computing Centre.

xiii

Chapter dependency chart

1

d

d

d

d

d

d

3 2

d

d

d

d

d

d

d

d

d

d

d d

9 5 4

6

7

8

1

Categories

1.1 De¬nition of category

A category C consists of two collections, Ob(C ), whose elements are the objects

of C , and Ar(C ), the arrows (or morphisms or maps) of C . To each arrow

is assigned a pair of objects, called the source (or domain) and the target (or

codomain) of the arrow. The notation f : A ’ B means that f as an arrow

’

with source A and target B. If f : A ’ B and g: B ’ C are two arrows, there

’ ’

is an arrow g —¦ f : A ’ C called the composite of g and f . The composite is

’

not de¬ned otherwise. We often write gf instead of g —¦ f when there is no danger

of confusion. For each object A there is an arrow idA (often written 1A or just

1, depending on the context), called the identity of A, whose source and target

are both A. These data are subject to the following axioms:

1. for f : A ’ B,

’

f —¦ idA = idB —¦ f = f ;

2. for f : A ’ B, g: B ’ C, h: C ’ D,

’ ’ ’

h —¦ (g —¦ f ) = (h —¦ g) —¦ f

A category consists of two “collections”, the one of sets and the one of arrows.

These collections are not assumed to be sets and in many interesting cases they

are not, as will be seen. When the set of arrows is a set then the category is said

to be small. It follows in that case that the set of objects is also a set since there

is one-one correspondence between the objects and the identity arrows.

While we do not suppose in general that the arrows form a set, we do usually

suppose (and will, unless it is explicitly mentioned to the contrary) that when we

¬x two objects A and B of C , that the set of arrows with source A and target B

is a set. This set is denoted HomC (A, B). We will omit the subscript denoting

the category whenever we can get away with it. A set of the form Hom(A, B)

is called a homset. Categories that satisfy this condition are said to be locally

small.

Many familiar examples of categories will occur immediately to the reader,

such as the category Set of sets and set functions, the category Grp of groups

1

2 1 Categories

and homomorphisms, and the category T of topological spaces and continuous

op

maps. In each of these cases, the composition operation on arrows is the usual

composition of functions.

A more interesting example is the category whose objects are topological

spaces and whose arrows are homotopy classes of continuous maps. Because ho-

motopy is compatible with composition, homotopy classes of continuous functions

behave like functions (they have sources and targets, they compose, etc.) but are

not functions. This category is usually known as the category of homotopy types.

All but the last example are of categories whose objects are sets with mathe-

matical structure and the morphisms are functions which preserve the structure.

Many mathematical structures are themselves categories. For example, one can

consider any group G as a category with exactly one object; its arrows are the

elements of G regarded as having the single object as both source and target.

Composition is the group multiplication, and the group identity is the identity

arrow. This construction works for monoids as well. In fact, a monoid can be

de¬ned as a category with exactly one object.

A poset (partially ordered set) can also be regarded as a category: its objects

are its elements, and there is exactly one arrow from an element x to an element

y if and only if x ¤ y; otherwise there are no arrows from x to y. Composition

is forced by transitivity and identity arrows by re¬‚exivity. Thus a category can

be thought of as a generalized poset. This perception is important, since many

of the fundamental concepts of category theory specialize to nontrivial and often

well-known concepts for posets (the reader is urged to ¬ll in the details in each

case).

In the above examples, we have described categories by specifying both their

objects and their arrows. Informally, it is very common to name the objects only;

the reader is supposed to supply the arrows based on his general knowledge. If

there is any doubt, it is, of course, necessary to describe the arrows as well.

Sometimes there are two or more categories in general use with the same objects

but di¬erent arrows. For example, the following three categories all have the same

objects: complete sup-semilattices, complete inf-semilattices, complete lattices.

Further variations can be created according as the arrows are required to preserve

the top (empty inf) or bottom (empty sup) or both.

Some constructions for categories

A subcategory D of a category C is a pair of subsets DO and DA of the

objects and arrows of C respectively, with the following properties.

1. If f ∈ DA then the source and target of f are in DO .

1.1 De¬nition of category 3

2. If C ∈ DO , then idC ∈ DA .

3. If f , g ∈ DA are a composable pair of arrows then g —¦ f ∈ DA .

The subcategory is full if for any C, D ∈ DO , if f : C ’ D in C , then

’

f ∈ DA . For example, the category of Abelian groups is a full subcategory of the

category of groups (every homomorphism of groups between Abelian groups is a

homomorphism of Abelian groups), whereas the category of monoids (semigroups

with identity element) is a subcategory, but not a full subcategory, of the category

of semigroups (a semigroup homomorphism need not preserve 1).

One also constructs the product C — D of two categories C and D in the

obvious way: the objects of C — D are pairs (A, B) with A an object of C and

B an object of D. An arrow

(f, g): (A, B) ’ (A , B )

’

has f : A ’ A in C and g: B ’ B in D. Composition is coordinatewise.

’ ’

To de¬ne the next concept, we need the idea of commutative diagram. A

diagram is said to commute if any two paths between the same nodes compose

to give the same morphism. The formal de¬nition of diagram and commutative

diagram is given in 1.7.

If A is any object of a category C , the slice category C /A of objects of C

over A has as objects all arrows of C with target A. An arrow of C /A from

f : B ’ A to g: C ’ A is an arrow h: B ’ C making the following diagram

’ ’ ’

commute.

h EC

B

d

g

fd

d

‚©

d

A

In this case, one sometimes writes h: f ’ g over A.

’

It is useful to think of an object of Set/A as an A-indexed family of disjoint

sets (the inverse images of the elements of A). The commutativity of the above

diagram means that the function h is consistent with the decomposition of B and

C into disjoint sets.

De¬nitions without using elements

The introduction of categories as a part of the language of mathematics has

made possible a fundamental, intrinsically categorical technique: the element-free

de¬nition of mathematical properties by means of commutative diagrams, limits