<<

. 2
( 60 .)



>>

component of a natural transformation at a functor and a functor applied to a
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  
‚©

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

<<

. 2
( 60 .)



>>