Basic Category Theory

Description

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 ...

Informations

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

Extrait

Basic Category Theory

Jaap van Oosten

Jaap van Oosten Department of Mathematics Utrecht University The Netherlands Revised, July 2002

1

1.1

Categories

and

Functors

Definitions and examples

AcategoryCis given by a collectionC 0 ofobjectsand a collectionC 1 which have the following structure.

•

•

•

•

ofarrows

Each arrow has adomainand acodomainwhich are objects; one writes f:X→YorX f →YifXis 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): (X f Y→ g Z)7→(X g → f Z) →

Composition isassociative, that is: givenf:X h:Z→W,h(gf) = (hg)f;

→Y,g

:Y

→Zand

For every objectXthere is anidentityarrow id X :X→X, satisfying id X g=gfor everyg:Y→Xandfid X =ffor everyf:X→Y.

Exercise 1Show that id X is theuniquearrow with domainXand codomain Xwith this property.

Instead of “arrow” we also use the terms “morphism” or “map”.

Examples

a)

b)

c)

1is the category with one object∗and one arrow, id ∗ ;

0is the empty category. It has no objects and no arrows.

Apreorderis a setXtogether with a binary relation≤which is reflexive (i.e.x≤xfor allx∈X) and transitive (i.e.x≤yandy≤zimplyx≤z for allx, y, z∈X can be viewed as a category, with set of objects). This Xand for every pair of objects (x, y) such thatx≤y, exactly one arrow: x→y.

Exercise 2 if also the converse: ProveProve this.Cis a category such thatC 0 is a set, and such that for any two objectsX, YofCthere is at most one arrow: X→Y, thenC 0 is a preordered set.

d)

e)

Amonoidis a setXtogether with a binary operation, written like mul- tiplication:xyforx, y∈X, which is associative and has a unit element e∈X, satisfyingex=xe=xfor allx∈X monoid is a category. Such a with one object, and an arrowxfor everyx∈X.

Set is the category which has the class of all sets as objects, and functions between sets as arrows.

1

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 F 0 :C 0 → D 0 andF 1 :C 1 → D 1 , such that for eachf:X→Y,F 1 (f) : F 0 (X)→F 0 (Y) and:

•forX f →Y g →Z,F 1 (gf) =F 1 (g)F 1 (f);

•F 1 (id X ) = id F 0 (X) for eachX∈ C 0 . But usually we write justFinstead ofF 0 , F 1 .

Examples.

a) There is a functorU: Top→Set which assigns to any topological space X “forgets” the Weits underlying set. it call this functor “forgetful”: mathematical structure. Similarly, there are forgetful functors Grp→Set, Grph→Set, Rng→Set, Pos→Set etcetera;

b)

c)

d)

e)

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)∈ C 0 × D 0 , and as arrows:(C, D)→ (C 0 , D 0 ) pairs (f, g) withf:C→C 0 in C, andg:D→D 0 in 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 stringsa 1 . . . a n on the alphabet A∪A −1 (A −1 consists of elementsa −1 for each elementaofA; the sets AandA −1 are disjoint and in 1-1 correspondence with each other), such that for nox∈A,xx −1 orx −1 xis a substring ofa 1 . . . a n  two. Given ~ ~ such strings~a=a 1 . . . a n , b=b 1 . . . b m , let~ab?the string formed by first takinga 1 . . . a n b 1 . . . b m and then removing from this string, successively, ˜ substrings of formxx −1 orx −1 x, until one has an element ofA. ˜ ˜ This defines a group structure onA.Ais called thefree groupon the set A.

2

Exercise 3Prove this, and prove that the assignmentA functor: Set→ functor is called theGrp. Thisfree functor.

f)

g)

7→

˜ Ais

part

of

a

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 relation∼ X,Y on the class of arrowsC(X, Y) which have domainXand codomainY, such that

•forf, g:X→Yandh:Y→Z, iff∼ X,Y gthenhf∼ X,Z hg; •forf:X→Yandg, h:Y→Z, ifg∼ Y,Z hthengf X,Z hf. ∼

Given such a congruence relation∼onC, one can form the quotient cat- egoryC/∼which has the same objects asC, and arrowsX→Yare ∼ X Y -equivalence classes of arrowsX→Yin C. ,

Exercise 4Show this and show that there is a functorC → C/∼, which takes each arrow ofCto its equivalence class.

h)

An example of this is the following (“homotopy”). Given a topological spaceXand pointsx, y∈X, 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) =  g f ( ( t t) −a) t els ≤ e a ) 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 definef∼ x,y gif there is a continuous mapF:A→XwhereAis the area:

inR 2 , such that

F(t,0) = F(t,1) = F(0, s) = F(s, t) =

(0,1)

(0,0)

(b,1) F F F F F F F F (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.

3

i)

j)

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 functorh C :C →Set which assigns to any objectC 0 the setC(C, C 0 ). Any arrowf:C 0 →C 00 gives by composition a functionC(C, C 0 )→ C(C, C 00  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:D→C toh:E→CinC/Cis an arrowk:D→EinCsuch thathk=g. Draw like: D k E @ @ @ @~ ~ ~ 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=g∙f. For categories the same construction is available: givenCwe can form a categoryC op the same objects and arrows as C, but withwhich has reversed direction; so iff:X→Yin C thenf:Y→XinC op . To ¯ make it notationally clear, writeffor the arrowY→Xcorresponding to f:X→Yin C. Composition inC op is 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, soF 1 (f) :F 0 (cod(f))→ F 0 (dom(f)) for arrowsfinC. In other words, a contravariant functor fromCtoDis a functor fromC op → D(equivalently, fromCtoD op ). Of course, any functorF:C → Dgives a functorF op :C op → D op . In fact, we have a functor (−) op : Cat→Cat.

Exercise 6LetCbe locally small. Show that there is a functor (the “Hom functor”)C(−,−) :C op × C →Set, assigning to the pair (A, B) of objects ofC, the setC(A, B).

l)

Given a partially ordered set (X,≤) we make a topological space by defin- ingU⊆Xto be open iff for allx, y∈X,x≤yandx∈Uimplyy∈U (Uis “upwards closed”, or an “upper set”). This is a topology, called the Alexandroff topologyw.r.t. the order≤.

4

If (X,≤) and (Y,≤) are two partially ordered sets, a functionf:X→ Ymonotone for the orderings if and only ifis fis continuous for the Alexandroff topologies. This gives an important functor: Pos→Top.

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.

m)

n)

“Abelianization”. Let Abgp be the category of abelian groups and ho- momorphisms. For every groupGthe subgroup [G, G] generated by all elements of formaba −1 b −1 is a normal subgroup.G/[G, G] is abelian, and for every group homomorphismφ:G→HwithHabelian, there is a ¯ unique homomorphismφ:G/[G, G]→Hsuch that the diagram

G v φ {{ vvv p ? ? ? ? ? ? ? ? v v v v v  G/[G, G] φ ¯ H

commutes. Show that this gives a functor: Grp→Abgp.

“Specialization ordering”. Given a topological spaceX, you can define a preorder≤ s onX sayas follows:x≤ s yif for all open setsU, ifx∈U theny∈U.≤ s is a partial order iffXis aT 0 -space. For many spaces,≤ s is trivial (in particular whenXisT 1 ) but in caseX is for example the Alexandroff topology on a poset (X,≤) as in l), then x≤ s yiffx≤y.

Exercise 8Iff:X→Ya continuous map of topological spaces thenis fis monotone w.r.t. the specialization orderings≤ s . This defines a functor Top→ Preord, 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 inRandx∈I. Morphisms (I , x)→(J, y) are differentiable functionsf:I→Jsuch thatf(x) =y. LetYbe the (multiplicative) monoidR, considered as a category. Show that the operation which sends an arrowf: (I , x)→(J, y) tof 0 (x), determines a functorX→Yfact of elementary Calculus does this rely? which basic . On

1.2 Some special objects and arrows

We call an arrowf:A→Bmono(or a monomorphism, or monomorphic) in a categoryC, if for any other objectCand for any pair of arrowsg, h:C→A, f g=f himpliesg=h.

5

In Set,fis mono ifff same is true for Grp, Theis an injective function. Grph, Rng, Preord, Pos,. . . We call an arrowf:A→Bepi(epimorphism, epimorphic) if for any pair g, h:B→C,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 inC op , and vice versa. In general, given a propertyP . . we can associate withof an object, arrow, diagram,.Pthe dual propertyP op : the object or arrow has propertyP op inCiff it hasPinC op . Theduality principle, a very important, albeit trivial, principle in category theory, says that any valid statement about categories, involving the proper- tiesP 1 , . . . , P n implies the “dualized” statement (where direction of arrows is reversed) with theP i replaced byP i op . 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,N→Zis an epimorphism. For, suppose Z f (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 Mon→Set does not preserve epis. An epif:A→Bis calledsplitif there isg:B→Asuch thatf g= id B (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:A→Bis anisomorphismif there isg:B→Asuch that f g= id B andgf= id A  call. Wegtheinverseoff(and vice versa, of course); it is unique if it exists. We also writeg=f −1 . 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 embeddingZ→Qis epi in CRng1.

6

Exercise 13

i)

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 Y→X Dually,in the category.Xisinitialif for allYthere is exactly one X→Y.

Exercise 15A full and faithful functor reflects the property of being a terminal (or initial) object.

Exercise 16IfXandX 0 are two terminal objects, they areisomorphic, that is there exists an isomorphism between them. Same for initial objects.

Exercise 17Let∼be a congruence on the categoryC, as in example g). Show: iffandgare arrowsX→Ywith inversesf −1 andg −1 respectively, thenf∼g ifff −1 ∼g −1 .

7

2

2.1

Natural

transformations

The Yoneda lemma

Anatural transformationbetween two functorsF, G:C → Dconsists of a family of morphisms (µ C :F C→GC) C∈C 0 indexed by the collection of objects ofC, satisfying the following requirement: for every morphismf:C→C 0 inC, the diagram F C µ C GC

F f

F C 0 µ C 0

Gf

GC 0

commutes inD say We(the diagram above is called the naturality square). µ= (µ C ) C∈C 0 :F⇒Gand we callµ C thecomponent atCof the natural transformationµ. Given natural transformationsµ:F⇒Gandν:G⇒Hwe have a natural transformationνµ= (ν C µ C ) C :F⇒H, and with this composition there is a categoryD C with 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 fromXtoYbyY X , for any setZthere is a bijection between functionsZ→Y X and functionsZ×X→Y (Set iscartesian closed chapter 7).: see

Proposition 2.1

For categoriesC,DandEthere is a bijection:

Cat(E × C,D)→ ∼ Cat(E,D C )

Proof. GivenF:E × C → Ddefine for every objectEofEthe functor F E :C → DbyF E (C) =F(E, C); forf:C→C 0 letF E (f) =F(id E , f) : F E (C) =F(E, C)→F(E, C 0 ) =F E (C 0 ) Giveng:E→E 0 inE, the family (F(g,id C ) :F E (C)→F E 0 (C)) C∈C 0 is a natural transformation:F E ⇒F E 0  we have a functor. SoF7→F (−) :E → D C . n a functorG:E C ˜ : → DE ×Con Conversely, give→ Dwe define a functorG ˜ ˜ objects byG(E, C) =G(E)(C), and on arrows byG(g, f) =G(g) C 0 G(E)(f) = G(E 0 )(f)G(g) C :

G(E)(C) =G ˜ (E, C) G(g) C G( ˜ E 0 , C) =G(E 0 )(C)

G(E)(f)

˜ G(E, C 0 )

G(g) C 0

8

G(E 0 )(f)

˜ G(E 0 , C 0 ) =G(E 0 )(C 0 )

˜ 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.

Cat(E,D C )

An important example of natural transformations arises from the functorsh C : C op →Set (see example i) in the preceding chapter); defined on objects by h C (C 0 ) =C(C 0 , C) and on arrowsf:C 00 →C 0 so thath C (f) is composition withf:C(C 0 , C)→ C(C 00 , C). Giveng:C 1 →C 2 there is a natural transformation

h g :h C 1 ⇒h C 2

whose components are composition withg.

Exercise 19Spell this out.

We have, in other words, a functor

h (−) :C →Set C op

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 id C ∈h C (C) for each object C, and id C is in no other seth D (E); thatYis full and faithful follows from the following

Proposition 2.2 (Yoneda lemma)For every objectFofSet C op and every objectCofC, there is a bijectionf C,F : Set C op (h C , F)→F(C). Moreover, this bijection isnaturalinCandFin the following sense: giveng:C 0 →CinC andµ:F⇒F 0 inSet C op , the diagram

commutes inSet.

Set C op (h C , F)

Set C op (g,µ)

f C,F

Set C op (h C 0 , F 0 ) f C 0 ,F 0

F(C)

µ C 0 F(g)=F 0 (g)µ C

F 0 (C 0 )

Proof. For every objectC 0 ofC, every elementfofh C (C 0 ) =C(C 0 , C) is equal to id C fwhich ish C (f)(id C ).

9