A CATEGORICAL PRIMER CHRIS HILLMAN Contents 1. Introduction 1 2. Categories 9 3. Distinguished Objects and Arrows 13 4. Finite Operations within a Category 15 5. LimitOperations within a Category 21 6. Functors 24 7. Naturality 28 8. Operations on Categories 29 9. Adjoints 34 10. Topoi 45 11. Logic in a Topos 51 12. Models in a Topos 57 References 62 1. Introduction The language and elementary results of category theory have now pervaded a substantial part ofmathematics. Besides the everyday use of these concepts and results, we should note that categorical notions are fundamental in some of the most striking new devel- opments in mathematics. Nathan Jacobson [15] Category theory is bunk. Marshall Cohen Mathematics developed with great rapidity in the nineteenth century and has continued to develop with ever greater speed in this century. By the late 1930's the need for simple principles organizing the alarming proliferation of di(cid:11)erent mathematical structures was painfully apparent. This paper attempts to explain perhaps the most succesful such organizing principle which has yet emerged, the theory of categories. The central concepts of category theory are arrow (or morphism), functor, nat- urality, and adjoint. (In a moment,I shall try to give the reader some idea of the meaning of these words.) The (cid:12)rst three of these notions were introduced [6] by Date:October17,1997. Key words and phrases. tutorialpaper,categorytheory. 1 2 CHRIS HILLMAN Samuel Eilenberg and Saunders Mac Lane in 1945. Since then, category theory has developed as still another (cid:12)eld where one studies a particular mathematical structure| albeit, the structure of a \category" is very general and abstract, un- likemostimportantmathematicalstructures, whicharecomparativelyspeci(cid:12)c and concrete. Today, some mathematicians even call themselves \category theorists"; these mathematiciansprovetheoremsofgreatgenerality,sogreatthatconsiderable e(cid:11)ort may be required to \translate them" in order to apply them in the sort of situation likely to interest the \average mathematician". In contrast, this paper promotes the viewpoint that the four elementary concepts listed above are really very simple,and together forman organizingprinciple very useful for the \average mathematician". Indeed, I would go further. One of the most striking trends in science and engineering in the second half of this century, in my view, has been the in(cid:12)ltra- tion of quite sophisticated mathematicsinto these (cid:12)elds; indeed, some of the most imaginative mathematical ideas of recent years have been introduced by physi- cists, computer scientists and engineers, not \mathematicians". Consequently, I feel that \non-mathematicians"willalsobene(cid:12)t fromsome acquaintance with cat- egory theory. Therefore, this paper is aimed at the broadest possible audience, although inevitable limits of time and energy have forced me to assume some de- gree of mathematicalsophistication. and many of my examples will not be useful toreaders unacquaintedwithatleastundergraduate levelrealanalysisandmodern algebra. In the interest ofspace, mostproofs are leftas (valuableandby nomeans impossiblydemanding)excercises for the reader; however, I listbelow a number of references which contain complete proofs of manyof the most importantresults. Intheremainderofthissection Iwishtogivethereader the(cid:13)avorofcategorical thinking, and in particular, some intuition for the four central concepts: arrow, functor, naturality,and adjoint. Much of modern mathematicsis devoted to the study of \mappingswith struc- ture"andcollectionsofsuchmappings. Forinstance,every science andengineering student studies linear mappings between vector spaces and di(cid:11)erentiable real val- ued functions, i.e. di(cid:11)erentiable maps from Rto R. Math majors are almost cer- tain to be introduced to continuous mapsbetween topologicalspaces, and perhaps measure-preserving mappingsbetween measure spaces. Typically,the composition ofsuch\mappingswithstructure" isanother mappingofthesametype. Moreover, theidentitymaptakingeachelementtoitselfistriviallyamappingwiththedesired structure. A category is essentially a collection of such \mappingswith structure", calledarrows,between certains \setswithstructure", calledobjects,whichisclosed under compositionand which contains an identity arrow for every object. A huge number of such categories have been studied in modern mathematics. However, many important properties of arrows do not depend on the particular structures de(cid:12)ningthem,butonlyonhowtheycombineundercomposition. There- fore,wemayexpect thatconsiderablesimpli(cid:12)cationswillacrue fromstudying those properties of arrows which are expressible entirely in terms of composition. This is the program of category theory. Hopefully it will become clear in the course of reading this paper that this programhas been quite successful. Thefactthatincategorytheorywestudyonlythosepropertiesofour\mappings withstructure" which are expressible entirely interms ofcompositionexplainsour preference for the term arrow rather than morphism, for we can diagrammatically A CATEGORICAL PRIMER 3 represent the composition (cid:14)' where ':X !Y and :Y !Z as ' X (cid:0)(cid:0)(cid:0)(cid:0)! Y (cid:0)(cid:0)(cid:0)(cid:0)! Z Such diagrams are a very useful mental tool for grasping more complicated situa- tions involvingmultiplecompositions,as we shall see. Category theory involves at least two major conceptual shifts from the way the reader is likely to have previously thought about mathematics. First, arrows (our \mappingswithstructure") rather than objects(the \sets withstructure" our mappingsmapbetween) are nowtoberegarded asprimary. Forexample,topology is, according to our point of view, not the study of topological spaces so much as the study of continous mappings. As Bell [2] puts it, category theory is like a language in which the \verbs" are on an equal footingwith the \nouns". Second,\structural-context-dependent properties"aretobedisregardedinfavor of \structural-context-free properties". This transition is best explained by exam- ple,in the setting ofthe simplestcategory ofall,namelythe category consisting of allordinarymappingsbetween sets. Twofamiliarproperties amapping':X !Y mayor maynot have are: 1. ' maybe one-one, 2. ' maybe onto. The categorical expression of these properties are (respectively): 1. postcancellation property: for all (cid:11);(cid:12) :E !X, if '(cid:14)(cid:11)='(cid:14)(cid:12) then (cid:11)=(cid:12), 2. precancellation property: for all (cid:27);(cid:28) :Y !F, if (cid:27)(cid:14)'=(cid:28) (cid:14)' then (cid:27) =(cid:28). Notice that these categorical properties do not refer to \elements" or \sets" at all, only to the arrows of our category and to the compositionof such arrows. Toseethatthepostcancellationpropertyisequivalentto\one-one",observethat on the one hand, if ' is one-one and (cid:11)6=(cid:12), i.e. for some e2E, (cid:11)(e)6=(cid:12)(e), then 1 '(cid:14)(cid:11)(e) 6= '(cid:14)(cid:12)(e), so the contrapositive of the postcancellation property holds whenever ' is one-one. On the other hand, suppose x1 6= x2 but '(x1) = '(x2). De(cid:12)ne (cid:11);(cid:12) :B !X, where B =f0;1g,by (cid:11)(0)=x1; (cid:11)(1)=x2 (cid:12)(0)=x2; (cid:12)(1)=x1 Then '(cid:14)(cid:11) = '(cid:14)(cid:12) but (cid:11) 6= (cid:12), showing that the postcancellation property fails unless ' is one-one. Tosee thatthe precancellationproperty isequivalentto\onto",observe thaton theone hand,if' isontoand(cid:27)(cid:14)'=(cid:28)(cid:14)',then foranyy 2Y there issomex2X suchthat'(x)=y andthus(cid:27)(y) =(cid:27)(cid:14)'(x)=(cid:28)(cid:14)'(x)=(cid:28)(y),so(cid:27) =(cid:28). Thus,the precancellation property holds whenever ' is onto. On the other hand, suppose y0 is not in the image of '. De(cid:12)ne (cid:27);(cid:28) : Y ! B by setting (cid:27)(y0) = 1;(cid:28)(y0) = 0 and setting (cid:27)(y)=(cid:28)(y) =0 for ally 6=y0. Then (cid:27)(cid:14)'=(cid:28) (cid:14)' but (cid:27) 6=(cid:28),showing that the precancellation property fails unless ' is onto. Many of the most important problems of mathematics have the form: classify the objects of a category A up to isomorphism. (Forthe momentwecanthinkofan isomorphism as a bijective arrow whose inverse mappingis also a arrow.) To take just one example, two of the most impressive achievements of twentieth century 1The contrapositive of the logical statement p ) q is the statement :q ) :p; these two statementsarelogicallyequivalent. See[23]. 4 CHRIS HILLMAN mathematicshave been the complete classicationof(cid:12)nite dimensionalcomplexLie algebras (due to Cartan) and the complete classi(cid:12)cation of (cid:12)nite groups (due to many people; this has been called \the enormous theorem" because a complete proof would (cid:12)ll several volumes). Such classi(cid:12)cation problems are often simply 2 intractable , but in such cases it may happen that we can introduce a simpler category B and devise a functor which takes a arrow (cid:11) of A to a arrow F(cid:12) of B, andmoreover,does soinawaywhichpreserves compositions(andthus,anynotion in category theory, since as we said these are always de(cid:12)ned entirely in terms of compositions). Note that if the object A of A is the \domain" of (cid:11), this entails mapping A to the object FA of B, the \domain" of F(cid:11); likewise for codomains. The point is that if FA is non-isomorphicto FB, then A cannot be isomorphicto B;the formerstatementmaybeconsiderablyeasiertoprovethanthe latter. Thus, functors outofAprovide(atthe veryleast) atoolfor\partialclassi(cid:12)cation"ofthe objects of A. In many categories we can construct the product X (cid:2)E of two objects X;E. It is then natural to demand that X (cid:2)E be isomorphic to E (cid:2)X, perhaps by the isomorphism!X : X (cid:2)E ! E(cid:2)X (the reason for the subscript will become apparent in a moment). However, further thought reveals that we not only desire that some such isomorphismexist, we want it to be natural in the sense that if we \perturb"X byreplacingitbyY,where wehavea\perturbing"arrow':X !Y, then not onlyshould Y (cid:2)E be isomorphicto E(cid:2)Y,say by !Y :Y (cid:2)E !E(cid:2)Y, but we should have (1E (cid:2)')(cid:14)!X =!Y (cid:14)('(cid:2)1E) where 1E : E ! E is the identity arrow (analogous to the ordinary identity map) on E. This rather cumbersome requirement is what we mean by saying that the isomorphism X (cid:2)E ' E (cid:2)X is \natural in X". It is easier to understand this property in the form,\the followingdiagrammust commute:" '(cid:2)1E X (cid:2)E (cid:0)(cid:0)(cid:0)(cid:0)! Y (cid:2)E ? ? ? ? !Xy y!Y 1E(cid:2)' E(cid:2)X (cid:0)(cid:0)(cid:0)(cid:0)! E(cid:2)Y This diagram is said to be commutative because we demand that that two paths from X (cid:2)E to E (cid:2)Y ((cid:12)rst right then down or (cid:12)rst down and then right) must have exactly the same e(cid:11)ect (describe the same arrow). In any case, the point is that natural arrows belong to a collection of arrows which \behaves nicely under perturbation by other arrows". Manyusefulfunctors \comeinpairs". Speci(cid:12)cally,we mayhaveanaturalbijec- tion between the collection of all arrows FA ! B and the collection of all arrows A!GB. (\Natural" in the category of ordinary mappings between sets, that is.) 3 In this case, F and G are said to be adjoint functors . Numerous examples will be given ina later section, when (hopefully) the reader willbe ready to appreciate them. Despite this author's promise not to pass beyond the boundaries of what might be called \elementary category theory", i.e. the basic theory of arrows, functors, 2ShaharonShelahhas developeda theoryof classi(cid:12)cationwhichin certaincasesgivesuseful criteriaforwhenthishappens;see[13] 3Thenotionofadjointfunctorswasintroduced[16]byKanin1958. A CATEGORICAL PRIMER 5 naturality,and adjoints, I must confess that this paper does contain a bit more: a briefintroductiontotopostheory. Brie(cid:13)yput,atoposisacategorywhosestructure is so rich that it is capable of modellingany situation which can even be discussed in mathematicalterms. It turns out that each topos provides a model of (cid:12)rst order logic; speci(cid:12)cally, a formallanguageconsistingoftheoperationsofaHeytingalgebraonterms(Heyting algebras are slight generalizations of Boolean algebras) and also existential and universal quanti(cid:12)ers (9 and 8, respectively). In the simplest case, the category of sets, the associated logic is the usual (cid:12)rst order logic (Boolean algebra plus existential and universal quanti(cid:12)ers) which su(cid:14)ces to do \standard mathematics". This suggests, correctly, that topoi other than the category of sets may serve as the foundation of all of mathematics. Interestingly enough, passing from Boolean algebras to more general Heyting algebras involves adopting an \intuitionistic" logic in which the law of the excluded middle may fail. To a considerable extent, topos theory succeeded in unifying some of the most important advances in logic, topology, and algebraic geometry made in this century. In particular, the forcing constructionintroduced byPaulCohen andothers to\force"certain statementsto holdtrue turns out to be the sameas the shea(cid:12)(cid:12)cation construction introduced by Grothendieck in algebraic geometry. This same construction also turns up (in still another disguise) in the nonstandard analysis of AbrahamRobinson. Under the optimistic assumption that by the time the reader has (cid:12)nished this paper, he or she will be hungry for more information about categories, I will list here some general references for further reading. The very recent textbook by McLarty [17] is an excellent and quite readable introduction to category theory and topos theory. This paper might perhaps be best regarded as an invitation to read McLarty's book. The older book by Goldblatt [9] provides a leisurely introduction to category theory and topos theory, but is less readable in places. The interesting mathematical physics textbook of Geroch [8] is based entirely on categoricalnotionsandisquitereadable. ThegraduatealgebratextofJacobson[15] (Volume II) contains a chapter discussing category theory. At a more advanced level, the recent book by Moerdjik and Mac Lane [20] provides a concise overview ofcategory theory and,forthose already familiarwithmodernalgebraic geometry, a compellingintroduction to topos theory. At the research level, the book [19] is a standard reference for most basic notions of category theory. Finally, a word about the notation. This author has struggled to produce a notational system which helps the reader to keep clear the many di(cid:11)erent levels of structure in category theory. This is particularly important because, as we shall see, these levels are rather \(cid:13)exible" in that by a mere change of perspective we can easily (cid:12)nd ourselves working at a higher level. In this paper, elements 4 of sets are denoted by lower case roman letters, while sets and, more generally, objects are denoted by upper case roman letters. Arrows are denoted by lower case Greek letters, categories are (almost) denoted by upper case fraktur letters, whereas functors are denoted by upper case calligraphic letters. 4Exceptforthe\usualsuspects"B =f0;1g;N;Z;Q;R,andC. Certainotherexceptionstoour notationalruleswillbenotedastheyoccur. 6 CHRIS HILLMAN SYMBOL MEANING x;y;z elements y x exponential element (in a Heyting algebra) d(cid:11)e the name of the predicate (cid:11) (in a topos) X;Y;Z objects X (cid:2)Y product object X +Y sum (coproduct) object Y X exponential object X^ pullback (in pullback square) X(cid:20) pushout (in pushout square) (cid:3) a unique object (e.g. in one-object category) 0 initialobject 1 (cid:12)nal object lim ! Xj direct limitof the Xj lim Xj inverse limitof the Xj (cid:10) classifying object QntX set of quotient objects of X SubX set of subobjects of X X (cid:10) power object of X A;B;C subobjects AuB meet of A;B AtB join of A;B :A psuedo-complementof A A)B psuedo-complementof A relative to B A@B A is a subobject of B (cid:11);(cid:12);(cid:13) arrows (morphisms) dom domainoperator cod codomainoperator id operator assigning identity arrow to each object (cid:12)(cid:14)(cid:11) composite arrow (read right to left) ker kernel coker cokernel im image 1X identity arrow for object X = identity arrow (in a commutativediagram) UMP Universal Mapping Property (cid:7) uniquely de(cid:12)ned arrow (in a diagramfor a UMP) ! a unique arrow (e.g. into a (cid:12)nal object) (cid:25)X canonical arrow X (cid:2)Y !X (cid:17)X canonical arrow X +Y X " equalizing arrow (cid:20) coequalizing arrow (cid:11)^ pullback (in pullback square) (cid:11)(cid:20) pushout (in pushout square) !X component over X of a natural transformation A CATEGORICAL PRIMER 7 SYMBOL MEANING Hom(A;B) arrows (morphisms)fromA to B AutX automorphismsof X EndX endomorphismsof X A;B;C categories S;T topoi op C the opposite category for C (reverse allarrows) ! C the arrow category for C C=X slice category over X X=C coslice category under X ## ! C the category of diagramsX !Y in C &. C the category of diagramsX !E Y in C -% C the category of diagramsX E !Y in C J C the category of \J-shaped diagrams"in C, (J;(cid:20)) a preorder A(cid:2)B product category B A category of \B-shaped diagrams"in A F;G;H functors G(cid:14)F composite functor (read right to left) . right adjunction operator / left adjunction operator F aG F is the left adjoint of G (and G is the right adjoint of F) E\ homfunctor induced by E \ E homcofunctor induced by E ((cid:1))# Yoneda functor # ((cid:1)) Yoneda cofunctor (cid:3) slice change functor (pullback functor) induced by the arrow (cid:3) E slice functor (pullback functor) induced by the object E ? ((cid:1)) preimagecofunctor (cid:3) (cid:6) left adjoint to (naturally isomorphic to (cid:3)) (cid:3) (cid:5) right adjoint to 9 existential quantifyingfunctor induced by the arrow 8 universal quantifying functor induced by the arrow 9E existential quantifyingfunctor induced by the object E 8E universal quantifying functor induced by the object E Set sets and mappings (cid:19) inclusion map PX powerset of set X A\B intersection of subsets A;B A[B union of subsets A;B c A complementof subset A A(cid:26)B A is included in B X nY set di(cid:11)erence (cid:0)1 (cid:11) ((cid:1)) preimageunder mapping(cid:11) (cid:11)jE restriction of map(cid:11) to subset E of dom(cid:11) 8 CHRIS HILLMAN SYMBOL MEANING Pos posets and order preserving mappings Lat lattices and lattice homomorphisms Mat(R) matrices with entries in R, R a ring KLin K-linear spaces and K-linear mappings GGet G-sets and G-equivariantmaps,G a group RMod R-modules and R-homs,R a ring Grp groups and group homomorphisms Abg abelian groups Rng rings and ring homomorphisms Crg commutativerings Cru commutativerings with unit element Msr measure spaces and measure-preserving maps Top topologicalspaces and continuous maps Met metric spaces and contractive mappings Man smooth manifoldsand smooth maps ! Pair the category with two non-identity arrows U !V Pull the category with two non-identity arrows U !W V Push the category with two non-identity arrows U W !V BnX bundles over X and bundle homomorphisms (cid:0)1 (cid:25) Ex stalk (cid:25) (x) for bundle E !X EtX etales over X and etale homomorphisms PsX presheaves over X and presheaf homs ShX sheaves over X and sheaf homomorphisms Sec sheaf of sections cofunctor fromBnX to ShX Grm sheaf of germs cofunctor fromPsX to EtX ev evaluation arrow (for an exponential object) E E (cid:11) exponential arrow (cid:11) ((cid:1))=(cid:11)(cid:14)((cid:1)) (cid:31) A characteristic arrow for subobject A (predicate) > truth arrow ? falsehood arrow (cid:11)^(cid:12) conjuction of predicates (cid:11);(cid:12) (cid:11)_(cid:12) disjunction of predicates (cid:11);(cid:12) :(cid:11) negation of predicate (cid:11) (cid:11))(cid:12) (cid:11) implies(cid:12) (cid:20):1!(cid:10) proposition with no free variables (cid:11):X !(cid:10) proposition with one free variable (cid:18) :X(cid:2)Y !(cid:10) proposition with two free variables x;y h(x;y):(cid:18)i truth object of proposition (cid:18) (subobject of X (cid:2)Y) A CATEGORICAL PRIMER 9 2. Categories The universe raises its head and stares at itself through me. Russell Edson De(cid:12)nition 2.1. Suppose we have two collections 1. a collection of objects X, 2. a collection of arrows (or morphisms)', and also four operators 1. an operator cod assigning to each arrow ' an object cod', the codomainof ', 2. an operator dom assigning to each arrow ' an object dom', the domain of ', 5 3. an operator id assigning to each object X an arrow 1X, the identityarrow of X, which has dom1X =cod1X =X, 4. abinaryoperator,calledcomposition,assigningtocomposablepair((cid:11);(cid:12)); that is, to every pair of arrows ((cid:11);(cid:12)) with dom(cid:12) = cod(cid:11), an arrow (cid:12) (cid:14)(cid:11) with dom(cid:12)(cid:14)(cid:11) = dom(cid:11) cod(cid:12)(cid:14)(cid:11) = cod(cid:12) These ingredients form a category C if 1. the composition operator (cid:14) is associative, 2. for each object X, the identity arrow 1X can be cancelled from any composi- tion, in the sense that (a) for every arrow ' with dom'=X, we have '(cid:14)1X =', (b) for every arrow with cod =X, we have 1X (cid:14) = , The collection of all arrows ' with dom' = X and cod' = Y is denoted Hom(X;Y). Note that \object" and \arrow" remain unde(cid:12)ned terms. We shall ' ' oftenwriteanarrowasX !Y orY X; either notationdenotes thesamearrow, with dom'=X and cod'=Y. Sets and ordinary mappingsbetween them de(cid:12)ne the premier example of a cat- egory, denoted Set. Here, for any mapping ' : X ! Y, dom' is the ordinary domainX and cod' is the ordinary domainY, the identity arrow 1X for a set X is just the usualidentity mapx7!x, and the compositionoperator is the ordinary compositionof mappings(so if ((cid:11);(cid:12)) are composable,(cid:12)(cid:14)(cid:11) is de(cid:12)ned by mapping (cid:12)rst by (cid:11) and then by (cid:12)). Thecollectionofallsetsis\toobig"toitselfbeaset;itisaproperclass(see[10]). Categories whose objects form a set (rather than a proper class) are called small categories. In many categories, the objects are \sets with structure" and the arrows are \structure preserving mappingsbetween objects". Thisstructure isoften algebraic in nature. Such categories are called concrete categories. A more formalde(cid:12)ni- tion will be given in Section 6; here we illustrate the idea by giving a number of examples of concrete categories and non-concrete categories. Exercise: verify that the followingform categories: 5We honorthespecialroleof identityarrowsbybreakingourconventionof alwaysdenoting arrowsbylowercaseGreekletters. 10 CHRIS HILLMAN 1. Pos: (a) objects are posets (X;(cid:20)); 0 (b) arrows are order preserving maps ' : X ! Y where x (cid:20) x implies 0 0 '(x)(cid:20)'(x) for all x;x 2X. 2. Lat: (a) objects are lattices (X;_;^); 0 (b) arrows are lattice homomorphisms ' : X ! Y where '(x ^x) = 0 0 0 0 '(x)^'(x) and '(x_x)='(x)_'(x) for allx;x 2X. 3. KLin: (a) objects are K-linear spaces (X;+;0;(cid:1)); 0 0 (b) arrows are K-linear mappings ' : X ! Y where '(k(cid:1)x+k (cid:1)x) = 0 0 0 0 k(cid:1)'(x)+k (cid:1)'(x) for all k;k 2K and all x;x 2X. 4. RMod: (a) objects are R-modules,where R is a ring; (b) arrows are R-homomorphisms. (Note that a special case is Abg, the category of abelian groups, which is obtained when R=Z.) 5. GGet: (a) objects are G-sets (X;(cid:18)), where G is a group and (cid:18) : G(cid:2)X ! X is a left actionby G on X; (b) arrows are G-homomorpisms ' : X ! Y, where X = (X;(cid:18)), Y = (Y; ), and '(cid:14)(cid:18)(g)= (g)(cid:14)' for all g 2G. 6. Grp: (a) objects are groups; (b) arrows are group homomorphisms. 7. Rng: (a) objects are rings; (b) arrows are ring homomorphisms. 8. Cru: (a) objects are commutativerings R with unity 12R; (b) arrows are ring homomorphsisms(respecting the unities). For a very readable and elementary introduction to Pos and Lat, see [5]. For a concise introduction to GGet, see [11]; for details see [22]. For an excellent introduction to KLin;RMod;Grp;Rng;Cru, see [3]. Exercise: verify that the followingform categories: 1. Msr: (a) objects are measurespaces (X;m;(cid:22)),where misasigma-algebraofsub- sets of X and (cid:22) is a measure on m; (b) arrows are measure preserving mappings ' : X ! Y, where X = (cid:0)1 (X;m;(cid:22)),Y =(Y;n;(cid:23)),and (cid:22)(' (F))=(cid:23)(F) for allF 2n. 2. Top: (a) objectsaretopologicalspaces (X;s),wheresisthecollectionofopensets in X; (b) arrows are continuous mappings ' : X ! Y, where X = (X;s), (cid:0)1 Y =(Y;t), and ' (B)2s for allB 2t. 3. Met: (a) objects are metric spaces (X;dX), where dX is a metric on X;