Basic Category Theory
88 pages

Basic Category Theory

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
88 pages
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres


Basic Category TheoryJaap van OostenJaap van OostenDepartment of MathematicsUtrecht UniversityThe NetherlandsRevised, July 20021 Categories and Functors1.1 De nitions and examplesA categoryC is given by a collectionC of objects and a collectionC of arrows0 1which have the following structure. Each arrow has a domain and a codomain which are objects; one writesff : X ! Y or X ! Y if X is the domain of the arrow f, and Y itscodomain. One also writes X = dom(f) and Y = cod(f); Given two arrows f and g such that cod(f) = dom(g), the compositionof f and g, written gf, is de ned and has domain dom(f) and codomaincod(g):f g gf(X!Y !Z) 7! (X!Z) Composition is associative, that is: given f : X ! Y , g : Y ! Z andh :Z!W, h(gf) = (hg)f; For every object X there is an identity arrow id : X! X, satisfyingXid g =g for every g :Y !X and fid =f for every f :X!Y .X XExercise 1 Show that id is the unique arrow with domain X and codomainXX with this property.Instead of \arrow" we also use the terms \morphism" or \map".Examplesa) 1 is the category with one object and one arrow, id ;b) 0 is the empty category. It has no objects and no arrows.c) A preorder is a setX together with a binary relation which is re exiv e(i.e. xx for allx2X) and transitive (i.e.xy andyz imply xzfor all x;y;z2X). This can be viewed as a category, with set of objectsX and for every pair of objects (x;y) such that xy, exactly one arrow:x!y.Exercise 2 Prove this. Prove ...


Publié par
Publié le 11 octobre 2011
Nombre de lectures 52
Langue English


Basic Category Theory
Jaap van Oosten
Jaap van Oosten Department of Mathematics Utrecht University The Netherlands Revised, July 2002
Definitions and examples
AcategoryCis given by a collectionC0ofobjectsand a collectionC1 which have the following structure.
Each arrow has adomainand acodomainwhich are objects; one writes f:XYorXfYifXis the domain of the arrowf, andYits codomain. One also writesX= dom(f) andY= cod(f);
Given two arrowsfandgsuch that cod(f) = dom(g), thecomposition offandg, writtengf, is defined and has domain dom(f) and codomain cod(g): (XfYgZ)7→(XgfZ)
Composition isassociative, that is: givenf:X h:ZW,h(gf) = (hg)f;
For every objectXthere is anidentityarrow idX:XX, satisfying idXg=gfor everyg:YXandfidX=ffor everyf:XY.
Exercise 1Show that idXis theuniquearrow with domainXand codomain Xwith this property.
Instead of “arrow” we also use the terms “morphism” or “map”.
1is the category with one objectand one arrow, id;
0is the empty category. It has no objects and no arrows.
Apreorderis a setXtogether with a binary relationwhich is reflexive (i.e.xxfor allxX) and transitive (i.e.xyandyzimplyxz for allx, y, zX can be viewed as a category, with set of objects). This Xand for every pair of objects (x, y) such thatxy, exactly one arrow: xy.
Exercise 2 if also the converse: ProveProve this.Cis a category such thatC0 is a set, and such that for any two objectsX, YofCthere is at most one arrow: XY, thenC0is a preordered set.
Amonoidis a setXtogether with a binary operation, written like mul-tiplication:xyforx, yX, which is associative and has a unit element eX, satisfyingex=xe=xfor allxX monoid is a category. Such a with one object, and an arrowxfor everyxX.
Set is the category which has the class of all sets as objects, and functions between sets as arrows.
Most basic categories have as objects certain mathematical structures, and the structure-preserving functions as morphisms. Examples:
f) Top is the category of topological spaces and continuous functions.
g) Grp is the category of groups and group homomorphisms.
h) Rng is the category of rings and ring homomorphisms.
i) Grph is the category of graphs and graph homomorphisms.
j) Pos is the category of partially ordered sets and monotone functions.
Given two categories C and D, afunctorF:C → Dconsists of operations F0:C0→ D0andF1:C1→ D1, such that for eachf:XY,F1(f) : F0(X)F0(Y) and:
forXfYgZ,F1(gf) =F1(g)F1(f);
F1(idX) = idF0(X)for eachX∈ C0. But usually we write justFinstead ofF0, F1.
a) There is a functorU: TopSet which assigns to any topological space X “forgets” the Weits underlying set. it call this functor “forgetful”: mathematical structure. Similarly, there are forgetful functors GrpSet, GrphSet, RngSet, PosSet etcetera;
For every category C there is a unique functorC →1and a unique one 0→ C;
Given two categories C and D we can define theproduct categoryC × D which has as objects pairs (C, D)∈ C0× D0, and as arrows:(C, D)(C0, D0) pairs (f, g) withf:CC0in C, andg:DD0in D. There are functorsπ0:C × D → Candπ1:C × D → D;
Given two functorsF:C → DandG:D → Eone can define the compositionGF:C → E composition is of course associative and. This since we have, for any categoryC, theidentity functorC → C, we have a category Cat which has categories as objects and functors as morphisms. ˜ Given a setA, consider the setAof stringsa1. . . anon the alphabet AA1(A1consists of elementsa1for each elementaofA; the sets AandA1are disjoint and in 1-1 correspondence with each other), such that for noxA,xx1orx1xis a substring ofa1. . . an two. Given ~ ~ such strings~a=a1. . . an, b=b1. . . bm, let~ab?the string formed by first takinga1. . . anb1. . . bmand then removing from this string, successively, ˜ substrings of formxx1orx1x, until one has an element ofA. ˜ ˜ This defines a group structure onA.Ais called thefree groupon the set A.
Exercise 3Prove this, and prove that the assignmentA functor: Set functor is called theGrp. Thisfree functor.
˜ Ais
Every directed graph can be made into a category as follows: the objects are the vertices of the graph and the arrows are paths in the graph. This defines a functor from the category Dgrph of directed graphs to Cat. The image of a directed graphDunder this functor is called the category generatedby the graphD.
Quotient categories. Given a category C, acongruence relationonC specifies, for each pair of objectsX, Y, an equivalence relationX,Yon the class of arrowsC(X, Y) which have domainXand codomainY, such that
forf, g:XYandh:YZ, iffX,YgthenhfX,Zhg; forf:XYandg, h:YZ, ifgY,ZhthengfX,Zhf.
Given such a congruence relationonC, one can form the quotient cat-egoryC/which has the same objects asC, and arrowsXYare X Y-equivalence classes of arrowsXYin C. ,
Exercise 4Show this and show that there is a functorC → C/, which takes each arrow ofCto its equivalence class.
An example of this is the following (“homotopy”). Given a topological spaceXand pointsx, yX, apathfromxtoyis a continuous mapping ffrom some closed interval [0, a] toXwithf(0) =xandf(a) =y. If f: [0, a]Xis a path fromxtoyandg: [0, b]Xis a path fromytoz there is a pathgf: [0, a+b]X(defined bygf(t) =gf((tt)a)telsea) fromxtoz. This makesXinto a category, thepath categoryofX, and of course this also defines a functor Top given pathsCat. Now f: [0, a]X,g: [0, b]X, both fromxtoy, one can definefx,ygif there is a continuous mapF:AXwhereAis the area:
inR2, such that
F(t,0) = F(t,1) = F(0, s) = F(s, t) =
(b,1) FFF FF FFF (a,0)
f(t) g(t) x s[0,1] y(s, t) on the segment (b,1)(a,0)
One can easily show that this is a congruence relation. The quotient of the path category by this congruence relation is a category called the category ofhomotopy classesof paths inX.
letCbe a category such that for every pair (X, Y) of objects the class C(X, Y) of arrows fromXtoYis a set (suchCis calledlocally small). For any objectCofCthen, there is a functorhC:C →Set which assigns to any objectC0the setC(C, C0). Any arrowf:C0C00gives by composition a functionC(C, C0)→ C(C, C00 A), so we have a functor. functor of this form is called arepresentable functor.
LetCbe a category andCan object ofC. Theslice categoryC/Chas as objects all arrowsgwhich have codomainC. An arrow fromg:DC toh:ECinC/Cis an arrowk:DEinCsuch thathk=g. Draw like: DkE @@@@~~~ g@@@~~~~h C We say thatthis diagram commutesif we mean thathk=g.
Exercise 5Convince yourself that the assignmentC functorC →Cat.
7→ C/Cgives rise to a
k) Recall that for every group (G,) we can form a group (G, ?) by putting f ? g=gf. For categories the same construction is available: givenCwe can form a categoryCopthe same objects and arrows as C, but withwhich has reversed direction; so iff:XYin C thenf:YXinCop. To ¯ make it notationally clear, writeffor the arrowYXcorresponding to f:XYin C. Composition inCopis defined by:
¯ f g¯ =gf
Often one reads the term “contravariant functor” in the literature. What I call functor, is then called “covariant functor”. A contravariant functorF fromCtoDinverts the direction of the arrows, soF1(f) :F0(cod(f))F0(dom(f)) for arrowsfinC. In other words, a contravariant functor fromCtoDis a functor fromCop→ D(equivalently, fromCtoDop). Of course, any functorF:C → Dgives a functorFop:Cop→ Dop. In fact, we have a functor ()op: CatCat.
Exercise 6LetCbe locally small. Show that there is a functor (the “Hom functor”)C(,) :Cop× C →Set, assigning to the pair (A, B) of objects ofC, the setC(A, B).
Given a partially ordered set (X,) we make a topological space by defin-ingUXto be open iff for allx, yX,xyandxUimplyyU (Uis “upwards closed”, or an “upper set”). This is a topology, called the Alexandroff topologyw.r.t. the order.
If (X,) and (Y,) are two partially ordered sets, a functionf:XYmonotone for the orderings if and only ifis fis continuous for the Alexandroff topologies. This gives an important functor: PosTop.
Exercise 7the construction of the quotient category in example g)Show that generalizes that of a quotient group by a normal subgroup. That is, regard a groupGas a category with one object; show that there is a bijection between congruence relations onGand normal subgroups ofG, and that for a normal subgroupNofG, the quotient category by the congruence relation correspond-ing toN, is to the quotient groupG/N.
“Abelianization”. Let Abgp be the category of abelian groups and ho-momorphisms. For every groupGthe subgroup [G, G] generated by all elements of formaba1b1is a normal subgroup.G/[G, G] is abelian, and for every group homomorphismφ:GHwithHabelian, there is a ¯ unique homomorphismφ:G/[G, G]Hsuch that the diagram
G v φ {{vvvp????????vvvvvG/[G, G]φ¯H
commutes. Show that this gives a functor: GrpAbgp.
“Specialization ordering”. Given a topological spaceX, you can define a preordersonX sayas follows:xsyif for all open setsU, ifxU thenyU.sis a partial order iffXis aT0-space. For many spaces,sis trivial (in particular whenXisT1) but in caseX is for example the Alexandroff topology on a poset (X,) as in l), then xsyiffxy.
Exercise 8Iff:XYa continuous map of topological spaces thenis fis monotone w.r.t. the specialization orderingss. This defines a functor TopPreord, where Preord is the category of preorders and monotone functions.
Exercise 9LetXbe the category defined as follows: objects are pairs (I , x) whereIis an open interval inRandxI. Morphisms (I , x)(J, y) are differentiable functionsf:IJsuch thatf(x) =y. LetYbe the (multiplicative) monoidR, considered as a category. Show that the operation which sends an arrowf: (I , x)(J, y) tof0(x), determines a functorXYfact of elementary Calculus does this rely? which basic . On
1.2 Some special objects and arrows
We call an arrowf:ABmono(or a monomorphism, or monomorphic) in a categoryC, if for any other objectCand for any pair of arrowsg, h:CA, f g=f himpliesg=h.
In Set,fis mono ifff same is true for Grp, Theis an injective function. Grph, Rng, Preord, Pos,. . . We call an arrowf:ABepi(epimorphism, epimorphic) if for any pair g, h:BC,gf=hfimpliesg=h. The definition of epi is “dual” to the definition of mono. That is,fis epi in the categoryCif and only iffis mono inCop, and vice versa. In general, given a propertyP . . we can associate withof an object, arrow, diagram,.Pthe dual propertyPop: the object or arrow has propertyPopinCiff it hasPinCop. Theduality principle, a very important, albeit trivial, principle in category theory, says that any valid statement about categories, involving the proper-tiesP1, . . . , Pnimplies the “dualized” statement (where direction of arrows is reversed) with thePireplaced byPiop. Example. Ifgfis mono, thenfis mono. this, “by duality”, if Fromf gis epi, thenfis epi.
Exercise 10Prove these statements.
In Set,fis epi ifffis a surjective function. This holds (less trivially!) also for Grp, but not for Mon, the category of monoids and monoid homomorphisms: Example the embedding. In Mon,NZis an epimorphism. For, supposeZf(M, e, ? monoid homomorphisms which agree on) two g the nonnegative integers. Then
f(1) =f(1)? g(1)? g(1) =f(1)? f(1)? g(1) =g(1)
sofandgagree on the whole ofZ. We say a functorFpreservesa propertyPif whenever an object or arrow (or. . . ) hasP, itsF-image does so. Now a functor does not in general preserve monos or epis: the example of Mon shows that the forgetful functor MonSet does not preserve epis. An epif:ABis calledsplitif there isg:BAsuch thatf g= idB (other names: in this casegis called asectionoff, andfaretractionofg).
Exercise 11 that every functor ProveBy duality, define what a split mono is. preserves split epis and monos.
A morphismf:ABis anisomorphismif there isg:BAsuch that f g= idBandgf= idA call. Wegtheinverseoff(and vice versa, of course); it is unique if it exists. We also writeg=f1. Every functor preserves isomorphisms.
Exercise 12In Set, every arrow which is both epi and mono is an isomorphism. Not so in Mon, as we have seen. Here’s another one: let CRng1 be the category of commutative rings with 1, and ring homomorphisms (preserving 1) as arrows. Show that the embeddingZQis epi in CRng1.
Exercise 13
If two off,gandf gare iso, then so is the third;
ii) iffis epi and split mono, it is iso;
iii) iffis split epi and mono,fis iso.
A functorFreflectsa propertyPif whenever theF-image of something (object, arrow,. . . ) hasP, then that something has. A functorF:C → Dis calledfullif for every two objectsA, BofC, F:C(A, B)→ D(F A, F B) is a surjection.Fisfaithfulif this map is always injective.
Exercise 14
A faithful functor reflects epis and monos.
An objectXis calledterminalif for any objectYthere is exactly one morphism YX Dually,in the category.Xisinitialif for allYthere is exactly one XY.
Exercise 15A full and faithful functor reflects the property of being a terminal (or initial) object.
Exercise 16IfXandX0are two terminal objects, they areisomorphic, that is there exists an isomorphism between them. Same for initial objects.
Exercise 17Letbe a congruence on the categoryC, as in example g). Show: iffandgare arrowsXYwith inversesf1andg1respectively, thenfg ifff1g1.
The Yoneda lemma
Anatural transformationbetween two functorsF, G:C → Dconsists of a family of morphisms (µC:F CGC)C∈C0indexed by the collection of objects ofC, satisfying the following requirement: for every morphismf:CC0inC, the diagram F CµCGC
F f
F C0µC0
commutes inD say We(the diagram above is called the naturality square). µ= (µC)C∈C0:FGand we callµCthecomponent atCof the natural transformationµ. Given natural transformationsµ:FGandν:GHwe have a natural transformationνµ= (νCµC)C:FH, and with this composition there is a categoryDCwith functorsF:C → Das objects, and natural transformations as arrows. One of the points of the naturality square condition in the definition of a natural transformation is given by the following proposition. Compare with the situation in Set: denoting the set of all functions fromXtoYbyYX, for any setZthere is a bijection between functionsZYXand functionsZ×XY (Set iscartesian closed chapter 7).: see
Proposition 2.1
For categoriesC,DandEthere is a bijection:
Cat(E × C,D)Cat(E,DC)
Proof. GivenF:E × C → Ddefine for every objectEofEthe functor FE:C → DbyFE(C) =F(E, C); forf:CC0letFE(f) =F(idE, f) : FE(C) =F(E, C)F(E, C0) =FE(C0) Giveng:EE0inE, the family (F(g,idC) :FE(C)FE0(C))C∈C0is a natural transformation:FEFE0 we have a functor. SoF7→F():E → DC. n a functorG:EC˜: → DE ×Con Conversely, give→ Dwe define a functorG ˜ ˜ objects byG(E, C) =G(E)(C), and on arrows byG(g, f) =G(g)C0G(E)(f) = G(E0)(f)G(g)C:
G(E)(C) =G˜(E, C)G(g)CG(˜E0, C) =G(E0)(C)
˜ G(E, C0)
˜ G(E0, C0) =G(E0)(C0)
˜ Exercise 18Write out the details. that CheckGas just defined, is a functor, and that the two operations
Cat(E × C,D)
are inverse to each other.
An important example of natural transformations arises from the functorshC: CopSet (see example i) in the preceding chapter); defined on objects by hC(C0) =C(C0, C) and on arrowsf:C00C0so thathC(f) is composition withf:C(C0, C)→ C(C00, C). Giveng:C1C2there is a natural transformation
whose components are composition withg.
Exercise 19Spell this out.
We have, in other words, a functor
h():C →SetCop
This functor is also often denoted byYand answers to the nameYoneda em-bedding. An embedding is a functor which is full and faithful and injective on objects. ThatYis injective on objects is easy to see, because idChC(C) for each object C, and idCis in no other sethD(E); thatYis full and faithful follows from the following
Proposition 2.2 (Yoneda lemma)For every objectFofSetCopand every objectCofC, there is a bijectionfC,F: SetCop(hC, F)F(C). Moreover, this bijection isnaturalinCandFin the following sense: giveng:C0CinC andµ:FF0inSetCop, the diagram
commutes inSet.
SetCop(hC, F)
SetCop(hC0, F0)fC0,F0
Proof. For every objectC0ofC, every elementfofhC(C0) =C(C0, C) is equal to idCfwhich ishC(f)(idC).
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents