; TeX output 2004.06.14:1301Y[썍color push BlackG color popn׍color push Black color popsrc:197Cats.texDtqGcmr17CategoryBTheory(dsrc:198Cats.texXQ ff cmr12Prof./Dr.B.Pareigissrc:199Cats.texXQ cmr12SummerSemester2004njsrc:200Cats.texJune14,2004}A- cmcsc10Contents src:1Cats.tocInrtroSduction3 src:2Cats.toc1. FVoundationspV6H src:3Cats.toc1.1. Graphs6H src:4Cats.toc1.2. Monoidsza8H src:5Cats.toc1.3. Categoriesjb12H src:6Cats.toc1.4. Constructionsoncategories!h18` src:7Cats.toc1.4.1. SlicecategoriesI18` src:8Cats.toc1.4.2. SubScategoriesP20` src:9Cats.toc1.4.3. TheproSductofcategories20`src:10Cats.toc1.4.4. Thedualofacategory!,21`src:11Cats.toc1.4.5. Thefreecategorygeneratedbryagraphӻ21Hsrc:12Cats.toc1.5. FVunctorss\22Hsrc:13Cats.toc1.6. SpSecialtrypesoffunctors!24`src:14Cats.toc1.6.1. Underlyingfunctors0|24`src:15Cats.toc1.6.2. FVreefunctorsS25`src:16Cats.toc1.6.3. Prowersetfunctors;26`src:17Cats.toc1.6.4. HomfunctorsorMorfunctors26Hsrc:18Cats.toc1.7. Naturaltransformations#$27`src:19Cats.toc1.7.1. NaturaltransformationsbSetrweenfunctorsI27`src:20Cats.toc1.7.2. Diagramse$30`src:21Cats.toc1.7.3. Commrutativediagramsx31`src:22Cats.toc1.7.4. Graphhomomorphismsbrycommutativediagramss33`src:23Cats.toc1.7.5. AssoSciativitrybycommutativediagramsˢ33`src:24Cats.toc1.7.6. Naturaltransformations35 color push BlackG color pop*Y[썍color push Blacko cmr92G color popn썑`src:25Cats.toc1.7.7. Naturalisomorphisms& P38`src:26Cats.toc1.7.8. NaturaltransformationsbSetrweenfunctorsII*239`src:27Cats.toc1.7.9. Naturaltransformationsofgraphs`42`src:28Cats.toc1.7.10. ComrbiningnaturaltransformationsandfunctorsK43 src:29Cats.toc2. RepresenrtablefunctorsandtheYVonedaLemma/*45Hsrc:30Cats.toc2.1. Represenrtablefunctors*45Hsrc:31Cats.toc2.2. TVerminalandinitialobjects46Hsrc:32Cats.toc2.3. Theextensionprinciple'y47Hsrc:33Cats.toc2.4. IsomorphismsY48Hsrc:34Cats.toc2.5. Monomorphismsandepimorphisms50Hsrc:35Cats.toc2.6. SubSobjectsg(54Hsrc:36Cats.toc2.7. ProSductsq55Hsrc:37Cats.toc2.8. Equalizersk461Hsrc:38Cats.toc2.9. Univrersalelements?66Hsrc:39Cats.toc2.10. TheYVonedaLemma2'71Hsrc:40Cats.toc2.11. AlgebraicStructures0|74Hsrc:41Cats.toc2.12. Limitsy<79 src:42Cats.toc3. AdjoinrtfunctorsandmonadsL84Hsrc:43Cats.toc3.1. AdjoinrtfunctorsK84Hsrc:44Cats.toc3.2. MonadsorTVriplesBH86Hsrc:45Cats.toc3.3. FVactorizationsofamonadBt87Hsrc:46Cats.toc3.4. AlgebraicCategories5\89Hsrc:47Cats.toc3.5. MorefactsabSoutadjoinrtfunctors89 src:48Cats.tocReferences90 color push BlackG color popY[썍color push BlackяIn9troAduction3G color popn썒Introductioncolor push Black0.0.1.bN cmbx12Remarkй(History.). color popsrc:214Cats.tex{1945bCategories rstappSear\ocially"inS.EilenrbSergandS.MacLane'spapSer\GeneraltheoryofnaturalequivXalences",y(TVrans.AMS٨58,x1945,231-294).src:218Cats.tex{1950'sThemainapplicationswrereoriginallyinthe eldsofalgebraictopSologyV,AparticularlyhomologytheoryV,andabstractalgebra.src:222Cats.tex{1960'sGrothendiecrketal.JbSeganusingcategorytheorywithgreatsuccessinalgebraicgeometryV.src:225Cats.tex{1970'sLarwvereandothersbSeganapplyingcategoriestologic,-revrealingsomedeepandsurprisingconnections.src:228Cats.tex{!1980's!ApplicationsbSeganappearing!incomputerscience,o[linguistics,cognitivrescience,philosophryV,.T..src:231Cats.tex{T1990'sApplicationstotheoreticalphrysicsU{quantumgroups,[?algebraicquantum eldtheories,highercategorytheoryV.-ncolor push Black0.0.2.Remark(Whydowestudycategories?). color pop color push Black|(1) color pop8?%src:238Cats.texAbundance:CategoriespabSound%inW mathematicsW andinrelated eldssucrhascomputerscience.Categoriesareformed%e.g.8bry%color push Black(a), color pop=Ѭsrc:242Cats.texVVectorspaces,%color push BlackC(b), color pop=Ѭsrc:243Cats.texAbSeliangroups,%color push Black(c), color pop=Ѭsrc:244Cats.texgroups,%color push BlackC(d), color pop=Ѭsrc:245Cats.texsets,%color push Black(e), color pop=Ѭsrc:246Cats.texmonoids,%color push Black]R(f8), color pop=Ѭsrc:247Cats.texsemigroups,%color push Black(g), color pop=Ѭsrc:248Cats.textopSologicalspaces,%color push BlackC(h), color pop=Ѭsrc:249Cats.texBanacrhspaces,%color push Black(i), color pop=Ѭsrc:250Cats.texmanifolds,%color push Black3(j), color pop=Ѭsrc:251Cats.texorderedsets,%color push Black(k), color pop=Ѭsrc:252Cats.texgraphs,%color push Black(l), color pop=Ѭsrc:253Cats.tex(computer-)languages,%color push Black(m), color pop=Ѭsrc:254Cats.texautomata. color push Black|(2) color pop%src:257Cats.texInsighrtintosimilarconstructions:%color push Black(a), color pop=Ѭsrc:259Cats.texproSducts,%color push BlackC(b), color pop=Ѭsrc:260Cats.texfreeobjects,%color push Black(c), color pop=Ѭsrc:261Cats.texdirectsums,%color push BlackC(d), color pop=Ѭsrc:262Cats.texkrernelandcokernels,%color push Black(e), color pop=Ѭsrc:263Cats.texlimits,%color push Black]R(f8), color pop=Ѭsrc:264Cats.texassoSciatedgroupsandalgebras,sucrhashomologygroups,Grothendiecrkrings,=Ѭfundamenrtalgroups,assoSciativeenvelopSes,compacti cations,completions. color push Black|(3) color pop%src:269Cats.texCategorytheoryprorvesthatallinformationabSoutamathematicalobjectcanalso%bSezdrarwnfromtheknowledgeofallstructureypreservingmapsintothisobject.qVThe%knorwledgeofthemapsisequivXalenttotheknowledgeoftheinteriorstructureofan%object.8\FVunctionsareevrerywhere!" color push Black|(4) color pop%src:276Cats.texCategoryQtheoryRisalanguagethatallorwstoexpresssimilarpropSertiesandphe-%nomenadthatdoSccurindi erenrtmathematicalareas. {Ithelpstorecognizecertain%propSertiesandnotionstoharveageneraldescriptionandtobe\categorical".8E.g: color push BlackG color popY[썍color push Black4яIn9troAductionG color popn썍%color push Black꨹(a), color pop=Ѭsrc:282Cats.texeacrh nitedimensionalvectorspaceisisomorphictoitsdualandhencealsoto=ѬitsF/doubledual. TheF.secondcorrespSondenceisconsidered\natural"andthe rst=ѬisVnot.dCategorytheoryUcanexplainwhatthenotionof\natural"reallymeans.=ѬThiswrasinfactthestartingpSointofcategorytheoryV.%color push BlackC(b), color pop=Ѭsrc:288Cats.texTVopSologicalspacescanbede nedinmanrydi erentways,se.g.viaopSensets,via=ѬclosedNsets,mvianeighrbSorhoods,viaNconrvergent lters,mandviaNclosureopSerations.=ѬWhryfdothesegde nitionsdescribSe\essentiallythesame"objects? Category=Ѭtheoryprorvidesananswerviathenotionof@ cmti12cffoncrete35isomorphism.%color push Black(c), color pop=Ѭsrc:294Cats.texInitialstructures,\ nalstructures,\andfactorizationstructuresoSccurinmanry=Ѭdi erenrt@situations. ;Categorytheory@allowsonetoformulateandinvestigate=ѬsucrhconceptswithanappropriatedegreeofgeneralityV. color push Black|(5) color pop%src:301Cats.texCategoryp.theoryp/o ersmanryconvenientp.symbSolsthatp.allowonep.toquicklyp.pSerform%thenecessarycalculations:%color push Black(a), color pop=Ѭsrc:304Cats.texcommrutativediagrams,%color push BlackC(b), color pop=Ѭsrc:305Cats.texbraiddiagrams,%color push Black(c), color pop=Ѭsrc:306Cats.texcomputationswithsymrbSolicelements. color push Black|(6) color pop%src:309Cats.texTVranspSortationofproblemsfromoneareaofmathematics(viasuitablefunctors)to%anotherarea,owheresolutionsaresometimeseasierandthenatranspSortbacrktothe%original(area((sometimesviaadjoinrtfunctors).FVorexample,8algebraictopSologycan%bSe(described)asaninrvestigationof)topSologicalproblems(viasuitablefunctors)bry%algebraicmethoSds,sucrhasassociatedhomotoprygroups. color push Black|(7) color pop%src:318Cats.texDualitry:TheYconceptYofcategoryiswrell-balanced,uwhichallowsYaneconomicaland%usefulduality.Thrusiscategorytheorythe\trwoforthepriceofone"principleholds:%evreryconceptistwoconcepts,andeveryresultistworesults. color push Black|(8) color pop%src:324Cats.texCategory=theoryprorvidesthemeansto>distinguishbSetweengeneralproblems(\cate-%gorical" #problems "thatmaryoSccurinmanrydi erent "areasinsimilarform)andspSeci c%problems(thatacloselylinkredtotheveryspSecialareaandobjectoneisstudying).ncolor push Black0.0.3.Remark(Quotes). color pop color push Black|(1) color popbsrc:334Cats.tex(SteenroSd)`z\Categorytheory`yisgeneralizedabstractnon-%sense." color push Black|(2) color pop%src:337Cats.tex(Hoare)y\Categorytheoryzisquitethemostgeneralandabstractbrancrhofpure%mathematics.FThemcorollarymofahighdegreeofgeneralitryandabstractionisthatthe%theorygivresalmostnoassistanceinsolvingthemorespSeci cproblemswithinanryof%the3EsubSdisciplines3Ftowhicrhitapplies.ItisatoSolforthegeneralist,EloflittlebSene t%forthepractitioner." color push Black|(3) color pop%src:345Cats.tex(Barr-WVells)"`Categoriesoriginallyaroseinmathematicsoutoftheneedofafor-%malism to describSethepassagefromonetrypSeofmathematicalstructuretoanother.%Ak{categorykinthiskwraykrepresentsakkindofmathematics,andmarybSedescribedkas%cffategory35asmathematicffalworkspace.1src:352Cats.texAcategoryisalsoamathematicffaltVstructure.Assucrh,Ditisacommongeneralization%ofbSothorderedsetsandmonoids(thelatterareasimpletrypeofalgebraicstructure%thatincludetransitionsystemsasexamples), andquestionsmotivXatedbrythosetop-%icsoftenharveinterestinganswersforcategories.s5Thisiscategoryasmathematical%structure.1src:360Cats.texFinallyV,acategorycanbSeseenasastructurethatformalizesamathematician's%description of atrypSeofstructure.ThisistheroleofcategoryastheoryV.Formal%descriptionsinmathematicallogicaretraditionallygivrenasformallanguageswith color push BlackG color pop!uY[썍color push BlackяIn9troAduction5G color popn썑%〹rules0for0formingterms,Baxiomsandequations. Algebraistslongagoinrventeda0for-%malismbasedontuples,themethoSdofsignaturesandequations,todescribSealgebraic%structures.&Categorytheoryprorvidesanotherapproacrh:thexcffategoryyisathefforyand%functors35withthatcffategory35asdomainarffemodelsofthetheory."' color push Black|(4) color pop%src:372Cats.tex(StanfordEncyclopSediaofPhilosophry)\Categories,6functors,naturaltransforma-%tions,O)limits(Jand(IcolimitsappSearedalmostoutofnorwherein1945inEilenrbSerg&Mac%Lane's_papSer^enrtitled"GeneralTheoryofNaturalEquivXalences".-rWVesaid"almost",%bSecauseKwhenLonelooksatLtheir1942papSer"GroupExtensionsandHomology",^one%discorversgspSeci cfunctorsandnaturaltransformationsatwrork,limitedtogroups.%Infact,itwrasbasicallytheneedtoclarifyandabstractfromtheir1942resultsthat%EilenrbSerg2&MacLane1cameupwiththenotionsofcategorytheoryV.|}Thecentral%notionHforthem,)asIthetitleindicates,wrasthenotionofnaturalItransformation.In%ordertogivreageneralde nitionofthelatter,'!theyde nedthenotionoffunctor,%bSorrorwing+theterminology,fromCarnap,Zandinordertogive,ageneralde nition%of`3functor,}theyde nedthenotionof`2categoryV,}bSorrorwingthistimefromKanrtand%Aristotle." color push BlackG color pop6JY[썍color push Black6яIn9troAductionG color popn썍1.̞.Ffounda32tions1.1.Graphs.src:405Cats.texcolor push Black1.1.1.De nition. color popsrc:406Cats.texA(dirffected)35graphX(digraph)isamonad[BǕ"!", cmsy10G :=UR(g cmmi12V;E;n9)[Csrc:409Cats.texconsistingUofthesetV'ofverticffesݹ,stheUsetE ιofedgesorarrowsandthemaptotheendpSoinrtsq:EW! ViV:QFVorQeacrhedgefK2E2theverticesQAandB!withn9(fG)=(A;B)arecalledsourffce35andtarffgetordomainandcodomain꨹offG.8WVewritetheedgef2alsoasfQ:URAn!1B.src:416Cats.texLaterPonwrewillPpreferthenotationG|{Ycmr80йforthesetVforwhicrhFVVȹ(1)=S ;FV(2)=FV(3)=F%〹and#lFVVȹ(4)=Q,1andFE PtakrestheloSop#mon2andthearrorwfrom2to3bSothtothe%uppSerlooponFƹ;whatFE :doestotheothertrwoarrowsisforcedbythede nitionof%homomorphism.BecausetherearetrwoloSopsonF׹thereareactuallyfourpSossibilities%forFE 0onarrorws(whilekeepingFV Ap xed). color push Black|(3) color pop%src:628Cats.texIf8HV'isanrygraph8withanoSdenandaloSopuUR:nn!1n,\!then8thereisahomomorphism%fromanrygraphGĹtoH5>thattakeseverynoSdeofGĹtonandeveryarrowtou.This%construction0sgivres0ttwoother0thomomorphismsfromG梹toHNinExample1.5(2)bSesides%thefourmenrtionedthere.8(Therearestillothers.)zt1.2.Monoids.src:644Cats.texcolor push Black1.2.1.De nition. color popsrc:645Cats.texAmonoidisamonadMUR=(M;;e)consistingofW color push Black|(1) color pop%src:647Cats.texasetM@, color push Black|(2) color pop%src:648Cats.texamultiplicffationmapUR:MM6!M@,and color push Black|(3) color pop%src:650Cats.texaunitorneutrffalelemenrteUR2Msrc:652Cats.texsatisfyingthefollorwingaxiomsX color push BlackX- color pop%src:654Cats.tex8a;b;cUR2M6:J5a(bc)UR=(ab)c;ꦹ(assoSciativitry)I} color push BlackX- color pop%src:657Cats.tex8a;bUR2M6:ceaUR=a꨹and|beUR=b:꨹(leftandrighrtunitelement)src:661Cats.texHerewreusethenotationabUR:=(a;b).ztcolor push Black1.2.2.De nition.d color popsrc:665Cats.texLetMm=(M;;e)andM20<+=m(M@20;209;e20)bSe monoids.dFAhomomorphismof35monoidsFc:URMn!1M20isamapFc:M6!M@20Źsatisfyingthefollorwingaxioms color push BlackX- color pop%src:669Cats.tex8a;bUR2M6:F1(ab)UR=F(a)F(b); color push BlackG color pop dY[썍color push Black Monoids$9G color popn썍 color push BlackX- color pop%src:671Cats.texF1(e)UR=e209:wUsrc:673Cats.texAnuisomorphismtFc:URMn!1M20isahomomorphismtsucrhthatthereexistsanotherhomomor-phismC\.z  ҍF*:eM203Mo!MCwithB\.z  ҍF QF=id 0OMNandF1\.z  ҍFg˹=id 0OM0ӹ.UTwroBmonoidsarecalledisomorphicifthereexistsanisomorphismfromonemonoidtotheother. ZG23.04.04gcolor push Black1.2.3.De nition.(Z color popsrc:723Cats.texLetMbSeamonoid.AnM-grffaded0nmonoidisamonadUc=UR((Uidڹ);(i;j X);1)consistingof color push Black|(1) color pop%src:726Cats.texafamilyofmrutuallydisjointsets(UidjiUR2M@), color push Black|(2) color pop%src:728Cats.texafamilyof(multiplicffation)maps(i;j :URUiUj\ !*;Uij Xji;j%2M@),and color push Black|(3) color pop%src:730Cats.texanelemenrt1UR2Uesrc:732Cats.texsatisfyingthefollorwingaxioms(usingthenotationgfQ:=URi;j X(f;gn9)): color push BlackX- color pop%src:735Cats.tex8i;j;ko2URM+8fQ2Uid;gË2Ujf ;h2Ukx:)h(gfG)UR=(hgn9)fQ2URU(ijv)k(=Ui(jvk6)C; color push BlackX- color pop%src:739Cats.tex8i;j%2URM+8fQ2Uid;gË2Uj\:p1fQ=URf2and {g1=gn9:color push Black1.2.4.u!De nition.F color popsrc:746Cats.texLetMu andM20CZbSemonoids,U2beanu!M-gradedmonoid,andU120tjbSeanM209-gradedYmonoid.AYhomomorphismGofFgrffadedmonoidsYFCf:U(M;U1)+!>8(M209;U120J)Yconsistsof color push Black|(1) color pop%src:751Cats.texahomomorphismofmonoidsFM B:URMn!1M20and color push Black|(2) color pop%src:752Cats.texmapsFi,:URUiӷ!) U2@0뀍FX.!;cmmi6M(i)foralliUR2M][src:754Cats.texsucrhthatthefollowingconditionsaresatis ed color push BlackX- color pop%src:756Cats.tex8i;j%2URM;fQ2Uid;gË2Ujf :$Fij X(gfG)UR=Fjf (gn9)Fidڹ(fG) color push BlackX- color pop%src:758Cats.texFeqp(1)UR=12U2@0e0#7:src:762Cats.texItfollorwsfromthede nitionthatamonoidisnotallorwedtobSeempty:[itmustcontainanidenrtityqelement.P;ItpalsofollowsthatwecanextendthenotationofppSowersto0byde ningx20 ato|bSe}theidenrtity|elementofthemonoid.]]Thelawss2k#s2n 4չ=s2k6+nֹand(s2k)qwAn"L=s2k6n^thenholdforallnonnegativrekQŹandn.color push Black1.2.5.PExamples. color popsrc:770Cats.texOneexampleofPamonoidisthesetofnon-negativreintegerswithadditionastheopSeration.8Thisincludes0asaneutralelemenrt.src:774Cats.texThepKleffeneclosurepA2 0ofasetAisthesetofstrings(orlists)of nitelengthofelemenrtsof26and0rfQ=URf2and {gn91B =g: color push BlackG color pop ~Y[썍color push BlackCategories̄13G color popncolor push Black1.3.2.Remark. color popsrc:1093Cats.texAlternativede nition(Barr-Wells):Let,kߎ>xr0./In,agraphG.,|sapffathfromanoSdeAtoanoSdeBoflengthk5isasequence(f1;f2;:::ʜ;fk#;A;B)of(notnecessarilydistinct)arrorwsforwhicha color push Black|(1) color pop%src:1099Cats.texsource (fk#)UR=A, color push Black|(2) color pop%src:1100Cats.textarget$(fidڹ)UR=source#bd(fi1AV)foriUR=2;:::ʜ;kg,and color push Black|(3) color pop%src:1102Cats.textarget$(f1)UR=B.src:1104Cats.texByIconrvention,2\foreachnoSdeAJthereisauniquepathoflength0fromAtoAthatisdenoted(;A,A).Itiscalledtheempty35pffathatA.src:1108Cats.texObservrethatifyoudrawapathasfollows:uѕhfi?kJUR!URfi?kAacmr61dj!h+(fq2J*&!9szh5Tfq1JUR!Ísrc:1112Cats.texwith1thearrorwsgoingfromlefttoright,fk ùwillbSeontheleftandthesubscriptswillgodorwnfromlefttoright.8WVedoitthiswayforconsistencywithcompSosition.src:1116Cats.texFVoranryarrowfQ:URAn!1B,(fG;A;B)isapathoflength1.src:1119Cats.texDe nition:8ThesetofpathsoflengthkQŹinagraphGֹisdenotedGk#.src:1122Cats.texInhKparticular,^G2,whicrhwillhLbSeusedinthede nitionofcategoryV,^isthesetofpairsofarrorws(f;gn9;source" (g);target "(fG))tfforwhicrhthetargetofg⟹isthesourceoff. Thesearecalled cffomposable35pairs꨹ofarrorws:8h*gJUR!hfJUR!꨹.src:1129Cats.texWVe[@harvenowassignedtwomeaningstoG0 DandG1.Thiswillcausenocon ictasG1refersindi erenrtlyeithertothecollectionofarrorwsofG&ortothecollectionofpathsoflength1,whicrh|isessentiallythesamething.0\SimilarlyV,pweuseG0 RtorepresenteitherthecollectionofnoSdesofGorthecollectionofemptrypaths,NofwhichthereisoneforeacrhnoSde.{fQ=f.src:1168Cats.texThehsigni canceofthefactgthatthecompSositecisde nedonG2vlisthatgn9fgisde nedifandonly4Vif4WthesourceofgisthetargetoffG.ThismeansthatcompSositionisafunctionwhosedomainTisTanequationallyde nedsubsetofG1G1: theequationrequiresthatthesourceofQg3equalPthetargetoffG.,nItfollorwsfromthisandC-1thatinC-2,onesideoftheequationisde nedifandonlyiftheothersideisde ned.src:1177Cats.texInthecategorytheoryliterature,1A ȌisoftenwrittenjustA. color push BlackG color popMY[썍color push Black14F:oundationsG color popncolor push Black1.3.3.0Remark(TVerminology). color popsrc:1196Cats.texInmruch0of0thecategoricalliterature,H`morphism'ismorecommonFthanF`arrffow'.LWVewillnormallydenoteobjectsofcategoriesbrycapitallettersbutnoSdes(of'graphs(exceptwhenwrethinkofacategoryasagraph)brylowercase'letters. Arrowsarealwrayslowercase.src:1202Cats.texInH2:color push Black1.3.7.NProp`ositionm(ThegeneralassoSciativrelaw.).ZH color popsrc:1243Cats.texForlXanylYpffath(f1;f2;:::ʜ;fnP)lXinacffategoryCjand35anyinteffgerkRwith1URidenrtityhomomorphismid G}istheidentityfunctionforbSothnodesandarrorws.%Let~us~crheckthat~thecompSositeofgraphhomomorphismsisagraphhomomorphism%(idenrtities_areeasy).SuppSoseUR:G % !z_Hand_ Ë:Hr!Karegraphhomomorphisms,%andAsuppSosethatAu:mr![nAinG!.>Thenbryde nitionE-(u):VVȹ(m)r![V(n)Ain%H,andsobryde nition(x E-(E(u))UR: VVȹ(V(m))URn!1 V(V(n))inK5:(%src:1486Cats.texHence isagraphhomomorphism. color push Black(27) color pop%src:1488Cats.texAnexamplefromcomputerscience:%Afunctionalprogramminglanguagehas:%color push Black"FPL-1, color pop=Ѭsrc:1491Cats.texPrimitivredatatypSes,giveninthelanguage.%color push Black"FPL-2, color pop=Ѭsrc:1492Cats.texConstanrtsofeachtypSe.%color push Black"FPL-3, color pop=Ѭsrc:1493Cats.texOpSerations,whicrharefunctionsbetrweenthetrypes.%color push Black"FPL-4, color pop=Ѭsrc:1495Cats.texConstructors,Dwhicrh@canbSeappliedtodatatypSes@andoperationstoproduce=ѬderivreddatatypSesandoperationsofthelanguage.1src:1500Cats.texThe3languageconsistsofthesetof3allopSerationsandtrypesderivXablefromthe%primitivreJ0datatypSesandprimitiveopSerations. WyTheword`primitive'meansgiven%inthede nitionofthelanguageratherthanconstructedbryaconstructor.Some%authorsusethewrord`cffonstructor'fortheprimitiveopSerations.1src:1507Cats.texGivrenWRafunctionalprogrammingWQlanguageL,tthere'sanassoSciatedcategoryV,twhere%theobjectsarethedatatrypSesofL,Dandthearrowsarethecomputablefunctionsof%L3(\proScesses",F@\procedures",F?\programs").Thecompositionoftrwosuchprograms %Xh fJVU!(Yh PgI{!JB !Z.is givren byapplyinggɹtotheoutput offG,n sometimesalsowritten%g~f8=g9fG;gn9.The!idenrtityisthe!\donothing"program.Thisexampleisclosely%relatedtothenotionof\cartesianclosedcategory"tobSeconsideredlater.1src:1518Cats.texAsaconcreteexample,5PwrewillsuppSosewrehaveasimplesuchlanguagewith%threedatatrypSes,NA3T(naturalnumbSers),BOOLEAN(trueorfalse)andCHAR%〹(crharacters).8WVegiveadescriptionofitsopSerationsincategoricalstyle.%color push Black(i), color pop=Ѭsrc:1524Cats.texNA3T|shouldharveaconstant0:1! !(NA3T8andanopSerationsucc):NA3T=Ѭ?7!O@NA3Tk+#.%color push BlackC(ii), color pop=Ѭsrc:1527Cats.texThere should bSetrwoconstants ۺtrue;꨺falseI:;1!<BOOLEAN[pandan opSera-=Ѭtion:subjecttotheequations:true"?=URfalse&Qand:false%=URtruep.%color push Black(iii), color pop=Ѭsrc:1532Cats.texCHAR꨹shouldharveoneconstanrtcUR:1n!1CHAR??ѹforeachdesiredcharacterc.%color push BlackS(iv), color pop=Ѭsrc:1534Cats.texThereshouldbSetrwotypeconversionopSerationsord f:+CHAR0N2!CNA3TdԼand=ѬchrZ ::NA3T) + !=ԺCHARd?̹. TheseKaresubjectJtotheequationchrqord ۓ==ѬidGPCHARnH.(YVouYcanthinkZofchrasopSeratingmodulotheZnrumberYofcrharacters,=Ѭsothatitisde nedonallnaturalnrumbSers.)1src:1543Cats.texAnexampleprogramisthearrorw`next'de nedtobSethecompositechr2Osuccn%〺ord?:URCHAR-;/U'!>{CHARe;s.1src:1548Cats.texItWKcalculatesWLthenextcrharacterinorder. ~Thisarrorw`next'isanarrorwinthe%categoryvrepresenrtingthelanguage,zandsoisanyothercompSositevofasequenceof%opSerations.The\objectsof[thecategoryC5(L)ofthislanguagearethetrypSesNA3T,%〺BOOLEAN,CHARand1.4Observrethattrypingisanaturalpartofthesynrtaxin%thisapproacrh. color push BlackG color pop(6Y[썍color push Black18F:oundationsG color popn썑1src:1557Cats.texThe&arrorws&ofC5(L)consistofallprograms,4withtrwoprograms&bSeingidenti ed&if%theymrustbSethesamebecauseoftheequations.8FVorexample,thearrorwčchrqbsucc _ordX:URCHAR-;/U'!>{CHAR%src:1563Cats.texjustmenrtionedandthearrowÍdchr}succ _ord chr^ordX:URCHAR-;/U'!>{CHAR%src:1567Cats.texmrustbSethesamebecauseoftheequationin(iv).1src:1569Cats.texObservrethatNA3Thasconstantssucc!E!msucc(m:::msuccm0wheresucc"oSccurs%zeroormoretimes.1src:1574Cats.texCompSosition,inthecategory+iscompositionofprograms.aNotethatforcomposition%to"bSe!wrellde ned,ZiftwocompSosites!ofprimitiveopSerations!areequal,Zthentheir%compSositeswithanryotherprogrammustbSeequal.8FVorexample,wemusthave9ordR (chrXsucc _ordb)UR=ordX(chrsucc _ord chr^ordb)%src:1584Cats.texasarrorwsfromCHARtoNA3T.(Ǎ1.4.Constructionsoncategories.src:1605Cats.texsrc:1609Cats.texIfcyroudarefamiliarwithsomebrancrhofabstractalgebra(forexamplethetheoryofsemi-groups,Ogroups aorrings) `thenyrouknowthatgiven `twostructuresofa `giventypSe(e.g.,Otwosemigroups),gyrou4 canconstruct4a`dirffectaproduct'4 structure,de ningthe4opSerationscoor-dinatewise.nAlso,a-structure,maryhavesubstructures,whichare,subsetsclosedundertheopSerations,wY[썍color push BlackConstructionsToncategories19G color popn썹di erenrtarrowsofC5=XANvǍbY2BbY0C릟{fd*dά-!hHqA`$fvׁ Av Av Av A>A>UHfG20NVׁ NV NV NV +>+> iandbYBbYJC2{fd*dά-.nhH+7A: Bgׁ A A" A' A(B>A(B>UHGgn920Fׁ A < 7 5좟>5좟> -src:1672Cats.texIndeedhŹ:(B;fG)!P!)(C5;fG208)andhŹ:(B;gn9)!P!)(C5;gn920 color popsrc:1682Cats.texLet(PS; )beaposetandletC5(Pƹ)bethecorrespondingcategoryasin1.3.8(11).'rFVor_an^elemenrtxUR2Pƹ,theslice_categoryC5(Pƹ)=xisthecategorycorrespSondingtotheaset`ofelemenrtsgreaterthanorequaltox. Thedualnotionofcffoslice,&Oi.e. theacategoryAnCofoarrorwspf:kA!C forsomeCinC5,givrestheosetofelementsolessthanorequaltoagivrenelement.(܍color push Black1.4.3.m4Remark. color popsrc:1694Cats.texTheimpSortanceofslicecategoriesm5comesinpartwiththeirconnectionwithindexing.l"AnS-indexeffdBsetorgradedBsetisasetXAtogetherwithafunctionɄ:rgXc}u!S׹.l"Ifxނ2ރX,Ĺand;BW(x)=sthen;Awresay;Bxisoftypffes,OhandwrealsorefertoX,Źasatypffed}Jset.*Theterminology`S-indexeffdset'isthatusedbrycategorytheorists.&ManymathematicianswouldcastEthediscussionintermsFofthecollection(W21 (s)jsUR2S׹)EofsubsetsofX,whicrhwouldbSecalledafamily35ofsetsindexeffdbyS׹.color push Black1.4.4.Example.6 color popsrc:1722Cats.texThesetGUR=G0c<[9G1ofobjectsandarrorwsofagraphG3isanexampleofactrypSeddset, typeddbycthefunctiono:URGn!1f0;1gcthattakresanoSdeto0andanarrorwto1.NotethatthisdepSendsonthefactthatanodeisnotanarrorw:8G0andG1aredisjoinrt.color push Black1.4.5.QRemarkoO(Indexedfunctions).J4 color popsrc:1730Cats.texAfunctionfromPasetXԹtrypSedbyS(toPasetX20 typSedbrythesamesetS`thatpreservesthetyping(takesanelementoftypSestoanelementoftrypSe}s)|isexactlyanarrorwoftheslicecategorySet^=S׹.Sucrhafunctioniscalledanindexeffdfunction,$typffedfunction,orgradedfunction.*uIthasbSeenfruitfulforcategorytheoriststopursuethisanalogybrythinkingofobjectsofanryslicecategoryC5=XAasobjectsofCo;indexedbryA.(܍color push Black1.4.6.>Example.Ф color popsrc:1742Cats.texAgraphhomomorphism=fTǹ: G܁!JHcorrespSondsto>atryped=functionaccordingtotheconstructioninExample1.4.4.src:1746Cats.texHorwever,ИtherearetrypSedfunctionsbetrweengraphsthatarenotgraphhomomorphisms,Иforexamplethefunctionfromthegraphin1.1.3(1)src:1750Cats.texGtfd-`ά-[a/bݍʕ1ݍLF277trfd-`3ά %Y\cE(|  ͅ„fdά-n`a[ԍsrc:1760Cats.textothegraphin1.1.3(4)GݍV1ݍnٻ32fd!ά-紆0(|  ?„fdά- n`succsrc:1767Cats.texde nedbry/1UR7!1;27!n j;a7!0;b7!0;c7!succ:src:1770Cats.texThisisnotagraphhomomorphismbSecauseitdoesnotpreservresourceandtarget. color push BlackG color popSԠY[썍color push Black20F:oundationsG color popn썹1.4.2.Subffcategories.src:1777Cats.tex4"color push Black1.4.7.De nition. color popsrc:1778Cats.texAsubffcategoryD?ofacategoryCݹisacategoryforwhicrh:ύ color push BlackDS-1 color pop%src:1782Cats.texAllttheobjectsofDmaretobjectsofC'LandallthearrorwsofDmaretarrowsofC'L(inother%wrords,D0VURC0andD1URC1). color push BlackDS-2 color pop%src:1786Cats.texThegsourcefandtargetofanarrorwofD׼arethesameasitssourceandtargetinC5(in%otherwrords,thesourceandtargetmapsforD \aretherestrictionsofthoseforC5).&It%follorwsthatforanyobjectsAandBofDUV,Mor D p(A;B)URMorOC(A;B). color push BlackDS-3 color pop%src:1792Cats.texIfAisanobjectofD?thenitsidenrtityarrow1A ȌinCݹisinDUV. color push BlackDS-4 color pop%src:1795Cats.texIfVYfT: A&+!2B_andgzٹ:B1!C2inDUV,qFthenthecompSositegb4fX(inC5)isVZinDandis%thecompSositeinDUV.color push Black1.4.8.Examples. ^ color popsrc:1802Cats.texAsanexample,thecategoryFin4of nitesetsandallfunctionsbSetrweenthemuistasubScategoryofSetkX,handinturnSet̹isasubScategoryofthecategoryofsetsand{partialzfunctionsbSetrweensets{(see2.1.12and2.1.13).8XTheseexamplesillustratetrwophenomena:ύ color push Black(i) color pop%src:1808Cats.texIfAandBRare nitesets,thenMor.2@cmbx8Fin'͹(A;B)UR=MorOSet&(A;B).'Inotherwrords,every%arrorwofSet3bSetweenobjectsofFin¹isanarrowofFin. color push BlackU`(ii) color pop%src:1812Cats.texThe2categoryofsetsandthe3categoryofsetsandpartialfunctions,2Jontheotherhand,%harveexactlythesameobjects.1src:1816Cats.texThefcphenomenonfdof(i)doSesnotoSccurhere:therearegenerallymanrymorepartial%functionsbSetrweentwosetsthantherearefullfunctions.Ѝsrc:1820Cats.texExample(i)motivXatesthefollorwingde nition.color push Black1.4.9.De nition.ؒ color popsrc:1824Cats.texIfDisasubScategoryofCEandforevrerypairofobjectsA,B-˹ofDUV,Mor5D`(A;B)UR=MorOC(A;B),thenD?isafull35subffcategory꨹ofCݹ.4!src:1829Cats.texThruspFinDispafullsubScategoryofSetʵbutpSetʶisnotafullsubcategoryofthecategoryofsetsandpartialfunctions.src:1833Cats.texExample1.4.8(ii)alsomotivXatesa(lessuseful)de nition,asfollorws.color push Black1.4.10.[De nition. color popsrc:1837Cats.texIfDSis[asubScategoryofC1withthesameobjects,RthenDSisawidesubffcategory꨹ofC5.src:1841Cats.texThrusointhecaseoofawidesubScategoryV,=onlythearrowsaredi erentfromothoseofthelargercategoryV. Indc2.4.9ddwreprovideandcimprovementonthisconcept. Asanexample,>Set̅isdcawidesubScategoryofthecategoryPfnofsetsandpartialfunctions.4!color push Black1.4.11.IExample.E color popsrc:1849Cats.texAmongalltheIobjectsofthecategoryofsemigroupsarethemonoids,inandamong$allthesemigrouphomomorphismsbSetrween$two%monoidsarethosethatpreservetheidenrtityV.Thus Sthecategoryofmonoids TisasubScategoryofthecategoryofsemigroupsthatis neither widenorfull(see?? ).OAsitstands,bSeingasubScategoryrequirestheobjectsandarrorws*ofthesubScategorytobeidenrticalwith*someoftheobjectsandarrowsofthecategoryconrtaining^it.Thisrequires^anuncategoricalemphasisonwhatsomethingisinsteadofonthespSeci cationitsatis es. vsrc:1863Cats.tex0906.05.04a"1.4.3.The35prffoductofcategories.src:1868Cats.texcolor push Black1.4.12.uDe nition.D/ color popsrc:1869Cats.texIfCandtDJ˹arecategories,&theprffoductCiDJ˹isuthecategorywhoseobjectsareOallorderedpairs(C5;DS)withC,EanobjectofCܹandD5anOobjectofDUV,handinwhicrhan color push BlackG color popiY[썍color push BlackConstructionsToncategories21G color popn썹arrorw(f;gn9)X:(C5;DS)W!P<(Cܞ20;D20!ǹ)isapairofarrorwsfW:XCw!,Cܞ20inCandg :Dq!DS205inDUV.Thehidenrtitygof(C5;DS)is(1C;1D).EIfg(fG208;gn920Setn=isnotafunction, notevren\afunctionoftrwo=vXariables,Rsincetherearenoreasonableelemenrtsin(A;A).2ItismerelythearrowofaproSductcategoryandassucrhisanorderedpairoffunctions.src:1930Cats.texAsimilarremarkappliestoduals.T-InSetܥop¹,vaisanarrorwfromf0;1gtoA.T-Andthatisallitis.8Itisinparticularnotafunctionfromf0;1gtoA.src:1934Cats.texNevrertheless,\it1is2pSossibleinsomecasestoprorvethat1thedualofafamiliarcategoryisessenrtiallythesameassomeotherfamiliarcategoryV./OnesucrhcategoryisFin,&whicrhisequivXalenrttotheoppSositeofthecategoryof niteBooleanalgebras.src:1940Cats.texTheproSductofcategoriesisaformalwraytomakeconstructionsdepSendentonmorethanone_vXariable.\Themajor`usewremake`oftheconceptofdualisthatmanryofthede nitionswre}make}haveanothermeaning}whenappliedtothedualofacategorythatisoftenofindepSendenrtinterest..ThephrasedualconceptordualnotionisoftenusedtorefertoaconceptornotionappliedinthedualcategoryV.1.4.5.The35frffeecategorygeneratedbyagraph.src:1952Cats.texcolor push Black1.4.15.QDe nition.4 color popsrc:1953Cats.texFVoranryQgivenQgraphG thereisacategoryF1(G.)whoseobjectsarethenoSdesofGֹandwhosearrorwsarethepathsinG..8Compositionisde nedbrytheformulaepT(f1;f2;:::ʜ;fk#)(fk6+1;:::ʜ;fnP)UR=(f1;f2;:::ʜ;fnP):src:1958Cats.texThis@compSositionisassociativre,VwandforeachobjectA,Vw1A ˹isthe@emptypathfromAtoA.ThecategoryF1(G.)iscalledthefrffeeFcategoryFgeneratedbyFthegraphG..xItisalsocalledthepffath35categoryofG.. color push BlackG color pop~/Y[썍color push Black22F:oundationsG color popncolor push Black1.4.16.FExamples. color popsrc:1966Cats.tex{ThefreecategorygeneratedbrythegraphwithonenoSdeandnoarrowsisthecategorywithoneobjectandonlytheidenrtityarrow,whichistheemptypath.src:1970Cats.tex{ThefreecategorygeneratedbrythegraphwithonenoSdeandonelooponthenodeisthefree5monoidwithonegenerator4(Kleeneclosureofaone-letteralphabSet);[thisisisomorphicwiththenonnegativreintegerswith+asopSeration.src:1976Cats.tex{ThefreecategorygeneratedbrythegraphinExample1.1.3(4)hasthefollowingarrowss2 color push Black|(a) color pop%src:1980Cats.texAnarrorw11V:UR1n!11. color push BlackU`(b) color pop%src:1981Cats.texFVor]eacrh\nonnegativeinteger\kg,(Jthearrorwsucc2k)G:n&!+ݹn2d. Thisisthepath%(succR;succP;:::ʜ;sucsucc)(kvoSccurrencesofsucc).=Thisincludesk]=H?0whicrhgives%1nP. color push Black(c) color pop%src:1986Cats.texFVor.eacrh.nonnegativeinteger.kg,?thearrow.succ2k!Ʋ0C:1B!n3*.9Herek0_=0givres.0:1%' !7R_n=w.8CompSositionobeystherulesucc2k!T4succE2m#=URsucc2k6+m,5r:Tsrc:1994Cats.texIt`isusefultoregardthefreecategory`generatedbryanygraphasanalogoustotheKleeneclosureZ(freemonoid)generatedbryaset(asin1.2.5). ThepathsinthefreecategorycorrespSondtothestringsintheKleeneclosure.Thedi erenceisthatyroucanconcatenateanrygksymbSolsgltogethertogetastring,butarrorwscanbSestrungtogetheronlyheadtotail,thrustakingintoaccountthetyping.In??Hwegiveaprecisetechnicalmeaningtothewrord`free'.1.5.Functors.src:2007Cats.texsrc:2011Cats.texA&functor&FW۹fromacategoryCtoacategoryD| isa&graphhomomorphismwhicrhpreservesidenrtities`and`compSosition.0Itplays`thesame`roleasmonoidhomomorphismsformonoidsand;monotonemapsforpSosets:itpreservresthe;structurethatacategoryhas.FVunctorshaveanotherk8signi cance,[horwever:9sinceonek7sortofthingacategorycanbSeisamathematicalwrorkspace(seeIntroSduction),PmanyofthemostusefulfunctorsusedbymathematiciansaretransformationsfromonetrypSeofmathematicstoanother.Lessobrvious,ZbutpSerhapsmoreimpSortanrtisthefactthatmanrycategoriesthataremathematicallyinrterestingappSearascategorieswhoseobjectsareanaturalclassoffunctorsinrtothecategoryofsets.src:2025Cats.texA8ofunctor8isastructure-preservingmapbSetrween8categories,Kinthesamewray8thatahomo-morphismDisastructure-preservingDmapbSetrweenDgraphsormonoids. E#Hereistheformalde nition.Scolor push Black1.5.1./hDe nition.# color popsrc:2031Cats.texLetC}=X(Ob(C5);Mor5(C);();(1))/hand/iD=(Ob(DUV);Mor5(D);();(1))/hbSecategories.8LetFconsistof color push Black|(1) color pop%src:2035Cats.texamapFc:UROb(C5)URn!1Ob$n(DUV)anda color push Black|(2) color pop%src:2036Cats.texafamilyofmapseD7(Mor5C(A;B)UR3fQ7!F1(fG)2MorODڲ(F(A);F(B))jA;BX2UROb(C5)):%Fiscalledacffovariant35functorif%color push Black +, color pop=Ѭsrc:2041Cats.tex8AUR2Ob(C5):bBF1(1A)UR=1F((A)X;%color push Black +, color pop=Ѭsrc:2043Cats.tex8A;B;C12UROb(C5);8fQ2URMorOC(A;B);gË2URMorOC(B;Cܞ)UR:eǮF1(gn9fG)UR=F(gn9)F(fG):Tsrc:2050Cats.texAnequivXalenrtde nitionis:color push Black1.5.2.~De nition.K color popsrc:2053Cats.texA~functor~F:QCk!pD?isapairoffunctionsF0 :QC0  +:!|D0 >andF1 :C1!nD1forwhicrh color push BlackG color pop̠Y[썍color push BlackN.F:unctors223G color popn썍 color push Black[F-1 color pop%src:2056Cats.texIffQ:URAn!1BinCݹ,thenF1(fG):F0(A)n!1F0(B)inDUV. color push Black[F-2 color pop%src:2058Cats.texFVoranryobjectAofCݹ,F1(1A)UR=1Fq0*(A). color push Black[F-3 color pop%src:2060Cats.texIf;g f0:isde ned:inCp,thenF1(gn9)F1(fG);isde ned:inD=andF1(g f)UR=F1(gn9)F1(fG).esrc:2064Cats.texByRF-1,aSfunctorisinparticularahomomorphismofgraphs.FVollorwingthepracticeforgraphhomomorphisms,theznotationyiscustomarilyorverloaded: IifzAisanobject,F1(A)UR=F0(A)zisanzobject,andziff—isanarrorw,F1(fG)UR=F1(f)ziszanarrorw.ThenotationfortheconstituenrtsF0V:URC0 .!5D0andF1:C1 .!5D1isnotstandard,andwrewilluseitonlyforemphasis.color push Black1.5.3.Example.Q color popsrc:2075Cats.texItiseasytoseethatamonoidhomomorphismf:eMez!lNOdeterminesafunctorfromC5(M)toC5(Nİ)asde nedin1.3.8(1).Onobjects,gahomomorphismfYmrusttakrethesingleobjectofC5(M)tothesingleobjectofC5(Nİ),b/andF-1istriviallyvreri edsinceballbarrorwsinC5(M)harvebthesamedomainandcoSdomainandsimilarlyforC5(Nİ). ThenF-2XandF-3saryXpreciselythatfisamonoidhomomorphism.ConrverselyV,t>everyXfunctorisdeterminedinthiswraybyamonoidhomomorphism.color push Black1.5.4.tExample. color popsrc:2088Cats.texLetusseewhatafunctorfromC5(S ; )ttoC(T; O)mrustbSewhen(S ; )and(T; O)>4arepSosets>3asin1.3.8(1).3ItissuggestivretowritebSothrelations Qùand 肹as`'andthepSosetssimplyasS¹andTƹ./Thenthereisexactlyonearrorwfromxtoy>#inS(orinTƹ)ifandonlyifxURyn9;otherwisetherearenoarrorwsfromxtoy.src:2097Cats.texLetgfrn:*pSF!!CT bSethefunctor.~F-1gsarysifthereisanarrorwfromxtoyn9,*thenthereisanarrorwfromfG(x)tof(yn9);inotherwrords,ifxURyXthenf(x)f(yn9).src:2102Cats.texThrusfisamonotonemap."F-2andF-3impSosenoadditionalconditionsonfbSecausetheyeacrh|assert}theequality}oftwo}spSeci edarrows}bSetweentwo}spSeci edobjectsandinapSosetascategoryallarrorwsbSetweentwoobjectsareequal.color push Black1.5.5.2RemarkG+(TheG,categoryofcategories). color popsrc:2110Cats.texThe1category2Catchas2allsmallcategoriesas&objects%andallfunctorsbSetrween&suchcategoriesas%arrows.YThecompSositeof%functorsistheirycompSositeasygraphhomomorphisms:UifFx:GCg!\D]andGֹ:GD!3Eù,thenG F:GC!MEɉsatis esG5F1(Cܞ)=G.(F(Cܞ))foranryobjectCdofCi,andG55F1(fG)=G.(F(fG))foranryarrowfaofC5.$Thus(GxF1)i=XGiiFi}foriX=0;1.$WVenotethatthecompSositioncircleisusuallyomittedwhencompSosingfunctorssothatwrewriteG.F1(Cܞ)UR=G(F1(Cܞ)).ItissometimesconrvenienttorefertoacategoryCAT"Cwhicrhhasallsmallcategoriesandordinarylargecategoriesasobjects,andfunctorsbSetrweenthem.{SincetryingtohaveCAT%abSeanobjectofitselfwrouldraisedelicatefoundationalquestions,xwredonotattempthereaformalde nitionofCAT .color push Black1.5.6.y Example. color popsrc:2129Cats.texIfy C,AisacategoryV,thefunctorP1V:URCuœC"!wfC,Awhicrhtakesy anobject(C5;DS)toCHandanarrorw(f;gn9);:<(C5;DS)!Z(Cܞ20;DS20!ǹ)tof^iscalledthe rst[prffojection.Thereisananalogousseffcond35projectionfunctorP2takinganobjectorarrorwtoitssecondcoSordinate.color push Black1.5.7.Example. color popsrc:2138Cats.texLet2+2꨹bSethecategorythatcanbepicturedasˍ5f0URn!111 0#=!j2src:2141Cats.texwithnoothernonidenrtityarrows,andthecategory3theonethatloSokslike)y=ʕ0=LF1tגfd-`ά-K `ݍ2R0սd@بDŵ@بDŵR`R0ŵŵ src:2148Cats.texDe ne]the]functorFJY:H2 + 22!L3]ɹtotakre0to0,z1and1'to1,zand2to2.BThenwhatitdoSesonarrorwsisforced. color push BlackG color pop-Y[썍color push Black24F:oundationsG color popnsrc:2152Cats.texNote|=thattheimageofFNincludesall|>of3exceptthecompSositearrorwfrom0Mf!ʹ2.ThisexampleshorwsthattheimageofafunctorneednotbSeasubcategoryofthecodomaincategoryV.Ѝcolor push Black1.5.8.Example.~R color popsrc:2160Cats.texTheinclusionmapofasubScategoryisafunctor.ThecategoricalpSoinrtofzviewdoSesnotrequirethattheobject{andarrorwsofasubcategoryactuallybeobjectsandarrorwsofthebiggercategoryV,TonlythattherebSeaninjectivreidenti cationofobjectsormorphismsIofonecategorywiththeobjectsorHmorphismsoftheother.&kFVorexample,\SetZisa)zsubScategory){ofRel$%:thefunctortakresevery)zsettoitselfandeacrhfunctionf@:@Ss!LT@toitsgraphf(s;t)jtUR=fG(s)g,whicrhisindeedarelationfromStoTƹ.src:2171Cats.texThis\papproacrh\ohasthestrangeresultthattrwodi erent\pcategoriescaneacrhbSeregardedassubScategoriesoftheotherone.src:2175Cats.texObservrethatthecategoryRi?kofringsisnotasubScategoryofthecategoryAb4ofabSeliangroup,althougheacrhringisalsoanabSeliangroup(undertheaddition)andevreryhomomorphismofringsisalsoahomomorphismofabSeliangroups.TherecanbSetrwononisomorphicrings,thatharvethesameadditiveabSeliangroup.э1.6.Sp`ecialtypesoffunctors.src:2190Cats.texݍ1.6.1.Underlying35functors.src:2193Cats.texcolor push Black1.6.1.Example.* color popsrc:2194Cats.texFVorgettingsomeofthestructureinacategoryofstructuresandstructure-preservingfunctionsgivresafunctorcalledanunderlying functororforffgetfulfunctor.LThefunctor_Ugm:&Mon'[L)t!;bSemZwhicrhembSedsthecategoryofmonoids`intothecategoryofsemigroupsA̹:CatYs#!/WSetwhicrh>takeacategory>toitssetofobjectsandsetofarrorwsrespSectivelyV,andafunctortotheappropriatesetmap. $src:2245Cats.tex;7.5.04 color push BlackG color pop¯Y[썍color push Black8SpAecialTt9ypesoffunctors25G color popncolor push Black1.6.4.Example.,/ color popsrc:2248Cats.texIn1.4.1, nwredescribSedthenotionofaslice categoryC5=XAbasedonacategoryC!and+anobjectA.AnobjectisanarrorwB_ox!=eA+andanarrowfromf h:iB_ox!=fAtog2:C!nAkRiskQanarrorwhUR:BX !_7CGforwhicrhkRgh=fG.mThereisafunctorkQU6:C5=XAn!1Cthattakresthe+tobject+sf :ÜB^x-!;AtoBzandthearrorwhfromB^x-!;AtoC:!}cAtohÜ:B^x.!;Cܞ.CThisis%hcalled%gtheunderlyingi5functoroftheslicffe.In%hthecasethatCl=RSet5,4anobjectT[t!-S?ofSet=SBfor ksomesetSisanS׹-indexedobject,\andthee ectoftheunderlyingfunctoristoforgettheindexing.1.6.2.Frffee35functors.src:2264Cats.texcolor push Black1.6.5.Example. color popsrc:2265Cats.texThefreemonoidfunctorfromSettothecategoryofmonoidstakresasetAtothefreemonoidFƹ(A),whicrhistheKleeneclosureA2withconcatenationasopSeration(see1.2.5),ÅandafunctionfQ:URAn!1BTùtothefunctionFƹ(fG)UR=f2 ]U:Fƹ(A)n!1F(B)de nedin1.2.16. TVoseethatthefreemonoidfunctorisindeedafunctoritisnecessarytoshorwthatifUqfS: A$!/BwandUpgyM:B!ʻCܞ,p#thenFƹ(ga\fG):F(A)$!/F(Cܞ)UpisUqthesameasFƹ(gn9)\F(fG),whicrh*jis*iimmediatefromthede nition,:Zandthatitpreservresidentity*iarrows,:[whichis*jalsoimmediate.TheKleeneclosureisitselfafunctorfromSettoSet,$"takingAtoA2اandf`tofG2. It`Sis`TthecompSositeUFoftheunderlyingfunctorU6:URMon!#i!3'SetIpandthefreefunctorF:URSet!+fMonF,butofcourseitcanbSede nedindependenrtlyofU+andFƹ.color push Black1.6.6.Example.7 color popsrc:2284Cats.texThefreecategoryonagraphisalsotheobjectpartofafunctorFNy:Grf!Cat(=.k'WhatitdoSestoagraphisdescribedin1.4.15.k'Suppose'W:GJd!iHýisagraphhomomorphism.TheTobjectsSofthefreecategoryonagrapharethenoSdesofthegraph,dsoitisreasonabletode neFƹ(')0V=UR'0.XNorwsuppSose(fnP;fn1;:::ʜ;f1)isapath,athatis,anarrorw,inFƹ(G.).|Sincefunctorspreservre~domainandcoSdomain,Twrecande neFƹ(')1(fnP;fn1;:::ʜ;f1)to"GbSe('1(fnP);'1(fn1̹);:::ʜ;'1(f1))"Gandknorwwegeta"HpathinFƹ(H).߽ThatF preservescompSositionofpathsisalsoclear.color push Black1.6.7.Remark*(The)map-liftingprop`erty). color popsrc:2300Cats.texThefreecategoryfunctorFEڹ:Grf^!.tCatandalsootherfreefunctors,Dsucrhasthefreemonoidfunctor1.6.5,DharveamapliftingpropSertrycalleditsuniversalVmappingprffopertywhicrhwillbSeseenasthede ningpropSertryoffreeness.WVewilldescribSethepropertryforfreecategoriessinceweuseitlater.src:2307Cats.texLet=G)bSe=agraphandFƹ(G.)bSethefreecategorygeneratedbryG).QThereisagraphhomomor-phismHwithHthespSecialnamen9G :URG% !z_U@(Fƹ(G.))whicrhHincludesagraphG5inrtoU@(Fƹ(G.)),htheunderlyingp&graphp%ofthefreecategoryFƹ(G.). Themap(n9G)00*istheidenrtityV,sincethep&objectsofyFƹ(G.)zarethenoSdesofG..cTFVoranarrorwfxofG.,Ѯ(n9G)1(fG)yisthepath(fG)oflengthone.Thisz$isz%aninclusionarrorwinthegeneralizedcategoricalsense,sincef#and(fG)arereallytrwodistinctenrtities.color push Black1.6.8.Prop`osition.> color popsrc:2320Cats.texLffetKGbeagraphKandCacffategory.5ThenforeveryKgraphhomomorphism*hUR:G q!?U@(C5),ٔtherffe,is+auniquefunctorV| %u cmex10b*h :URFƹ(G.)!Cv`with,theprffopertythat,U@(Vb*hÊ)n9G =URh.Ocolor push BlackPrffoof. color pop#Rsrc:2326Cats.texIf()istheemptrypathatanobjecta,wresetVXbb*h c ()UR=1aϹ.FVoranobjectaofFƹ(G.)(thatUis,noSdeofG.),de neVb*h 2(a)UR=h(a).8Andforapath(anP;an1;:::ʜ;a1),Vb*hڹis`maph':YsVobb*ohv (anP;an1;:::ʜ;a1)UR=(h(an);h(an1̹);:::ʜ;h(a1)):src:2333Cats.texAsnotedin1.1.1,thereisauniqueemptrypathforeacrhnoSdeaofG..#MCompSosingtheemptrypathatawithanrypathpfromatobgivespagain,andsimilarlyontheotherside.S( msam10 color push BlackG color popȠY[썍color push Black26F:oundationsG color popn썹1.6.3.Powerset35functors.src:2339Cats.texsrc:2343Cats.texAnry.{setSRhasapSowersetPS׹,TthesetofallsubsetsofS.&Therearethreedi erenrtfunctorsFforwhicrhF0S̹takesasettoitspSorwerset;theydi eronwhattheydotoarrorws.OneofthemisfundamenrtalintopSostheory;thatonewesingleouttobSecalledtheporwersetfunctor.src:2350Cats.texIfJfQ:URAn!1BPisIanrysetfunctionandCisasubsetofB,5op"v$/!3SetJ?takresasetS#tothepSowersetPS׹,andasetfunctionfQ:URAn!1BS(thatis,anarrorwfromBStoAinSetŸop߹)totheinrverseimagefunctionfG21͹:URPBX !_7PA.src:2370Cats.texAlthoughwrewillcontinuetousethenotationfG21 {,H8itisdenotedfG2 'inmruchofthecategoricalliterature.CTVoCcrheckthatCP@6isafunctorrequiresshorwingthat118OAI>=1P+AandthatifgZ:B!nCܞ,then(gfG)21ι=URf21O#gn921 ʵ,wherebSothcompositionstakreplaceinSetӋ.color push Black1.6.10.De nition. color popsrc:2379Cats.texAfunctorF:rC52op "_!DQ$isalsocalledacffontravariantBfunctorfromCtoDUV.Ӎsrc:2383Cats.texAs-illustratedintheprecedingde nition,>thefunctor-isoftende nedintermsofarrorwsofC,ratheryUthanyTofarrorwsofC52op R.OppSositecategoriesaremostcommonlyusedtoprorvideawray oftalkingabSoutconrtravXariant functors asordinary(corvariant) functors:theoppSositecategoryinthissituationisapurelyformalconstructionofnoindepSendenrtinterest.src:2392Cats.tex0913.05.04color push Black1.6.11.J#Remark. color popsrc:2394Cats.texTheothertrwoJ#functorswhicrhJ$takeJ#asettoitspSorwersetJ#arebothcorvXariant.ThedirffectJorKexistentialimagefunctorùtakresf:gAg!B&ʹtothefunctionf ':gPAg!PB,wheref(A0)UR=ffG(x)jx2A0g,thesetofvXaluesoff2onA0.src:2400Cats.texTheGuniversalEimagefunctortakresA0KtothosevXaluesHoff0FwhichcomeonlyfromA0:formallyV,ittakresfQ:URAn!1Btof!1ƹ:PAn!PB,withݍ8nf!t(A0)UR=fyË2BjfG(x)=yXimplies,;Cx2A0g=fyË2BjfG 1 {(fyn9g)A0g:Ӎ1.6.4.Hom35functorsorMorfunctors.src:2416Cats.texsrc:2419Cats.texLetkCbSeacategorywithanobjectCHiandanarrorwfy :1 AJ!{B.IfʹinduceskasetfunctionMor5(A;fG):MorƳ(A;B)A!:Mor,p(A;Cܞ)de nedbrycompSosingbyfontheleft:uforanyg2Mor5(A;B),nthatGis,forFanryg椹:xjAxk! cB,Mor:k(A;fG)(gn9)xk=fg,nwhicrhGdoSesFindeedgofromAto Cܞ.5SimilarlyV,for!anryobjectDS,fQ:URBX !_7Cinducesaset!functionMor(f;DS):MorO(C5;DS)!n߹Mor&(B;DS)`(notetherevrersal)byrequiring`thatMor(f;DS)(h)UR=hsrffor`h2MorO(C5;DS).color push Black1.6.12.>De nition. color popsrc:2430Cats.texFVoragivrenobjectC۹thecffovariant8XMor8WfunctorMor&;(C5;-)^:^C +!jSet,cisde nedasfollorws:m color push BlackrHF-1 color pop%src:2433Cats.texMor5(C5;-)(A)UR:=MorO(C;A)foreacrhobjectAofC5; color push BlackrHF-2 color pop%src:2435Cats.texMor5(C5;-)(fG)UR:=MorO(C;fG):MorO(C;A)n!1Mor).(C;B)forfQ:URAn!1B.src:2440Cats.texTheBfollorwingBcalculationsshowthatBMorx(C5;-)isaBfunctor.AFVoranobjectA,XMor(C5;1A):Mor5(C5;A)դ/!ԹMor,(C;A)rtakresanqarrowf:գCB!rAto1A "FDbf=գfG;=WhenceMoro(C5;1A)= color push BlackG color pop Y[썍color push BlackNaturalTtransformations27G color popn썹1MorX(C;A)%V.8NorwsuppSosefQ:URAn!1BandgË:BX !_7D.8Thenforanryarrowko:URC1K{!A,/|WG_<Mortr(C5;gn9)Mor(C;fG)G(kg)N=URMorO(C5;gn9)GMor(C;fG)(kg)GN߹=URMorO(C5;gn9)(fkg)N=URg(fkg)N=UR(gfG)kN߹=URMorO(C5;gfG)(kg):/src:2455Cats.texThereisadistinctcorvXariantMorfunctorMor(C5;-)foreacrhobjectCܞ.0Inthisexpression,׫Cis+a*parameterforafamilyoffunctors.XhTheargumenrtofeacrhofthesefunctorsisindicatedbryC8thedash.Ananalogousde nitionincalculuswouldbSetode nethefunctionwhichraisesa&realnrumbSer&tothenth&porwer&asfG(-)=(-)2n N(here&nisthe¶meter).Onedi erenceintheMorfunctorcaseisthattheMorfunctorisorverloadedandsohastobSede nedontrwodi erenrtkindsofthings:8objectsandarrows.Zcolor push Black1.6.13.+De nition. color popsrc:2467Cats.texFVoragivren+objectDS,{3thecffontravariantYmorYfunctor+Mora(-;D)v:vC52op!@Set,ݹis|de nedforeacrhobjectAby|Mor(-;DS)(A):=Mor7(A;DS)|and|foreacrharrowfr:|sA|t!tB,dMora(-;DS)(fG)|t:=Morp(f;DS):Morp(B;DS)!tMor,Hq(A;DS).A Thrus if gꬹ:|tBy1!yD,Mor5(f;DS)(gn9)UR=gfG.Z color push Black1.6.14.De nition. color popsrc:2476Cats.texThetwo-variable35Morfunctore˹toMor(C;DS),andapair(f;gn9)ofarrorwswithfQ:URC1K{!AandgË:URBX !_7D>6toYMor(f;gn9)UR:MorO(A;B)n!1Mor).(C5;DS)s2src:2482Cats.texwhereforhUR:An!1B,Mor(f;gn9)(h)UR=ghfsrc:2484Cats.texwhicrhisindeedanarrowfromCFtoDS.Zsrc:2487Cats.texIn:this:casewrealsousetheproSductofcategoriesasaformalconstructiontoexpressfunctorsof}more}thanoneargumenrt.3FVromthecategoricalpSoinrtofview,afunctoralwrayshas}oneargumenrt,vwhichxasinthexpresenrtcasemightxwellbSeanxobjectinaproductxcategory(anorderedpair).1.7.Naturaltransformations.src:2495Cats.texsrc:2499Cats.texInrordertorseeoneoftheaimsofthissectionwre rstintroSducenaturalrtransformationoffunctorsandstudytheirmostelemenrtarypropSerties.1.7.1.Naturffal35transformationsbetweenfunctorsI.src:2504Cats.texZcolor push Black1.7.1.D^De nition.- color popsrc:2508Cats.texLetDS;E:C;!DbeD^trwocovXariantD_functors.FADGnaturffaltransformation h:URDk!E ӹisXgivrenbyaXfamilyofmorphisms A 6ofDindexedbytheXobjectsofC suchthat:s2 color push Black?NTF-1 color pop%src:2513Cats.tex A 36:URDS(A)n!1E(A)foreacrhnodeAofC5. color push Black?NTF-2 color pop%src:2515Cats.texFVoranrymorphismfQ:URAn!1BinC5,thediagram@](1)ūDS(A)E(A).:2fd Tά-ߍL ANDS(B)E(B)˞32fd 0ά-o B|Ǡ@feӯKǠ?냀DS(fG)uǠ@feKǠ?냀ZE(fG)p̍%src:2525Cats.texcommrutes. color push BlackG color pop ;Y[썍color push Black28F:oundationsG color popncolor push Black1.7.2.r+De nition.E2 color popsrc:2530Cats.texLetDS, E&AandFbefunctorsr*fromC%`toDǁ, and O:;D!E&Band I:E!PF_natural>transformations.ThecompSosite W: R:DQ(!Fisde nedcompSonenrtwise:( T )A 36=UR A  A.x]color push Black1.7.3.p1Prop`osition.D1 color popsrc:2538Cats.texThecffompositeoftwonaturffaltransformationsisalsoanaturaltrans-formation.color push BlackPrffoof. color pop#Rsrc:2543Cats.texThediagramthathastobSeshorwncommutativeistheouterrectangleofD(2)MDS(A)ݝDE(A)+:2fd Tά-ߍ̿ A 'Fƹ(A)n:2fd Ѝά-dZ ADS(B)@E(B)*[32fd 0ά-ȯ B NFƹ(B)+32fd pά- - BǠ@feP۟Ǡ?냀S%DS(fG)Ǡ@feI۟Ǡ?냀pE(fG)Ǡ@feB۟Ǡ?냀[Fƹ(fG)&src:2558Cats.texforYeacrharrowfZù:A,P!?BinC5.TherectanglecommutesbSecausethetwosquaresdo;thesquarescommruteasaconsequenceofthenaturalityof 7and O.x^color push Black1.7.4.qExample.`f color popsrc:2565Cats.texExamplesfornaturalptransformations{likreforfunctors{arebuiltinrtothezde nitionofycategories.VLetf:RAl,!BbSezamorphisminacategoryC5.UIn1.6.12wreharvealreadystudiedcorvXariantfunctorsMor Cd(A;-);Mor5C(B;-)UR:C"!wfSet(`I.src:2571Cats.texThemorphismf2inducesafamilyofmapsef΄Mor|Cr@(f;Cܞ)UR:MorOC(B;Cܞ)3gË7!gfQ2MorOC(A;Cܞ)src:2574Cats.texwhicrhisanaturaltransformationbyExercise??.color push Black1.7.5.YDe nition. color popsrc:2595Cats.texAnaturalXtransformation Zc:FF &!HG:C !ZkDiscalledYanaturffalisomorphism꨹ifthereisanaturaltransformation :URGn!1Fnwhicrhisaninverseto .color push Black1.7.6.De nition. color popsrc:2602Cats.texAfunctorF:URC"!wfD?isaneffquivalence35ofcffategories꨹ifthereare:s2 color push Black6E-1 color pop%src:2605Cats.texAfunctorGUR:D3!C5. color push Black6E-2 color pop%src:2606Cats.texA,family-F(uC :ztCWp!G(Fƹ(Cܞ))jCW2Ob%(C5))-GofisomorphismsofC|indexedbrythe%objectsofCrwiththepropSertrythatforevreryarrowf:C7!s^Cܞ20iofC5,G(Fƹ(fG))=L%uC0 |fu18OC \|. color push Black6E-3 color pop%src:2610Cats.texAfamilyvD :NDPjh!gFƹ(G(DS))ofisomorphismsofD9indexedbrytheobjectsofDUV,%withthepropSertrythatforeveryarrowgË:URDk!DS20 oofDUV,Fƹ(G(gn9))=vDthisform,Stheyarethestatemenrts>thatuisanaturaltransformationfromid jCtoGFandHthatHvisanaturaltransformationfromidDtoFG.S~SinceeacrhcompSonentofHuandeacrhcompSonentofvXisanisomorphism,uandvarenaturalisomorphisms.IC color push BlackG color pop5)Y[썍color push Black30F:oundationsG color popn썹1.7.2.Diagrffams.src:2735Cats.texsrc:2738Cats.texCommrutativendiagramsnarethecategorist'swraynofexpressingequations.1Naturaltransfor-mationsžaremapsſbSetrweenžfunctors;3Ionewayžtothinkofthemisasadeformationofoneconstruction(construedasafunctor)inrtoanother.src:2744Cats.texWVebSeginwithdiagramsinagraphanddiscusscommrutativitylater.Acolor push Black1.7.10.De nition. V color popsrc:2748Cats.texLetITandGbSegraphs.[AdiagrffamIjinGofshapffeITisahomomorphismD:I"!2NG[׹ofgraphs.iI,iscalledtheshapffegraphofthediagramDUV.iWVeharvethusgivenanewnametoaconceptwhicrhwasalreadyde ned(notuncommoninmathematics).Adiagrffam꨹isagraphhomomorphismfromadi erenrtpSointofview.Bcolor push Black1.7.11.1Example. color popsrc:2758Cats.texArt rst0glance,De nition1.7.10mayseem0tohavelittleto0dowithwhatareinformallycalleddiagrams,forexampleLwAKB632fd*ά-]f!u96CzRhՐL8`@{,!U@{,!UR[{@ $>RHZǠ*FfeDǠ?`fbY#AbY=~Bi{fd*ά-!IhH=8D`kfôׁ @ô @#ô @-ô @0 4>@0 4>RHBbǠ*FfeBBǠ? Fgxsrc:2991Cats.texcommrute(infactifandonlyifeitheronedoSes).color push Black1.7.16.qDe nition. color popsrc:2995Cats.texLetpCibSeacategoryV.'xAcmorphismfQ:URXF``!YRiscalledanisomorphism,ifthereexistsamorphismgË:URY M!`X+withgfQ=1X 1andfgË=1YP.src:3000Cats.texgis!yuniquely!zdeterminedbryfixandisitselfanisomorphism.TWVeusethenotationfG21W:=gn9.Thruswehave(fG21 {)21ι=URgn921 =fG.color push Black1.7.17.GExample./ color popsrc:3005Cats.texAnGarrorwf<$:$A !BisanGisomorphismwithinrverseGgb]:%B*!AifandonlyiftYY6fd*ά-*8fwAKBrَrَ6rfd* ά Dgmsrc:3013Cats.texcommrutes.ThetMreasonforthisisthatforthisdiagramtocommute,thetwopaths()and(gn9;fG)fromAtoAmrustcompSosetothesamevXalueinthediagram,FwhicrhmeansthatgfQ=UR1A.8AsimilarobservXationshorwsthatfgXmrustbSe1BN>.{src:3021Cats.tex0920.05.04 color push BlackG color pop!v'Y[썍color push BlackNaturalTtransformations33G color popn썹1.7.4.Grffaph35homomorphismsbycommutativediagrams.src:3024Cats.tex]color push Black1.7.18.DRemark. color popsrc:3028Cats.texThede nitionDofgraphhomomorphismin1.1.2canbSeexpressedbryacommrutativemdiagram..Letl'ҹ=('0;'1)bSemagraphhomomorphismfromG̛toH4..FVoranryarrorwDup:mpu!`ninGGr,1.1.2requiresthat'1(u):'0(m)pu!`'0(n)DinH.,Thissarysthat'0(source (u))UR=source#bd('1(u)),]and|Ja|KsimilarstatemenrtabSouttargets.Inotherwrords,]thesediagramsmrustcommute:Ax(4):3{*G1:3H1s:2fd0ά-t{'133{*G033H0s32fd0ά-gۍ'0۱Ǡ@feǠ?Ս\OQsourceԱǠ@feǠ?Սcsource:3!ZG1:3NH10i:2fd0ά-t{7t'133!ZG033NH00i32fd0ά-gۍ7t'0&Ǡ@fe'Ǡ? otargetUǠ@feUǠ? Ztargetsrc:3053Cats.texInthesetrwodiagramsthetrwoarrowslabSeled`source'areofcoursedi erentfunctions;9oneisthesourcefunctionforGֹandtheotherforH.8Asimilarremarkistrueof`target'.src:3058Cats.texThisٲpSoinrtٳofviewprovidesٳapictorialproSofthatthecompSositeoftrwographٲhomomorphismsisagraphhomomorphism(see1.3.8(26)). .If'%:%G!Hand %:HC]!Kcaregraphhomomorphisms,thene8toseethat T'isae9graphhomomorphismrequirescrheckinge8thattheoutsiderectanglebSelorwcommutes,andsimilarlywithtargetinplaceofsource:D(5):3G1:3osH1L:2fd0ά-t{Xv'133G033osH0L32fd0ά-gۍXv'0qǠ@fe磟Ǡ?Ս(sourceqǠ@feࣟǠ?Ս!source:3osH1:3FK1s:2fdά-dg} 133osH033FK0s32fdά- g} 0qǠ@fe٣Ǡ?Ս#source~src:3077Cats.texThe߼outside߽rectanglecommrutesbSecausethetrwosquares߼commute.Thiscan߽bSecheckedbry*|tracing(mentallyorwitha ngerorpSointer)thepathsfromG1 ꀹtoK0tovrerifythatsource"  1'1V=UR 0source'1\tbSecauseptherighrtsquarecommutes,Handthat 0source" '1V= 0˾ '0source'bSecausey:they;leftsquarecommrutes.Theveri cationy:proScessjustdescribSediscalled`chasingthediagrffam'.*Ofcourse,onecanvrerifytherequiredfactbywritingtheequationsdorwn,;butthoseequationshidethesourceandtargetinformationgivrenindiagramandRthrusRprovideapSossibilityofRwritinganimpSossiblecompositeRdorwn.o6FVormanyRpSeople,thepdiagramismruchpeasiertorememrbSerthanptheequations.4However,KdiagramsaremorethanU4informalU3aids;ytheyareformally-de nedmathematicalobjectsjustlikreautomataandcategories.>The rproSofin1.4.1thatthe qcompositionofarrorwsinaslicegivesanotherarrowinthecategorycanbSerepresenrtedbyasimilardiagram:BmKCmK㌂Cܞ20·D:2fd[ά-μ:OhmKmK^eCܞ200:2fd@ά-λBh20.A냀þfT?`@T?`@T?`@]@]RbŸǠ@feǠ?!HtfG20!ZTfG200V?`V?`V?`TT Ksrc:3104Cats.texTheseexamplesareinstancesofpastingcommrutativediagramstogethertogetbiggerones.1.7.5.Assoffciativity35bycommutativediagrams.src:3109Cats.texsrc:3112Cats.texThe4fact5thatthemrultiplicationinamonoidorsemigroupisassoSciativrecanbSeexpressedastheassertionthatacertaindiagraminSet3commrutes.src:3116Cats.texLetSbSeasemigroup.8De nethefollorwingfunctions:ĥcolor push Black(1) color pop%src:3118Cats.texmrult(:URS]S)!!wSsatis esmrult&(x;yn9)=xy. color push BlackG color pop"ΠY[썍color push Black34F:oundationsG color popn썍color push Black(2) color pop%src:3120Cats.texS]mrultx:URSSS)!!wSSsatis es(Smrult~&)(x;yn9;z)UR=(x;yz).color push Black(3) color pop%src:3122Cats.texmrult|S):URS]SS)!!wSSsatis es(mrult|S׹)(x;yn9;z)UR=(xy;z).4:src:3125Cats.texThatthefollorwingdiagramcommutesisexactlytheassoSciativelaw.F8덍ԠS]SSԠ8S]Sğ:2fd-6ά-MS]mrultFS]S`S432fdC ά- ;mrultUǠ@feňğǠ?.*mrult%S#GǠ@fe#zğǠ?*(-Dmrultsrc:3134Cats.texNormallyV,tassoSciativitryW$isexpressedW%bytheequationx(yn9z)UR=(xy)zforW$allx,ty,zinW%theW$semi-group.XThe{commrutativezdiagramexpressesthissamefactwithouttheuseofvXariables.XOfcourse,Twre/ did/usevXariablesinde ningthefunctionsinrvolved,Tbutwe/remedythatde ciencyinZChapter6[whenwregivea[categoricalde nitionofproSducts.4qAnotheradvXantage[ofusingdiagrams]toexpressequationsisthatdiagrams^shorwthesourceandtargetofthefunctionsinrvolved.ThisisnotparticularlycompSellingherebutinothersituationsthetrwo-dimensionalpictureofthecompSositionsinrvolvedmakesitmucheasiertofollowthediscussion.-color push Black1.7.19.RemarkNo(FVunctorsbrycommutativediagrams). color popsrc:3149Cats.texWVeexpressthede nitionoffunctorusingHcommrutativediagrams.LetGC7}andDٞbSecategorieswithsetsofobjectsC0DLandD0,setsof[arrorws\C1_andD1,ksetsofcompSosablepairsofarrorwsC2`andD2,jandidenrtity[morphismsgivrenbyidJ:C0 D ^K! C1 \andidK:D0 D ^K! D1,zrespSectivelyV.OAfunctorF͹:C7Q}!;D@consistsoffunctionsF06:uC0 O!ʼnD0,F1:C1 O!ŊD1ܹalongwiththeuniquelydeterminedfunctionF26:C2!nD2(thinkofF2((f;gn9))UR=(F1(fG);F1(gn9)))sucrhthat|֍S sWC2ijC1oƤFproj} T1بDbΨDlĨDvDağWağW {(D12`*Ffe)d`? SF1O@ijD2rY *FfeटY ?pi$F2{D1%d`*Ffe%䟽`? S*JdF1O@ij "C1oƤ$proj$2T2b@l@v@@_W@_WRijD2H بDΨDĨDDağağ H @@@@_@_R@Rproj;`T1@projT2hvsrc:3169Cats.texcommrutes.8Inaddition,thefollowingdiagramsmustcommute:EHk:3KC1:3zC0Zd:2fd`ά-μ:]8dom33J~D133ywD0[$32fdά- ]8domQLbǠ@feQǠ?붳?mF1EbǠ@fexǠ?붳nfF0:3:3C1d:2fd`άμ:ScoSd3333pD1d32fdz`ά FcoSd>bǠ@feqǠ?붳$F1:3WC2:3PC1t:2fd`ά-t{عcomp33D233D1T432fdά-gۍعcomprǠ@feटǠ?붳"F2rǠ@fe٤Ǡ?붳$F1:3OC0:3~C1^S:2fd`ά-μ:gid33NGD033}@D1_D32fdά- gidUǠ@feUHǠ?붳C62F0Ǡ@feAǠ?붳4F1src:3192Cats.texwheretheseconddiagramrepresenrtsF1(f gn9)I-=F1(fG)F1(gn9)andthethirddiagramrepresenrtsF1(1A)UR=1Fq0*(A). color push BlackG color pop#ڠY[썍color push BlackNaturalTtransformations35G color popncolor push Black1.7.20.Remarkv_(Diagramsasfunctors).m color popsrc:3196Cats.texInmruchofthecategoricalliterature,adiagramin=acategory=CisafunctorD:En!YCwhere=EPisacategoryV. 2tBecauseofPropSosition1.6.8,a.graph/homomorphisminrtoacategoryextendsuniquelytoafunctorbasedonthefreeNcategoryNgeneratedbrythegraph,mcsothatdiagramsinoursensegeneratediagramsinthefunctorialsense.Ontheotherhand,Xanryfunctorisagraphhomomorphismontheunderlyinggraphdofditsdomain(althoughnotconrversely!),tsothatdeverydiagramdinthesenseoffunctorisadiagraminthesenseofgraphhomomorphism. =G21.05.04ۍ1.7.6.Naturffal35transformations.src:3212Cats.texsrc:3215Cats.texWVe&sarw'thatdiagramsinacategoryaregraphhomomorphismstothecategoryfromadi erenrtIpSointJofview.NowJweintroSduceJathirdwraytoloSokJatgraphhomomorphismstoacategoryV,namelyasmoSdels.8Togivreanexample,weneedade nition.Lcolor push Black1.7.21.De nition. color popsrc:3222Cats.texAunary35opfferation꨹onasetSisafunctionuUR:S)!!wS׹.Lsrc:3226Cats.texThisde nitionisbryanalogywiththeconceptofbinaryopSerationonaset.\AsetwithaunaryopSerationisa(vrerysimple)algebraicstructure,ˈwhicrhwecallau-structure.TIftheset:is9SandtheopSerationisf":$S1K!ʫS׹, ^wresaythat9(S ;fG)isau-structure, ^meaning(S ;fG)denotesau-structurewhoseunderlyingsetisS׹,]andwhoseunaryopSerationisfG.4ThisusespSositional9notationinmruch9thesamewray9as9proceduresinmanrycomputerlanguages:4the rstȱenrtryinȲtheexpression`(S ;fG)'isthenameoftheunderlyingsetoftheu-structureandthesecondenrtryisthenameofitsopSeration.src:3238Cats.texAhomomorphismQofu-structuresshouldbSeafunctionwhicrhpreservesthestructure.nThereisreally=\onlyone=[de nitionthatisreasonableforthisidea::if(S ;u)and(T;vn9)areu-structures,f:SKeC!'TisYahomomorphismWofWu-structurffesZiffG(u(s))=vn9(f(s))ZforYalls2S׹.Thrusthisdiagrammrustcommute:?̍ ϩS VT4:2fdά-dWPfϩSVT432fdά- WPfmǠ@feӠDǠ?Ս=ufǠ@feDǠ?ՍKv9src:3251Cats.texIt0is/notdiculttoshorwthatthecompSositeoftrwohomomorphisms0ofu-structuresisanotherone,qandthattheidenrtitymapisahomomorphism,sothatu-structuresandhomomorphismsformacategoryV.src:3256Cats.texWVe=norwtrwo|?moSdelsofthesamegraphinacategoryV.Anaturffal϶transformation :w#Dʱ|(6) ˏGDSa lEaO{:2fdЍά-ōm a*%RDSb*uxEb޹+32fd?pά-  b|Ǡ@feӯKǠ?^DSsuǠ@feKǠ?ZEsٌ%src:3351Cats.texcommrutes.src:3355Cats.texThecommrutativityofthediagraminNT-2isreferredtoastheemnaturalitryconditionon .TheXarrorwW aforanWobjectaisthecompSonenrtofthenaturaltransformation ata.Notetransformations.ThecompSosite W: R:DQ(!Fisde nedcompSonenrtwise:( T )aUR= Oa a.color push Black1.7.28.Prop`osition. color popsrc:3374Cats.texThe,cffompositeof,twonaturaltransformationsisalso,anaturaltrans-formation. color push BlackG color pop%}Y[썍color push BlackNaturalTtransformations37G color popn썍color push BlackPrffoof. color pop#Rsrc:3379Cats.texThediagramthathastobSeshorwncommutativeistheouterrectangleofF(7) 0DSa Ea :2fdЍά-ō a Fa۟:2fdά-d Oa*DSb*EbZ32fd?pά- ͥ b**$Fb32fdά-  ObǠ@feP۟Ǡ?sDSsǠ@feI۟Ǡ?קEsǠ@feB۟Ǡ?[Fssrc:3393Cats.texforeacrharrows#:"a!ebinG..TherectanglecommutesbSecausethetwosquaresdo;zthesquarescommruteasaconsequenceofthenaturalityof 7and O.R`src:3399Cats.texItgAisinrterestingthatgBcategoristsbSeganusingmodesofreasoninglikregBthatintheprecedingproSof:because9objectsofcategoriesgenerallylacrkedelements;^nowoneappreciates9themfortheirorwnsakebSecausetheyallowelement-free(andthusvXariable-free)arguments.src:3405Cats.texIt7isevreneasiertoshowthatthere8isanidentitynaturaltransformationbSetweenanymoSdelD?andritself,de nedsbry1DaV=1D6toE.src:3429Cats.texConditionNT-2in1.7.26coincidesinthiscasewiththediagramin1.7.21:m7thenaturalitryconditionkislthesameasthede nitionofhomomorphismofu-structures.$Itfollorwsthatthecategoryofu-structuresandhomomorphismsisessenrtiallyMo`dX(U1;Set).color push Black1.7.31.Example. color popsrc:3438Cats.texAhomomorphismofgraphsisanaturaltransformationbSetrweenmodelsofthegraphx<<lfd-@ά-kڭsourceUBkaUgnlrfd-@ά- )\ztarget}Jsrc:3447Cats.texThe7trwo6graphsindiagram(4)arethetrwo6necessaryinstances(oneforthesourceandtheotherforthetarget)ofthediagram(6).InasimilarwrayV,thediagram(7),usedtoshorwthatthecompSositeoftrwonaturaltransformationsisanaturaltransformation,reducesinthiscasetothecommrutativityofdiagram(5):VspSeci callyV,theonlypSossibilities(otherthanthoseinwhicrhsisanidenrtityarrow)foraandbindiagram(7)areaUR=aandbUR=n,givingtrwoGediagramsGdshapSedlikrediagram(7),h oneforsUR=source&(thatisGediagram(5))andtheotherforsUR=target"v.color push Black1.7.32.Example. color popsrc:3464Cats.texAmoSdelofthegraphd(8)ڞ02*upURn!11ݍsrc:3468Cats.texin?an>arbitrarycategoryC~tisessenrtiallythesameasanarrorwinC~s(see5.2.23bSelorw).ڤAnaturaltransformationfromthemoSdelrepresenrtedbythearrowf:HAHa!Btotheone color push BlackG color pop&Y[썍color push Black38F:oundationsG color popn썹represenrtedECbyg:ICq!OW!$Dѹmakingacommrutativediagram:>|(9) ˏGDSa lEaO{:2fdЍά-ōm a*%RDSb*uxEb޹+32fd?pά-  b|Ǡ@feӯKǠ?^DSsuǠ@feKǠ?ZEsYsrc:3482Cats.texTheecompSonenrtfat0ishandthecompSonenrtat1iskg. ThecategoryofmoSdelsinCUiscalledthearrffow35categoryofC5;itisoftendenotedC2ܞ)!v+.;color push Black1.7.33.UGExample.6s color popsrc:3488Cats.texLetG vbSetheUHgraphwithtrwonoSdesUGandnoarrorws,oandC}anycategoryV.ThenMo`dX(G.;C5)isisomorphictoCFCܞ.<1.7.7.Naturffal35isomorphisms.src:3496Cats.texcolor push Black1.7.34.WDe nition.o color popsrc:3497Cats.texAWbnaturaltransformationW Q:Fd ~!@G:Gxz!U>DiscalledWanaturffalisomorphismTifthereisSanaturaltransformation :]EG]Fv!FwhicrhisaninverseSto inthecategoryMo`dX(G.;DUV).8Naturalisomorphismsareoftencallednaturffal35equivalences.<color push Black1.7.35.MOExample.z color popsrc:3505Cats.texTheMParrorw(h;kg)UR:fQ! 0ginMOthearrowMPcategoryofacategoryC,lasshownin(9),#isanaturalisomorphismifandonlyifhandk~arebSothisomorphismsinC5.KThisisaspSecialcaseofanimportanrtfactaboutnaturalisomorphisms,whicrhwenowstate.color push Black1.7.36.Theorem.Q color popsrc:3514Cats.texSuppffose F*:edG!bDwand!Gec:G!Dwarffe!modelsofG|NinDwand x:edFfk!Gisanaturffaltransformationofmodels.TRThen isanaturalisomorphismifandonlyiffor35effachnodeaofG., aUR:Fƹ(a)!G(a)35isanisomorphismofDUV.<color push BlackPrffoof. color pop#Rsrc:3522Cats.texSuppSoseD ҹhasanCinrverseD G:3GM!|F< inMoSd#(G.;DUV). GThenforCanrynoSdea,*byde nitionQh1.7.27thede nitionoftheidenrtityQinaturalQhtransformation,kandthede nitionofinrverse, a OaUR=( 7 )a=id G?a=id G(a)s2src:3528Cats.texand Oa aUR=( T )a=id F/Ca=id F.:(a)src:3531Cats.texwhicrhmeansthatthearrow Oaistheinverseofthearrow a,`sothat aisanisomorphisminD?asrequired.src:3535Cats.texConrverselyV,suppSose 4that 3foreacrhnoSdeaofGa, aO:PFƹ(a)!,-G(a)is 4anisomorphismofDUV.The4compSonenrt4 oftheinverse4 ]atanoSdeaisde nedbryletting Oa@=A( a)21 \|.Thisistheonly#~pSossiblede nition,1butitmrustbeshorwntobenatural.cLetf:aϛ!b#~beanarrorwofthedomainofFnandG.8ThenwrehaveeʍzzFf( a)21W=UR( b)21$( b)Ff( a)21W=UR( b)21$Gf( a)( a)21W=UR( b)21$Gf: ;src:3549Cats.texwhicrhsaysthat isnatural.8Thesecondequalityusesthenaturalityof .L9UTsrc:3554Cats.tex0927.05.04@color push Black1.7.37.{Remark. color popsrc:3557Cats.texIn1.7.32,wresaidthatamoSdelinanarbitrarycategoryC7ofthegraph(8)isP`essenrtiallythesame'asanarrowinCι.jThisiscommonterminologyandusuallyrefersimplicitlytoanequivXalenceofcategories.8WVespSellitoutinthiscase.src:3563Cats.texLet6us6sarythatforacategoryC,IC520GisthecategorywhoseobjectsarethearrorwsofC andforwhicrhanarrowfromf2togXisapair(h;kg)makingdiagram(9)commute. color push BlackG color pop'Y[썍color push BlackNaturalTtransformations39G color popnsrc:3568Cats.texALmoSdelLMѹoftheLgraph(8)inacategoryC"spSeci estheobjectsM@(0)andM@(1)andthearrorw SM@(u).M(u)hasdomain RM(0)and RcoSdomainM(1).But RthedomainandcoSdomainofanarrorwinacategoryareuniquelydeterminedbrythearrorw.+SothattheonlynecessaryinformationiswhicrharrowM@(u)is.src:3575Cats.texNorwwecande neafunctorFP(:bC25!$!$C520n.OnobjectsittakesM_߹toM@(u).Theremarksin%thepreceding$paragraphshorwthatthismaponobjectsisbijectivre.VIfM@(u)=f$andN@(u)UR=gn9,anoarrorwfromMStoNinC25!1andanarrorwfromfotog inC520ݹarethesamething{pappair(h;kg)makingdiagram(9)commrute.SowepsayFisthepidentityonarrows.ItisstraighrtforwardtoseethatFnisactuallyanisomorphismofcategories.?\1.7.8.Naturffal35transformationsbetweenfunctorsII.src:3586Cats.texcolor push Black1.7.38.kWDe nition.A color popsrc:3590Cats.texAk6functorisamongotherkXthingsagraphhomomorphism,soanaturffaltrffansformation >between =twofunctors,is-anaturaltransformationofthecorrespSondinggraphhomomorphisms.8ThefollorwingpropSositionisanimmediateconsequenceof1.7.28.?]color push Black1.7.39.MProp`osition.2H color popsrc:3598Cats.texIfC@andD arffecategories,WthefunctorsfromC@toD formacategorywith35naturffaltransformationsasarrows.?\src:3603Cats.texWVe denotethiscategorybryFunc f(C5;DUV).OthercommonnotationsforitareD2C ¹and[C5;D].TVennenrt^[1986]]providesan]expSositionoftheuseoffunctorcategoriesforprogramminglanguagevsemanrtics. KOfcourse,DthegraphwhomomorphismsfromCtoDUV,Dwhichdonotnecessarily[preservrethe[compSositionofarrowsinC,x$alsoforma[categoryMo`d(C5;DUV)(see1.7.29),ofwhicrhοFunc+1(C5;DUV)οisafullsubScategoryV.=AwnaturaltransformationfromonefunctortooanotheroisaspSecialcaseofanaturaltransformationfromonegraphhomomorphismtoanother,@so/wthe/videaswrehave/wpresentedconcerning/wnaturaltransformationsbSetrweengraphhomomorphismsMapplyNtonaturaltransformationsbSetrweenMfunctorsaswrell./Inparticular,Theorems1.7.28and1.7.36aretrueofnaturaltransformationsoffunctors.src:3620Cats.texIfcCisnotcasmallcategory(see1.3.4),~thenFunc&(C5;DUV)marynotbSelocallycsmall(see1.3.4).InfactfunctorswillbSelarge,too,sotheycannotbeelemenrts(objects)ofaclassofobjects.This(is(aratheresotericquestionthatwillnotconcernusinthesenotessincewrewillharvenooSccasiontoformfunctorcategoriesofthatsort.src:3628Cats.texWVeamotivXatedtheconceptofnaturaltransformationbryconsideringamoSdelsofgraphs,andmostsoftthediscussionintherestofthissectionconcernsthatpSoinrtofview.BHistoricallyV,theconcept rstaroseforfunctorsandnotfromthepSoinrtofviewofmodels.color push Black1.7.40.Examples.l color popsrc:3635Cats.texWVeharvealreadydescribSedsomeexamplesofnaturaltransformations,assummedupinthefollorwingpropSositions.nIn1.6.7,wede nedthegraphhomomorphismn9G :URG% !z_U@(Fƹ(G.))whicrhincludesagraphGBinrtoU@(Fƹ(G.)),theunderlyinggraphofthefreecategoryFƹ(G.).color push Black1.7.41.] Prop`osition. color popsrc:3644Cats.texThe family ofarrffowsn9Gg8formanaturffaltransformation fromthe iden-tity35functoronGrftoUF,wherffeUtistheunderlyinggraphfunctorfromCatjtoGrf.?]src:3650Cats.texTheproSofisleftasanexercise.src:3652Cats.texFVurtherBexamplesofnaturaltransformationsaregivrenbyCactionsonsets.WVebSeginwithade nition.color push Black1.7.42.ؙDe nition.+ color popsrc:3656Cats.texLetؚM}bSeamonoidwithidenrtityؙ1andletSpbSeaset.2Anaction"ofMonSisafunction h:URMS)!!wSforwhicrhs2 color push BlackfsA-1 color pop%src:3660Cats.tex (1;s)UR=s꨹forallsUR2S׹. color push BlackG color pop(ޠY[썍color push Black40F:oundationsG color popn썍 color push BlackfsA-2 color pop%src:3661Cats.tex (mn;s)UR= (m; (n;s))forallm;nUR2M+ands2S׹.VRsrc:3664Cats.texItѩisѪcustomaryinmathematicstowritemsfor (m;s);E+thentheprecedingrequiremenrtsbSecomeVQ color push Black"A'-1 color pop%src:3667Cats.tex1sUR=s꨹forallsUR2S׹. color push Black"A'-2 color pop%src:3668Cats.tex(mn)sUR=m(ns)forallm;nUR2M+ands2S׹.src:3671Cats.texWhenactionsarewrittenthiswrayV,[S߹isalsocalledanM@-set.ThesamesynrtaxmsformUR2Mandsc2SN2>O(UHU@)(M)stoh(mm20).ӄThelorwersroutestakesitQUtoQVh(m)h(m209).lThecommrutativityQUofthediagramthenfollorwsfromthefactthathisahomomorphism.Ucolor push Black1.7.48.PDe nition.$ color popsrc:3781Cats.texLetQC9bSeacategoryV.mA7subfunctorofafunctorF:URC"!wfSet+晹isafunctorG6:Ck!:Set.witho theo propSertrythatforeacrhobjectCKofC5,%G(Cܞ)6Fƹ(C)o andsucrho thatforeacrharrowf{]:3]C)!\Cܞ20Zandeachelementx3]2G(Cܞ),IwehavethatGfG(x)3]=Ff(x).ItÏisÐstraighrtforwardtocheckÐthattheinclusionfunctioniC :ƄG(Cܞ)!Fƹ(C)ÏisÐanaturaltransformation.Vcolor push Black1.7.49. Example.hi color popsrc:3791Cats.texLetBR%bSea xedset.GWVede neafunctorRʣ:ZSet=op%.'H>!7SetOsucrhthatfor@asetA,V@RJ(A)=Rel⁹(A;B),the@setofrelationsfromAto@B.;(A@rffelationfrom@AtoBisessenrtiallysetoforderedpairsinA8;B.)FVorasetfunctionfA:BA20{ !VJAandrelation 2]Rel(A;B),de neRJ(fG)( )tobSetherelation 20&2]Rel(A209;B)de nedbrya20 20bifandonly[iffG(a209) b.}ItiseasytoseethatthismakresRN:Setop% '#!7œSetOWڹafunctor.(NotethatRJ(A)UR=RelO(A;B),butRisnotMor Rel()4(-;B).)src:3802Cats.texFVoreacrhA,let'A 36:URRelO(A;B)URn!1Mor).(A;PB)bSethebijectionthattakresarelation !fromAq toq B tothefunctionthattakresanelemenrta:2:Atothesetfb:2:Bja bg. (YVoushouldcrheckVthatUthisisabijection.)IfwrecheckUthatthefunctions'A f:arethecompSonenrtsofanaturalTtransformationfromRmֹtoMor(A;PB),othetransformationwillautomaticallybSeanatural{isomorphism|bryTheorem1.7.36._ZTVoshorwthatitisnatural,let ~2k'Releҹ(A;B)anda20#2URA209.8ThenDMor-(f;PB)('A( )(a 09))UR='A( )(fG(a 09))=fbjf(a 09) bg=fbja 0  0bg='A0 (RJ(fG)(a 0))src:3815Cats.texasrequired.src:3817Cats.texThisnaturalisomorphismcanbSetakrentobethede ningpropertryofatopos.WYAtopffosisacartesianclosedcategorywithsomeextrastructurewhicrhproSducesanobjectofsubobjectsforeacrhobject.8ThisstructuremakestopSosesverymuchlikethecategoryofsets.color push Black1.7.50.kExample.z color popsrc:3825Cats.texFVorleacrhsetS׹,AletfgS7:Grf'!/SetBչ.yIttakesaUgraphG toitsKsetG0 ڹofnoSdesandahomomorphism'to'0.\iNorwpickagraphwithonenoSdeandnoarrorwsandcallitEù.8LetV¹=URMorOGrf((E;-).src:3861Cats.texA&graph2homomorphism3fromthegraphE-toanarbitrarygraphG`isevidenrtlydeterminedbry1theimageofEandthatcan0bSeanynoSdeofG..cInotherwords,noSdesofG?_are`essentiallythesamething'asgraphhomomorphismsfromE_toG.,thatis,astheelemenrtsofthesetVp(G.).src:3868Cats.texWVegcande neanaturaltransformation h:URV M!`N%Lbryde ning G.(fG)=f0()whereGisagraphoandfQ:UREh!G%isagraphhomomorphism(arrorwoofGrfo).TheremustobSeanaturalitydiagram(6)foreacrharrowofthesourcecategoryV,7whicrhinthiscaseisGrf _.+Thrustoseethat 7isnatural,wrerequirethatforeachgraphhomomorphismgË:URG1V .!5G2,thediagramDL(11):3ȷhVpG1:3hVpG2{:2fdά-qXVpg33N@G133N@G2032fda@ά- rℐN@g0Ǡ@fed#Ǡ?붳Aj G1)Ǡ@fe]#Ǡ?붳 G2src:3884Cats.texcommrutes.*NowwkN@g她isg0 7p(thenoSdemapwlofgn9)bryde nition,andthevXalueofVܹ(whicrhisaψhomωfunctor)atahomomorphismg=¹compSosesg=withagraphhomomorphismfromthegraph4Eù.-Thenwrehave,forahomomorphismfQ:URE i"!xHG18(i.e.,anelemenrtoftheuppSerleftcornerofthediagram),7( G2jVpgn9)(fG)UR= G2(gfG)=(gfG)0()8src:3892Cats.texwhileҍH(N@g G1)(fG)UR=Ngn9(f0())=g0(f0())ssrc:3894Cats.texandtheseareequalfromthede nitionofcompSositionofgraphhomomorphisms.src:3897Cats.texThenaturaltransformation visinfactanaturalisomorphism.EThisshorwsthatN/˹isnatu-rally:isomorphictoahomfunctor.8Sucrhfunctorsarecalledrffepresentable,]and:areconsideredingreaterdetailin2.1.1color push Black1.7.53.ORemarkn(ConnectedcompSonenrts).j color popsrc:3906Cats.texAnodeOaNcanbSecffonnectedOtothenoSdebofagraphtGѢifitispSossiblestogetfromatobfollorwingasequenceofarrorwsofGѢineitherdirection.\In |ordertostatethismorepreciselyV,-let }ussarythatanarrowa`has'anoSdenifnisthedomainorthecoSdomain(orboth)ofa.wThenaiscffonnectedtobmeansthatthereis=a>sequence(c0;c1;:::ʜ;cnP)=ofarrorws>ofGnkwiththepropSertrythataisanoSde(eitherthesource݀orthetarget)ofc0,!bisanoSdeofcnP,andforiUR=1;:::ʜ;n,"ci1չand݀ciBZharveanoSdeincommon.8WVecallsucrhasequenceanundirffected35pathbetweenaandb.src:3919Cats.texItnisoagoSodnexercisetoseethat`bSeingconnectedto'isanequivXalencerelation.3(FVorre ex-ivitry:4AahYnoSdehXisconnectedtoitselfbrytheemptyhXsequence.)AnequivXalencehYclassofnoSdes color push BlackG color pop+EY[썍color push BlackNaturalTtransformations43G color popn썹with6respSectto6thisrelationiscalledacffonnectedy:componenty;ofthegraph6G.,Iand6thesetofconnectedcompSonenrtsiscalledWG..src:3926Cats.texConnected compSonenrtscanbede nedforcategoriesinthesamewray asforgraphs./Inthatcase,eacrhconnectedcompSonentisafullsubScategoryV.src:3930Cats.texIf\fQ:URG % !z_Hz?isagraphhomomorphism\andiftrwonoSdes\aandbareinthesamecompSonenrtof;KGy,tthenfG(a)andf(b)areinthesamecompSonenrtof;JHX,tthisisbecausefJtakresanundirected|path}bSetrweena}andbtoanundirectedpathbSetrween}fG(a)andf(b).^Thrusthearrorw#fkinducesafunction#Wf:WGlw!=7WH,23namely#theonewhicrhtakes#thecompSonentofatothecompSonenrtoffG(a);andthismakesWnafunctorfromGrfOtoSetӋ.src:3939Cats.texFVor!a graphG.,J~let OG꘹:4kN@G$!8WGNbSethesetfunctionwhicrhtakes anoSdeofGOtothecompSonenrte4ofGathatcontainsthatnoSde.(Thecomponenrtise3thevXalueof OGaatthenode,notžthecoSdomain.)+Then :URN6!Wdcisanaturaltransformation.+Itisinstructivretocrheckthecommrutativityoftherequisitediagram.y1.7.10.Combining35naturffaltransformationsandfunctors.src:3948Cats.texycolor push Black1.7.54.Remark(CompSositesofnaturaltransformations).2 color popsrc:3952Cats.texLetFK:PAO!l,BymandGO:B G!əCbSe3Gfunctors. Thereisa3HcompositefunctorGfF&s:A8!"C|de ned3Hin3Gtheusualwray3GbyGFƹ(A)=G(F(A)).\SimilarlyV,let |HV,KandLbSefunctorsfromAtoBiand u:H|=!$Kand. sŹ:vK!LbSe.naturaltransformations.RecallthatthismeansthatforeacrhobjectAofA,) Ad:HVA~!KܞA۹and OA:KA~!LA.T|Thenasin??۹.2.11,)wrede ne [; x:dHRRk!Lbry( T )AUR= OA A.color push Black1.7.55.Remark4(FVunctorsandnaturaltransformations).W color popsrc:3965Cats.texThingsgetmoreinrterestingwhenwre$Nmix$Ofunctorsandnaturaltransformations.FVorexample,KsuppSosewrehave$OthreecategoriesA .,BfandCc,fourfunctors,trwo .ofthem,FS;GF:AG!,Bfand .theothertrwo .HF:;Ke:FB?!Cc,andtrwonaturaltransformations C:FG{a!Gand P:H !RMKܞ.ƎWVepicturethissituationasfollorws:src:3972Cats.tex9(12)[YFA[YfhB耎趲fd|λb {타Hǻb8Hǻb8j32fd|λ HH {ǻ!Hǻ!H*[YfhB[Y.y!C耎{趲fd|D;b{~타H=;b8H=;b8j{32fd|D; H{H~=;!H=;!H*ìF kH èG  RKA/+UR A0+UR ycolor push Black1.7.56.De nition.? color popsrc:3999Cats.texThenaturaltransformation OF:URHU-F!eK -FTisde nedbrytheformrula( OFƹ)AXM= (FA)foranobjectAofA.UThenotation (FA)meansthecompSonenrtofthenaturaltransformation attheobjectFA.SThisisindeedanarrorwHV(Fƹ(A))d~!Kܞ(F(A))as.jrequired.%TVoshorw.ithat OF0isnaturalrequiresshorwingthatforanarrorwf:ȦAȧ2!A20ofA,thediagramHu (13)KPHV(Fƹ(A))$@Kܞ(Fƹ(A)):2fd'@ά-dm OFA4HV(Fƹ(A209))$Kܞ(Fƹ(A209))432fd%ά- эܯP OFA20aǠ@feɓǠ?냀HV(Fƹ(fG))aǠ@feǠ?냀nKܞ(Fƹ(fG)) src:4017Cats.texcommrutes,:butPthisOisjustthenaturalitydiagramofO pappliedtothearrowOFƹ(fG)4:3F(A)!nFƹ(A209).color push Black1.7.57.De nition. color popsrc:4022Cats.texThenaturaltransformationHV :HWF9SX!bHGٹisde nedbryletting(HV )A=H( A)foranobjectAofA,thatisthevXalueofH%Dappliedtothearrorw A.TVo color push BlackG color pop,YJY[썍color push Black44F:oundationsG color popn썹seethatHV 7thrusde nedisnaturalrequiresshowingthatEYiaHV(Fƹ(A))WHV(G(A)):2fd'@ά-˰(C;-);Goin(thiscaseonesarysthatC rffepresentsthe35functor.src:4091Cats.texAdcffontravariantfunctorisrffepresentableifthereexistsanobjectCofCandanaturalisomorphism` D:1qF6!3Mor/T0C4(-;Cܞ)toathehomfunctorMor8^C(-;Cܞ);arbitraryarrorwintoA.uInT>thiscontext,nanarbitraryarrowT>a :T]!jAT?iscalledavariable*$element*#ofA,+pffarametrized*$byTƹ.5ThesetofvXariableelemenrtsofAparametrizedbryTnisA(Tƹ)UR:=MorOC(T;A).src:4124Cats.texWhenaistreatedasavXariableelemenrtofAandfҹhassourceA,onemarywritefG(a)forfa.8Sowremayconsiderf2asamapofvXariableelements:jYxcfQ=URMorOC(T;fG)UR:MorOC(T;A)n!1Mor).C/g(T;B):src:4128Cats.texSo fStakresthevXariableelements ofAwithparameterT_tothevXariableelemenrtsofBwiththesameparameterTƹ.color push Black2.1.4.Prop`osition. color popsrc:4134Cats.texIf35f;gË:URA!B;arffemorphismsinCjthenthefollowingareequivalent:5, color push Black|(1) color pop%src:4137Cats.texfQ=URgn9, color push Black|(2) color pop%src:4138Cats.texfG(a)UR=gn9(a)35forallpffarameters35TandallvariableelementsaUR2A(Tƹ). color push BlackG color pop.uY[썍color push Black46ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popn썍color push BlackPrffoof. color pop#Rsrc:4144Cats.texClearly(1)implies(2).\Assumethat(2)holds.TVakreTF:=Aanda=1A.ThenfG(a)UR=gn9(a)impliesfQ=URf1A 36=f(1A)=gn9(1A)=g1A 36=gn9.{2Ks2.2.Terminalandinitialobjects.src:4151Cats.texsrc:4155Cats.texOneTofUthemostfundamenrtalobjectsinthecategoryofsetsisasingletonXsetT=URfg,asetwithEexactlyoneelemenrt.2IthasDthecategoricalpropSertyV,thatDthereisexactlyonearrowA!nTJfor)eacrhsetA.# ThelastpropSerty(canbSegeneralizedtoarbitrarycategoriesasfollows.:!color push Black2.2.1.De nition. color popsrc:4163Cats.texAnobjectToɹofacategoryC8iscalledaterminalobjeffctifthereisexactlyone)arrorwAo!lT\foreachobjectAofC5.WVeusually)denotetheterminalobjectbry1andtheuniquearrorwAURn!11byhi.src:4168Cats.texTheZdualnotion[(see1.4.13),janobjectofacategorythathasauniquearrorwtoeacrhobject(includingitself8),iscalledaninitial35objeffctandisoftendenoted0.: color push Black2.2.2.Examples.t color popsrc:4175Cats.texInthecategoryofsets,2theemptrysetisinitialandanyone-elementsetisterminal.WThrusJ thecategoryofsetsJ hasauniqueinitialobjectbutmanyterminalobjects.Theone-elemenrtmonoidisbSothinitialandterminalinthecategoryofmonoids.src:4181Cats.texInthecategorydeterminedbryapSoset,]anobjectisinitialifandonlyifitisanabsoluteminimrum]for]thepSoset,z>anditisterminalifandonlyifitisanabsolutemaximrum.{Sincethere%is&nolargestorsmallestwholenrumbSer,the%categorydeterminedbrythesetofinrtegerswithitsnaturalorder(thereisanarrorwfrommtonifandonlyifmURn)givresanexampleofacategorywithoutinitialorterminalobject.src:4190Cats.texInգtheդcategoryofsemigroups,theemptrysemigroup(see1.2.9)istheinitialobjectandanryone-belemenrtcsemigroupisaterminalobject.eOntheotherhand,thecategoryofnonemptrysemigroupsdoSesnotharveaninitialobject.src:4196Cats.texWVarning:To@prorvethis,gitisnotAenoughtosayAthattheinitialobjectinthecategoryofsemigroupsEisEtheemptrysemigroupandthatsemigroupismissinghere!JYVouharvetoEshowthat{.no{/otherobjectcanbSetheinitialobjectinthesmallercategoryV.sOnewrayto{.dothisistoletU^bSethesemigroupwithtrwoelements1ande͹with1zye_=^e1=_e,*11=_1andeJe͹=e.ThenanrynonemptysemigroupSǹhastwohomomorphismstoU@:qtheconstantfunctionEMtakingELevrerythingto1andtheonetakingevrerythingtoe. HThrusnononemptrysemigroupScanbSetheinitialobject.src:4208Cats.texIn6thecategory6ofgraphsandgraphhomomorphisms,thegraphwithonenoSdeandonearrorwistheterminalobject.color push Black2.2.3.7Prop`osition.'H color popsrc:4213Cats.texA2nyytwoterminal(rffespectivelyyinitial)yobjectsinacategoryyC-areiso-morphic.color push BlackPrffoof. color pop#Rsrc:4218Cats.texSuppSose|1and120Kareterminalobjects.Since1isterminal,tthereisanarrorwf<:N<120!N1.?SimilarlyV,thereisanarrorwg:{1L!1209.Thearrorwfhm ng:{1{L!1isanarrowwithtarget{1.+'Since1|isaterminalobjectofthecategoryV,ɷtherecanbSeonlyonearrorwfrom1to1.ThrusitmustbSethatfMYZgistheidenrtityof1.AnanalogousproSofshorwsthatgsZfḹistheidenrtityof1209.color push Black2.2.4.>Remark.B color popsrc:4229Cats.texInSet!,anelemenrtx?ofasetAistheimageofafunctionfromasingletonset'itoAthattakrestheuniqueelementofthesingletontox.#ThusifwepickaspSeci csingletonfgandcallit1,AtheelemenrtsofthesetAareinonetoonecorrespSondencewithMor5(1;A),whicrhlisthesetloffunctionsfromtheterminalobjecttoA.Moreover,iffzu:2wA!Bgis?ba?asetfunctionandxisanelemenrtofAdeterminingthefunctionx刹:1!A,Tthen color push BlackG color pop/Y[썍color push BlackmTheTextensionprinciple-47G color popn썹theeelemenrtdfG(x)ofB%kisessenrtiallythesamethingasthecompSositef.xUR:1n!1B.Becauseofgthis,AthecategoristtrypicallythinksfofanelementxUR2AgasbSeingtheconstantxUR:1n!1A.Ƌcolor push Black2.2.5.xDe nition. color popsrc:4244Cats.texAnarrorw1Z!q*AinacategoryV,*+where1istheterminalwobject,*,iscalledacffonstant35oftypeA.src:4248Cats.texThruseachelementofasetisaconstanrtinSeto.set>ofarrorwsofasmallcategoryistheobjectpartofafunctorthatisrepresenrtedbythecategory2 ,whicrhisthegraph2Pwiththeadditionoftwoidentityarrows.2.4.Isomorphisms.src:4364Cats.texsrc:4368Cats.texIn 1.7.16wrehavede ned thenotionofanisomorphism.ThisisanotherexampleoftheprincipleofcorvXariantextensionofset-theoreticpropSerties.src:4372Cats.texInMgeneral,thewrord`isomorphic'isusedinamathematicalcontexttomeanindistinguishableinform.color push Black2.4.1.De nition. color popsrc:4376Cats.texAmapfQ:URAn!1BinSet3iscalledanisomorphismifitisbijectivre.src:4380Cats.texItz5isz4clearthatf:IAc4!B;isz5anisomorphismi thereisaninrversemapz5g:IB:!GAsucrhthatgfQ=UR1A ȌandfgË=UR1BN>.src:4384Cats.texIn Lthecategory MofarrorwsofSet{twoarrows Mfx:zA!,BSand LfG20:A20Wq>!B20rareisomorphicifandzonlyiftherearemapsgË:URAn!1A209,Jh:BX !_7B20i?,Ign920Ĺ:A20#=!jA,andzh20#:B20!-pBsucrhthat ҍʍuhfQ=URfG20gn9; h20xfG20k=fgn920; hh20#=1Bd0 :src:4396Cats.texwithB(14)mKAmK,A20:2fdά-t{;gfK>OBfK2B20:Þ32fdά- hhmKmKABS:2fdά-dqgn920fKfK0OBۜ32fdά- ۍcah20mKAmK*A20ғ:2fdά-t{;gfK0OBfK)2B20 ,Þ32fdά- Zh1Ǡ@fecǠ?냀=.color push BlackPrffoof. color pop#Rsrc:4439Cats.texLetfڃbSeanisomorphism. 0tChooseCf:=&B. 0tThenMorȂC 6A(B;fG)&:Mor\şC ʄ(B;A)@S!Mor5C(B;B)ӧisӨabijectivremap.15ThusӧthereisgË2URMorOC(B;A)withfë{gË=URMorOC(B;fG)(gn9)UR=1BN>.}FVurthermore2MorT/C(A;fG) :MorCPǹ(A;A)Ɩ!sMor*C0_(A;B)2isbijectivre1henceMorT/C(A;fG)(g;fG)UR=fgfQ=UR1B f=URf1A 36=MorOC(A;fG)(1A)impliesgfQ=1A.src:4448Cats.texConrverselynassumethatthereisamorphismgË:URBX !_7AsucrhnthatgfQ=1A LandfgË=1BN>.LetZC7AbSeanZobjectinC عandhǫ:ǬCJ!A. ThenMorC`(C5;gn9)23Mor0CH(C;fG)(h)ǫ=Ǭgl2f1hz*=h-hence-MorcCֹ(C5;gn9)2Mor/C)(C;fG)z*=1MorX6 C0!(C;A)*-. 8FVurthermore-let-kG:CVpS!B.ThenMor5C(C5;fG)zyMorvCP5(C;gn9)(kg)UR=fyygko=URkThencen6Mor3C(C5;fG)zMorvCP5(C5;gn9)UR=1MorX6 C0!(C;Bd)*.eThrusMor5C(B;fG)UR:MorOC(C5;A)n!1Mor).C/g(C5;B)isabijectivremap.ėsrc:4460Cats.texWVenorwhavetoshowthatthisde nitionsatis esextensionprinciple2.3.1(3).src:4463Cats.texLetfܹ:WAWqi!HBbSea(categorical)isomorphisminSetkp.ByLemma2.4.3fʌhasaninrversemapgË:URBX !_7A,henceitisbijectivre.Ícolor push Black2.4.4.VProp`osition.o( color popsrc:4468Cats.texIfKfֹ:A.B!BPandg6:BbH!!CarffeisomorphismsinaJcategorywithinversesnrfG21͹:URBXV!Anqandgn921 :C1[!B,thengckfqisnqanisomorphismwithinversefG21 kgn921 ʵ.src:4474Cats.texTheproSofisomitted.5Thispropositionissometimescalledthe`ShoSe-SocrkTheorem':qtoundodthedactofputtingonyroursoScks,WthenyourdshoSes,Vyouhavedtotakedo yourshoSes,WthenyroursoScks.Ícolor push Black2.4.5.,De nition. color popsrc:4480Cats.texLet+CvabSeacategoryandsuppSosethatAandB^1aretrwoobjects,ofC5.+WVesarythatAisisomorphic35toB,writtenAPUR԰n:=B,ifthereisanisomorphismfQ:URAn!1B.color push Black2.4.6.qDe nition. color popsrc:4487Cats.texAnarrorwfQ:URAn!1Aqinacategory(withthesourceandtargetthesame)iscalledanendomorphism.8Ifitisinrvertible,itiscalledanautomorphism.Ícolor push Black2.4.7.0Examples.s color popsrc:4493Cats.texIdenrtityarrowsinacategoryareisomorphisms(henceanautomorphisms).InJC1 (C;B)isinjectivre%forallobjectsCFinC5. color push Black|(2) color pop%src:4580Cats.texAjmorphismkf+:AA!B"inankarbitrarycategoryCQiscalledanepimorphismif%Mor;}CmropH߹(C5;fG)UR:MorOCmrop&(C;A)n!1Mor).Cmrop7o(C;B)isinjectivreforallobjectsCFinC5.color push Black2.5.3.Prop`osition. color pop color push Black|(1) color pophgsrc:4589Cats.texAЛmorphismf:yA߀!XBkisamonomorphismifandonlyifit%satis es35theleftcancelationpropSertry:%color push Black +, color pop=Ѭsrc:4592Cats.tex8C12URC5;338gn9;h:C[!A:OfgË=URfhUR=)gË=h: color push Black|(2) color pop%src:4595Cats.texA׵morphism fǹ:`A`2!'Bs'isanepimorphism!ifandonlyifitsatis estherighrt%cancelationpropSertry:%color push Black +, color pop=Ѭsrc:4598Cats.tex8C12URC5;338gn9;h:BXV!Cܞ:OgfQ=URhf=)URgË=h: color push BlackPrffoof. color pop#Rsrc:4605Cats.texTheleftcancelationpropSertrysaysthatV Mor Cȹ(C5;fG)UR:MorOC(C;A)n!1Mor).C/g(C;B)src:4607Cats.texisinjectivreforallCFinC5.src:4609Cats.texTherighrtcancelationpropSertiesfollowsbydualityV.4 Xsrc:4613Cats.tex0903.06.04 src:4615Cats.texWVe> norwhaveto> showthatthede nitionofamonomorphism> satis estheextensionprinciple2.3.1(3). color push Black2.5.4.zProp`osition. color popsrc:4620Cats.texAmapain`Set-is`a(cffategorical)monomorphismifandonlyaifitisinjeffctive. color push BlackG color pop3䃠Y[썍color push Black1MonomorphismsTandepimorphisms51G color popn썍color push BlackPrffoof. color pop#Rsrc:4625Cats.texLet_f:вA=!BbSeamonomorphisminSetHԹ. ThenMorSet(ԉ(C5;fG):MorSet)EJ(C;A)!Mor))Set7h (C5;B)eeisefinjectivreforallsetsCܞ. Letx;yH42AwithfG(x)=f(yn9). LetCBbSea terminalobjectfginSet .Thentherearemapsgn9;he:efg~!A withg()e=exandh()UR=yn9.6'The~compSositessatisfy}fg()UR=fG(x)=f(yn9)=fh()}hence~fgË=fh~andgË=URh.8Sowregetx=gn9()=h()=yXwhicrhshowsthatf2isinjective.src:4635Cats.texConrverselycassumebthatfbisinjectivre.cLetgn9;h:Cl_!Amapswithfpm(ng=fh.cThenfG(gn9(x))UR=f(h(x))forallxUR2Cܞ,-hencegn9(x)=h(x)andgË=URh.Thrusfιisleftcancelableandhenceamonomorphism.OVssrc:4641Cats.texUsingGtheHnotationofvXariableelemenrtsof2.1.3,ofFisamonomorphismifforanryvXariableelemenrtsx;y:sT/ !A,ifxs6=yn9,thenfG(x)s6=f(yn9),i.e.nuf:sA(Tƹ)C!B(T)isinjectivreforallparametersTƹ.color push Black2.5.5.qRemark.D color popsrc:4648Cats.texNorwqthatweqhavecompletedallqthreestepsoftheextensionprinciplewremaryabbreviatetheterm`categoricalmonomorphism'justto`monomorphism'.src:4650Cats.texAnuarrorw,MthatisavmonomorphisminacategoryV,LisamonomorphisminanrysubScategoryithappSens82to81bein.cHorwever,[an81arrowcan81bSeamonomorphisminasubScategoryofacategoryCݹwithoutbSeingamonomorphisminC5.color push Black2.5.6.Examples.C color popsrc:4657Cats.texInmostfamiliarcategoriesofsetswithstructureandfunctionsthatpre-servrestructure,7themonomorphismsareexactlytheinjectivefunctions.6Inparticular,7themonomorphisms#`in#aMon!Tare#atheinjectivrehomomorphisms(see2.5.7).sThisismoreevidencethat Xde nition Y2.5.2isthecorrectcategoricalde nitiongeneralizingtheset-theoreticconceptofinjectivitryV.src:4666Cats.texInLtheMcategorydeterminedbryapSoset,evreryarrowMisamonomorphism.aAImonomorphismofthecategorydeterminedbryamonoidisgenerallycalledleftcancelable.src:4670Cats.texAn|isomorphism}inanrycategoryisamonomorphism.(FVorsuppSosef{isanisomorphismandassumefxUR=fyn9.8Thenx=fG21O#fx=fG21O#fyË=yn9.color push Black2.5.7.PProp`osition. color popsrc:4677Cats.texAmonomorphisminthecffategoryofmonoidsisaninjeffctivehomomor-phism,35andcffonversely.color push BlackPrffoof. color pop#Rsrc:4682Cats.texLetAff0:M)Cg!,`M@20PbSeamonoidAghomomorphism.=SupposeitAfisinjectivre.=Letgn9;h:V!|MbSehomomorphismsforwhicrhf^g3=bfh.%FVoranryv32bVp,fG(gn9(v))=fG(h(v)),sogn9(v)UR=h(vn9)sincef2isinjectivre.8HencegË=URh.Itfollorwsthatf2isamonomorphism.src:4689Cats.texEssenrtiallyM.thesameproSofworksinothercategoriesofstructuresandstructure-preservingmaps){if)themapisinjectivreitisamonomorphismforthesamereasonasinSetInBgeneral,WthisneednothappSen.OneexampleisBtheinclusionofZinQinRi)describSed@in??A.(aninrverse@wouldalso@havetobSeaninverseinSet)z,Vbutthereisn'tonesincetheinclusionisnotbijectivre).src:4935Cats.texAneasierexampleisthearrorwinsrc:4937Cats.tex!bΔC%DQ\32fdj0ά-(|  7 „fdά-(|  0 „fdά-src:4944Cats.texfrom: CtoDS.' Itisbothmonic: andepic(vXacuously)butthereisnoarrorwfromDtoCsoitisnotanisomorphismbSecausethereisnoarrorwinthecategorythatcouldbSeitsinrverse.src:4950Cats.texIf|Ywretry|Ztogeneralizethenotionofasurjectivremapaccordingtotheextensionprinciplewreobtainthenotionofasplitepimorphism.8WVe rstinrtroSducethisnotion.src:4954Cats.texAnarrorwf:zAzu!aBŹinacategoryisanisomorphismifithasaninrverseg#:zB/{!hAwhicrhmrustsatisfybSoththeequationsge,f=]1A candf\+gT=]1BN>. Ifitonlysatis esthesecondequation,f B g>=1BN>,thenfisaleftinverseofg7=and(asyroumightexpSect)g7=isarightinverse꨹offG.color push Black2.5.15.glDe nition.? color popsrc:4962Cats.texSuppSosegkfkhasarighrtinverseglgn9.+Thenfkiscalledasplitepimorphism(f2issplit35bygn9)andgXiscalledasplitmonomorphism.7color push Black2.5.16.Lemma. color popsrc:4978Cats.texEvery35surjeffctioninSetOMisasplitepimorphism.color push BlackPrffoof. color pop#Rsrc:4982Cats.texIff:AŨ!qB,*ethencrhoSose,*fforeachb2B,*fsomeelemenrta2AsucrhthatfG(a)=b.TheHexistenceHofsucrhanaisguaranrteedbyHsurjectivityV.De negn9(b)HtobSea.ThenfG(g(b))UR=fG(a)UR=b꨹foranrybUR2B,sofgË=UR1BN>. Eҍsrc:4989Cats.texTheso-calledaxiomofcrhoiceisexactlywhatisrequiredtomakeallthosegenerallyin nitelymanrychoices.src:4992Cats.texAnd6oin6nfact,Z{onepSossibleformrulationoftheaxiomofcrhoiceisthatevery6nepimorphismsplits. color push BlackG color pop6'Y[썍color push Black54ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popncolor push Black2.5.17.Prop`osition. color popsrc:4996Cats.texA35morphismfQ:URA!B;in35Cjisasplitepimorphismifandonlyif/MoreCX(C5;fG)UR:MorOC(C;A)!Mor*GC/͹(C;B)src:4999Cats.texis35surjeffctiveforallobjectsCinC5.e鍍color push BlackPrffoof. color pop#Rsrc:5003Cats.texLet$flharvethesplittingg&:pBSum!%rA.Leth2MormC\,(C5;B).Theng@Nho2MormC\,(C5;A)andf(gh)UR=(fgn9)hUR=h꨹sothatMor Cd(C5;fG)issurjectivre.src:5008Cats.texConrverselyBassumeCthatallMorF?C(C5;fG)aresurjectivre.ChoSoseC1=URBHandletgË2URMorOC(B;A)withMor5C}(B;fG)(gn9)y;=y<1B y2Mor8C(B;B).x,Thenfgt=1B MsothatfGisasplitepimorphism.kasrc:5014Cats.texSoewrefhavecheckedfallitemsfortheextensionprincipleandasplitepimorphismisthecorvXariantextensionofthenotionofsurjectivremapinSetӋ.src:5018Cats.texEpimorphisms in othercategoriesmarynotbSesplit.IThefunctionthatincludesthemonoidofnon-negativrejintegersk(N;+)onadditioninthemonoidofalltheinrtegers(Z;+)onadditioncertainly*doSes*notharve*arighrtinverse*inthecategoryofmonoids,:sinceitdoSesnotharve*arighrtinverseinthecategoryofsets.ՃThereareplentyofexamplesofepimorphismsofmonoidswhicrharesurjectivewhichhavenorightinverseinthecategoryofmonoids,eRalthoughofcoursektheydointhelcategoryofsets.)Onesucrhepimorphismofmonoidsisthefunctionthat@takres@theintegers@moSd4onadditiontotheinrtegersmoSd2onaddition,Uxwith0and2goingto0and1and3goingto1.src:5032Cats.texUnlikreepis,whichalwayssplitinthecategoryofsets,monicsinSet(,donotalwrayssplit.Evreryarrowoutoftheemptysetismonicand,savefortheidentityof;toitself,isnotsplit. On]the]otherhand,yevrerymonicwithnonemptrysourcedoSessplit. WVelearvethe]detailstothereader.d2.6.Sub`objects.src:5053Cats.texsrc:5057Cats.texThefconceptofsubSobjectisinrtendedtogeneralizetheconceptofsubsetofgaset,submonoidofQ#aQ$monoid,jsubScategoryofacategoryV,jandsoon.lSThisideacannotbSetranslatedexactlyinrto categoricalterms,esince theusualconceptofsubsetviolatesthestricttrypingrulesofcategoryNtheory:togofromNasubsettoasetrequiresacrhangeoftrypSe,msothereisnofeasiblewrayotosarynthatthesameelementxisninbSothasetandasubsetoftheset.4Becauseofthis,anrycategoricalde nitionofsubSobjectwillnotgivreexactlytheconceptofsubsetwhenappliedtothecategoryofsets.!Horwever,theusualde nitionofsubSobjectproduces,inSet,avconceptthatisnaturallyequivXalenrttotheconceptofsubset.Thede nition,Vwhenappliedtosets,de nessubsetintermsoftheinclusionfunction.src:5073Cats.texWVe'~need'apreliminaryidea.cLetC5=CbSeacommacategoryV.cWe'~callanobjectf޹:Ak!LCmonic꨹iff2isamonomorphisminC5.ecolor push Black2.6.1.f^Prop`osition.?- color popsrc:5076Cats.texIffo:'AP!7CandfG20>:A20 \!pCarffemonic,Ythenthereisatmostonemorphism35gË:UR(A;fG)!(A209;fG208)35inC5=Cܞ.color push BlackPrffoof. color pop#Rsrc:5080Cats.texGivrengn9;g20 :](A;fG)]w0!ع(A209;f208). (Thenf20g0g߹=]f=]f20hgn9202inC5. )SincefG20 isamonomorphisminCݹwregetgË=URgn920isamonomorphism+inDUV.Thenitiseasytoprorve+that >isamonomorphisminMo`dX(G.;DUV).8Theconrverseisnottrue.2.7.Pro`ducts.src:5119Cats.texsrc:5122Cats.texAnotherapplicationoftheextensionprinciplerelatestoproSducts.\WVe rstde netheproductoftrwosets.color push Black2.7.1.De nition. color popsrc:5126Cats.texIfAandB7$aresets,theCartesianprffoductA =Bisthesetofallorderedpairswith rstcoSordinateinAandsecondcoordinateinB;inotherwrords,ԍABX=URf(a;b)ja2A꨹and|b2Bg:Սsrc:5132Cats.texThe /coSordinates 0de nefunctionspA lH=dprojrT1!ڹ:dA|B)jB![A /andprojC>T2!=dprojrT2!ڹ:dAB)jB![Bcalledthecffoordinate35functions,ortheprffojections.src:5137Cats.texNorwthisde nitiondoSesnotsatisfythe rstpropSertryfortheextensionprinciple,iasetXisomorphictoAB$willingeneralnotconsistofpairsofelemenrts.Sothesetsf0;1;2;3;4;5gandf0;1;gtsf0;1;2gareclearlyisomorphic,bSecausebothharve6elements,butthe rstsetdoSesnotconsistofpairs.dSoherewrehaveasettheoreticde nitionthatreferstospSeci cpropSertiesoftheelemenrts.src:5146Cats.texAllthemoreitisinrterestingto ndoutthatthereisanexamplefortheextensionprinciplehiddenbSehindtheirconcept.color push Black2.7.2.CProp`osition. color popsrc:5151Cats.texLffetύA,6Bjbesets. ;pTheόCartesianproductABjtoffgetherόwiththeprffojectionsprojI,T1#K:AOB"!AandprojI,T2:AOB"!B$satis esthefollowinguniversalprffoperty:j color push Black|(*) color pop%src:5156Cats.texforkeverysetTy1andeverypffairofmapsfQ:URT]!A,gË:T]!Brqtherffekisauniquemap%〹(f;gn9)UR:T]!AB;such35thatthediagrffamG4A2AB|32fdpά 2ԍA#projx1T1 B,32fd@ά- 2ԍùproj)џT2@b߹(f;gn9)bYq(TZǠ*Ffe곌Ǡ?H`ef{,ׁ {, {, {, 4>4> H W gׁ @ @ @ @2l>@2l>R%src:5168Cats.texcffommutes,35i.e.fiprojwT1!]y(f;gn9)UR=f{4andprojjCT2 *E(f;gn9)=g.color push BlackPrffoof. color pop#Rsrc:5174Cats.texWVe rstshorwtheuniquenessofthemap(f;gn9):T@Z!AB:'GivrenTƹ, fG, andg.KIfh;k*@:#Td~t!AA֕B3are+,maps+-sucrhthatprojb:T1 "<h=f "=proj1T13kJandprojb:T2 "<h=g1\=proj1T23kthen foranrytB2BTqwehaveh(t)B=:(a;b)B2ApBand kg(t)B=:(a209;b20)B2AppB.Then color push BlackG color pop8TaY[썍color push Black56ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popn썹wregetaU=projcT1 g(a;b)T=(proj7T1h)(t)=fG(t)=(proj7T1kg)(t)=projcT1 g(a209;b20)U=a20andbɹ=projןT2۹(a;b)=(proj7T2h)(t)=gn9(t)=(proj7T2kg)(t)=projןT2۹(a209;b20)=b20,dhence]h(t)=(a;b)UR=(a209;b20)UR=kg(t)andhUR=k.8Thisshorwstheuniquenessofthemaph.src:5185Cats.texExistence:O2FVromtheuniquenessproSofwreobtainareasonablede nitionof(f;gn9).Z[FVorthP2hQTwrede ne]n(f;gn9)(t)UR:=(fG(t);gn9(t)):Nsrc:5188Cats.texThispisamapfromT>6toAB.xSinceitsatis es(proj7T1(f;gn9))(t)UR=fG(t)pand(proj7T2(f;gn9))(t)UR=gn9(t)wregetproj!T1(f;g)UR=f2andproj!T2(f;g)=g.˺9|src:5194Cats.texObrviously3anytriple(PS;p20bA c:P'n @!ƣA;p20bB :P'n @!B)3isomorphic3to(AB;proj7 T1;proj7 T2)satis esTtheSsameunivrersalpropSertyV.InSfactleth_:PO!{OASB"ZbSeTanisomorphismsucrhthatA|bY>PAƍ[p20bAB̟ҁ Bׁ̟ m k]m k]H Bƍ,p20bB$Lҁ H$Lׁ H k]H k]j`2AB􍍒ڹprojT1B̟ǠHB̟ǠHm cHm cY`􍍒,proj$:T2$LǠ$LǠ c c*HZǠ*Ffe곌Ǡ? f hOsrc:5205Cats.texcommrutes. SLete$TbSeae#setandletf!:ًT{R !njA,gGĹ:T{R !B*bSee#maps. TThenthee$maph21 T(f;gn9)UR:T!ePbLsatis esp20bA 2~T(h21T(f;gn9))=fandp20bB T(h21T(f;gn9))=g.*ItisaneasyexercisetoshorwthatthismapisuniquewiththispropSertyV.!SotheuniversalpropSertygiveninthetheoremsatis esthe rstpropSertryoftheextensionprinciple.src:5212Cats.texIntarbitraryucategorieswrecannotconstructtheCartesianproSductoftrwotobjectssincethereare no elemenrtsandwe thuscannotconstruct pairsofelements.VSo whenweuse thenotationA66BMinanarbitrarycategorythiscannotmeanasetofpairsofelemenrts.%ItwillstandforanarbitraryobjectwithadditionalpropSertiesdescribedbrymorphisms.src:5220Cats.texTheextensionprinciple2.3.1(2)prorvidesthefollowingde nition.}color push Black2.7.3.De nition. color popsrc:5224Cats.texGivrenobjectsAandBinacategoryC5.TAnobjectAB¹togetherwithmorphisms pA 36:URAyBX !_7AandpB :URABX !_7B)iscalleda(notthe!)(cffategorical)productofAandB,andthemorphismspA,pB Darecalledprffojections,ifforallobjectsTinC thereisanisomorphismofsetsCx9Mor6C%(T;AB)PUR԰n:=Mor%5C*(T;A)Morय़CNd(T;B)src:5232Cats.tex(whereMor Cd(T;A)Morय़CNd(T;B)istheCartesianproSduct)sucrhthatthediagramn2sMorpCb/(T;AB)@MorV"؟C[(T;A)^MortߟCyu(T;pA) l l  lF_ l l  lF^ l lx lF]vq vq )Zf;Moro8Cu (T;B)8,MorN)CS(T;pBN>)\P \ P\F_P!\P+\ P5\F^P?\PI\PS\F]PTl PTl qJ7Mor4C(T;A)Morय़CNd(T;B))捑lpMorX6 C0!(TV;A) lǠP lrKP lP lǡP lrLP lP lǢP lrMPx lPvqܕJPvqܕJi)捒8,pMorX6 C0!(TV;Bd)\Ǡ \rK\!\ǡ+\rL5\?\ǢI\rMS\TlܕJTlܕJ1ZǠM@fe곌Ǡ?1f h9src:5245Cats.texcommrutes.}src:5249Cats.tex0911.06.04color push Black2.7.4.GProp`osition}D(Characterizationofproductsby}Etheuniversalmappingprop-erty).DI color popsrc:5253Cats.texGivenobjeffctsAandBI$inacategoryC5.&A2nobjectABI%togetherwithmorphismspA 36:URABXV!A35andpB :ABXV!B;is35a(cffategorical)35product, color push BlackG color pop9iY[썍color push BlackةProAductsi57G color popn썍 color push Black(**) color pop%src:5257Cats.texif.and-onlyifforeffachobject.Th21C]candeffachpair.ofmorphismsfy:1Th9!kwA,g۹:1T%(I!7?B;therffe35isauniquemorphism(f;gn9)UR:T]!ABsuch35thatthediagrffamHl~A2AB|32fdpάgۍpA B,32fd@ά-gۍTVpB@b߹(f;gn9)bYq(TZǠ*Ffe곌Ǡ?H`ef{,ׁ {, {, {, 4>4> H W gׁ @ @ @ @2l>@2l>RX?%src:5269Cats.texcffommutes,35i.e.fipA (f;gn9)UR=f{4andpB (f;gn9)=g.wEcolor push BlackPrffoof. color pop#Rsrc:5275Cats.tex(=:.Let(AhIhJB;pA;pBN>).bSe-aproductofAand-B.|rLetTbe.anobjectin-Ccandlet6u:29Mor6Cg(T;A=k=jB).De nef 8:=9pA Ou:Te!CA6undg2s:=9pB u::Te!CB.Then(f;gn9)UR2MorOC(T;A)]MorRZC(T;B).!Norwwede neh(u)UR:=(f;gn9)2MorOC(T;A)]MorRZC(T;B)and+get*Mor'C^(T;pA)(u)UR=pA 'Iu=fQ=pMorX6 C0!(TV;A)+Ih(u)*andMor(C^(T;pBN>)(u)=pB Iu=gË=pMorX6 C0!(TV;Bd),&h(u).src:5278Cats.texItremainstoshorwthathisbijective.8WVeconstructtheinversemapas@Oko:URMorOC(T;A)Morय़CNd(T;B)URn!1Mor).C/g(T;AB)kg((f;gn9))UR:=usrc:5281Cats.texwhererq(f;gn9)UR2MorOC(T;A)MorCXٹ(T;B).ByrqtherrunivrersalpropSertyofrrtheproSductthereisauniqueuUR:T!eA0302BIsucrhthatpA uUR=fandpB ~q03u=gn9.$WVeusethisuforthede nitionofthemaph.src:5283Cats.texLet(f;gn9)UR2MorOC(T;A)Mor;CT(T;B).Then(hkg)((f;gn9))UR=h(u)=(pA|u;pB Su)UR=(f;gn9)hence(iu)UR=1MorX6 C0!(TV;A)MorXX.C(T;Bd)Y.src:5285Cats.texLetuUR2MorOC(T;A%&B).6WThen(kCh)(u)UR=kg((f;gn9))=k((pA y &u;pB c%u))=u20Iwhereu20#:T!2A!!B4\isVtheUuniquemorphismsucrhthatpA y!u20L޹=~pA z!fUandpB ou20L޹=~pB o!uhenceuUR=u20and(kh)=1MorX6 C0!(TV;ABd)7ڹ.src:5287Cats.tex=):Givren)(u)l=g=pB Qu~withauniqueu.8Thrus(AB;pA;pBN>)isaproSductofAandB.Lcolor push Black2.7.5.Prop`osition. color popsrc:5294Cats.texThe35familyofisomorphismsjPEhT i:URMorOC(T;AB)UR!Mor*GC/͹(T;A)Morय़CNd(T;B)src:5296Cats.texsuch35thatjNsMorpCb/(T;AB)@MorV"؟C[(T;A)^MortߟCyu(T;pA) l l  lF_ l l  lF^ l lx lF]vq vq )Zf;Moro8Cu (T;B)8,MorN)CS(T;pBN>)\P \ P\F_P!\P+\ P5\F^P?\PI\PS\F]PTl PTl qJ7Mor4C(T;A)Morय़CNd(T;B))捑lpMorX6 C0!(TV;A) lǠP lrKP lP lǡP lrLP lP lǢP lrMPx lPvqܕJPvqܕJi)捒8,pMorX6 C0!(TV;Bd)\Ǡ \rK\!\ǡ+\rL5\?\ǢI\rMS\TlܕJTlܕJ1ZǠM@fe곌Ǡ?KDf hT src:5308Cats.texcffommute35forallobjectsTinC5,isanaturalisomorphisminT,A,andB.color push BlackPrffoof. color pop#Rsrc:5312Cats.texWVeshorwthattheinversesjCkT i:URMorOC(T;A)Morय़CNd(T;B)URn!1Mor).C/g(T;AB) color push BlackG color pop:}Y[썍color push Black58ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popnsrc:5314Cats.texasconstructedinPropSosition2.7.4formanaturaltransformation.Soforti:hTƟ20 0h I! ]TawreharvetoshorwthatthediagramE^yMorܟCO(T;A)Morय़CNd(T;B) Mor5AC:ֹ(T;AB):2fdά-TbqkTv6MorlCF(TƟ20o;A)Morय़CNd(TƟ20;B)PpMor3mC8,(TƟ20o;AB)k32fdmά-TkT.:0Ǡ@fe4Ǡ?냀:MorPCUr(t;A)Morय़CNd(t;B)GǠ@feH4Ǡ?냀LMora豟CgVp(t;AB)%src:5321Cats.texcommrutes.xLet(f;gn9)72Mor4CN(T;A)3j3kMorihC'(T;B).xThen[f;gn9]8:=7kT((f;gn9))istheuniquemorphismsatisfyingpA Moù[f;gn9]UR=fѹandpB où[f;gn9]=g./DThetrwosidesofthesquaregivretwomorphisms[f@t;g*t]UR=(kT@MorvC䬹(t;A)@@MorvC䭹(t;B))((f;gn9))and[f;gn9]@@tUR=(Mor5C(f;A@B)kT.:0 R޹)((f;gn9)).WVe*harvetoshowthatthese* areequal.Observethatamorphismut2Mor5C(TƟ20o;A4B)-isuniquely.determinedbrythemorphismspA 4uandpB q4u.pWVegetfrompA Gj[f;gn9]jtUR=fjt=pA G[fjt;g:t]andpB ?[f;gn9]tUR=g9t=pB >[fjt;g:t]theresult[f;gn9]tUR=[ft;gt].src:5323Cats.texNorwletaUR:An!1A20andb:BX !_7B20SbSegivren.8ThenthediagramD^{nMor̟C(T;A)Morय़CNd(T;B)! Mor7C([aif;bfG])UR=p20bB(kоi(Mor5C(T;a)Mor5C(T;b)))((f;gn9))impliesMor Cd(T;ab)ko=URk(Mor5C(T;a)Morय़CNd(T;b)).7Eȍsrc:5350Cats.texBeforewreshowthatthede nitionofaproSductsatis estheextensionprinciple2.3.1(3)weshorwageneraluniquenesstheorem.JKcolor push Black2.7.6.5Theorem. color popsrc:5355Cats.texLffetMAMandBbeobjectsMofacffategoryMC5.{If(PS;pA;pBN>)andM(PƟ20o;p20bA;p20bBN>)arffeNproductsofAMandBTinC5,thenthereisaMuniqueisomorphismkb:EPƟ20 D s!PsuchthatpA ko=URp20bA and35pB k=URp20bBN>.JJcolor push BlackPrffoof. color pop#Rsrc:5362Cats.texSince(PS;pA;pBN>)satis es theunivrersalpropSerty(**) thereisauniquemorphismko:URPƟ20!ooP#(sucrhcthatpA ,Hk=Up20bA _GandpB _k=Up20bBN>.SymmetricallythereisauniquemorphismhEŹ:PƟ20 O!Psucrhwthatwp20bA  h=pA Uйandp20bB Y h=pBN>.Considerwthefollorwingcommutativediagram:yw.>P֗Akm[pA{,M`{,M`{,M`{,M`{,M`vlOvlO tK"PƟ20vp20bA l l ,Qw,Qw) >PƳkpA lΠP lyKP,P,ifK"PƟ20ߧvm[p20bA{,Ǡ@{,Ǡ@{,Ǡ@{,Ǡ@{,Ǡ@vl@vlIs,dBk6,pB쟅M`@쟏M`@쟙M`@쟣M`@쟭M`@𬟱O@𬟱ORvlp20bB\P \ P쟱QwP쟱QwqƳklpB\Π \yK1ߧv6,p20bBǠǠǠǠǠsZՠ@fe곌ՠ?*=hZΠ@fe곌Π?*qkZǠ@fe곌Ǡ?*f hsΠM@feLΠ?wq̹1PtǠM@fe̟Ǡ?wQ1P.:0 color push BlackG color pop;WY[썍color push BlackةProAductsi59G color popnsrc:5383Cats.texSinceOWpAKNmkkԇmjhUR=pA 36=pAKO1P a#andOWpBmkkԇhUR=pB =pBmj1P a#wreOWgetbyuniquenesskԈmjhUR=1P̹.SymmetricallyHwreHgeth__ko=UR1P.:0 Ó,i thushisHanisomorphismwiththerequiredpropSerties. src:5390Cats.texWVe{norwhavetoshowthatthede nition|ofaproSductsatis estheextensionprinciple2.3.1(3).color push Black2.7.7.Prop`osition.{ color popsrc:5395Cats.texGiven sets AandB.YA setPtoffgetherwithtwomapsp20bA 36:URP]!Aandp20bB :AzP@I!'BMsatis estheuniversalprffoperty(*)ofprffoposition2.7.2ifandonlyiftherffeisan35isomorphismhUR:P]!AB;such35thatpA hUR=p20bA and35pB h=p20bBN>.color push BlackPrffoof. color pop#Rsrc:5403Cats.texBy/propSosition02.7.2theCartesianproSductA.l.kBG6andtheprojectionspA |:A.l.kB!nA4andpB :URABX !_7B-:satisfythe3univrersalpropSertyofpropSosition2.7.4.dFVollowingtheproSofOjofOiproposition2.7.2wreOihaveshownthat(PS;p20bA;p20bBN>)Oialsosatis estheunivrersalpropSerty(*).src:5411Cats.texConrverselyifatriple(PS;p20bA;p20bBN>)satis estheunivrersalpropertry(*)resp. ](**)thenbytheorem2.7.6PnandABareisomorphicbryhwithpA hUR=p20bA ȌandpB h=p20bBN>./src:5418Cats.texSointhefuturewrewillassumethatproSductsaregivenbyandsatisfypropSerty(**).src:5421Cats.texAllpropSositionsandtheoremsofthissectionofproSductsareaswrellvXalidforproSductswithmorethantrwofactors,forproSductsofarbitraryfamiliesofobjects(AidjiUR2I).color push Black2.7.8.dDe nition.  color popsrc:5427Cats.texLet(Aidjis2I)dbSeafamilyofobjectseinacategoryC5.nAnobjectQQi2IAiRtogether&Twitha&Sfamilyofmorphisms(pj ԫ:nQi2I "Ai{ ![Ajf jjt2nI)iscalledaprffoduct,u?themorphismsfidڹ]H!,fjܜ ׁ @ @ @ @⌟>@⌟>RJ)src:5442Cats.texcommrute.src:5445Cats.texTheseproSductsconsistofanobjectandafamilyofprojectionsandaredenotedW>(Y;Ai2IUVAid;(pj\:URYi2IAi,ӷ!) Ajf jj%2URI)):Jsrc:5449Cats.texWVelearvethedetailstothereader.src:5508Cats.texIf?Wacategory?XChasaproSductforanrytwoobjectsinCthenitisclearthat?XithasproSductsforanry nitenon-emptyfamilyofobjects.IfCDhasaproSductforanrytwoobjectsinCCandaterminalobjectthenithasproSductsforanry nitefamilyofobjects.color push Black2.7.9.De nition. color pop color push Black|(1) color popzsrc:5516Cats.texAS8categorySTCiscalledSSacategorywith nitekprffoducts,m~ifSTthereis%aproSductinCݹforanry nitefamilyofobjects(emptyfamiliesincluded). color push Black|(2) color pop%src:5519Cats.texA]category̗C̹iscalled̘acategorywithprffoducts,if̗thereisaproSductinC̹foranry%familyofobjects(emptryfamiliesincluded). G17.06.04 src:5529Cats.texThedualnotionofaproSductthenotionofacoproduct.color push Black2.7.10. De nition.{ color popsrc:5532Cats.texLet (AidjiUR2I)bSeafamilyofobjectsina categoryC5.Anobject``i2IM5AiRtogetherPwithQafamilyofmorphisms(j ѹ:Aj 6\!&`'B}i2I6RAidjjc2I)PisQcalledacffoproduct,;themorphismsj\:URAj !*;`$i2I3gAiLarecalledinjeffctions,KifforeacrhobjectT2URCandeachfamily color push BlackG color pop<Y[썍color push Black60ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popn썹ofϮmorphismsϯ(fi,:URAiӷ!) Tji2I)ϮthereisϯauniquemorphismhfidjiUR2Ii:`i2I ~Ai,ӷ!) Tqtsucrhthatforallj%2URI+thediagramsL9-"Aj`:i2I5AiV{fdά-:jHxTǠ*FfeܟǠ?`\hfidiH! fjuׁ @u @u @u @|>@|>R src:5548Cats.texcommrute. color push Black2.7.11.Examples. color pop color push Black|(1) color popaEsrc:5553Cats.texTheCartesianproSductsofsemigroups,monoids,groups,abelian%groups,moSdules,vrectorzspaces,rings,algebras,LiealgebraswithcompSonenrtwise%opSerationsareproducts. color push Black|(2) color pop%src:5557Cats.texThe1;CartesianproSductof1:topologicalspaceswiththeprffoductttopology1;isaproduct.%Here%and&inthe rstexamplethemoreprecisestatemenrtisthatthereexistproSducts%andthattheunderlyingfunctortosetsmapstheseproSductsandtheirprojectionsto%CartesianproSducts.7SothereisaproductstructureontheCartesianproSductsofthe%underlyingsets,buttheproSductstructurehastobedeterminedineacrhcase. color push Black|(3) color pop%src:5565Cats.texInthecategoryof eldsthereareingeneralnoproSducts. color push Black|(4) color pop%src:5567Cats.texLet,G#and,HJbSetrwo,graphs.TheproductGHKinthecategoryof,graphsand%homomorphisms%isde ned$asfollorws:!(GKHV)0V=URG0 H0.)_An%arrow$from(gn9;h)to%(gn920gn920*inGyandb:[hu !Џh20inH.CTheprojectionsare%theusual rstandsecondprojections. color push Black|(5) color pop%src:5573Cats.texWVe&harvealreadyseen&in1.3.8thatanypSoset(partiallyordered&set)hasacorrespond-%ingpcategorystructurepC5(Pƹ)..LetPZbSeaposetandxpandy̹trwopobjectsofC5(Pƹ)(that%is,Helemenrts/of0Pƹ).Letusseewhat,Hifanrything,istheir0proSduct.Aproductmrust0be%ankelemenrtz/Ntogetherlwithapairofarrowsz5!Mxandlz5!yn9,whicrhisjustanother%wraylofmsayingthatz7XTxandzXTyn9.>-Thede nitionmofproSductalsorequiresthatfor%anryw2URPƹ,givenanarroww!xandonew!yn9,thereisanarrorww!z.1src:5584Cats.texThisF{translatestowDHxandwyimplieswz^whicrh,]ptogetherwiththefact%thatwQz5URxandzURyn9,ccrharacterizesz4asthein mumwRofxandy,coftendenotedx^y.%Thrus{thezexistenceofproSductsinsucrhacategoryisequivXalenrttotheexistenceof%in mrums.1src:5591Cats.texInCparticular,ewreseeCthatproSductsgeneralizeawrell-knownCconstructioninpSosets.%Note thatapSosetthatlacrksin mumsprovidesaneasyexampleofacategorywithout%proSducts. color push Black|(6) color pop%src:5595Cats.texThePpproSductofcategoriesasde nedin1.4.12PoistheproductofthecategoriesinCatp. color push Black|(7) color pop%src:5597Cats.texThecoproSductofvrectorspacesisthedirectsum. color push Black|(8) color pop%src:5598Cats.texThe)coproSduct)oftrwo)abelian)groupsinthecategoryofabSeliangroupsisthedirect%sumortheproSduct. color push Black|(9) color pop%src:5600Cats.texThe13coproSductoftrwo13 nite12abeliangroups(6=#0)inthe12categoryofgroupsisan%in nitenonabSeliangroup.color push Black2.7.12.Prop`osition. color popsrc:5615Cats.texIf35Aisanobjeffctinacategorywithaterminalobject1,then11At32fd,cӜ`άqhi |A t32fd*ά-뷍(1AE>src:5621Cats.texis35aprffoduct35diagram. color push BlackG color pop=Y[썍color push BlackEqualizers׊61G color popn썍color push BlackPrffoof. color pop#Rsrc:5625Cats.texAconeorverAand1hastoharvethisform,wherefQ:URBX !_7Aisanryarrow.I1At32fd,cӜ`ά Vpqhi |A t32fd*ά- 7(1AbYTǠ*Ffe,DǠ?`gfH`3nhiׁ d>d> H`fdׁ @d @d @d @$>@$>R?Esrc:5634Cats.texClearlytheonlypSossiblearrorwinthemiddleisfG. color push Black2.7.13.De nition:fand:gRemark.љ color popsrc:5638Cats.texOurnotationA..BImeansthatA.BIisthevrertexofaproSductconewithbasethediscretediagramDwithDS(1)UR=AandD(2)UR=B.)ThenB^MXAdenotestheproSductgivrenbythediagramPPBڌBEAM32fd6άm{_Cp1GA\32fd$0ά-m{4p2Qsrc:5646Cats.texwhere)Bwreuse)Ap1 Fandp2toarvoid)Bconfusing)Athemwiththearrorwsproj`PT1$IandprSoj2 FoftheproSductdiagram. (Ofcourse,Fthisisanadhocsolution. Ifonehadtodealwiththis'эsituation 8a 9lotitwrouldbSenecessarytoinrtroSducenotationsucrhasprojO@FA;B@F1/RandprojO@FBd;A@F1*Hܹ.)ThenthisisaproSductdiagram:SA2BEAØ32fd$0Оάm{p2xB,32fdά-m{Sp1*src:5656Cats.texIt@follorwsAfromTheorem2.7.6thatthereisanisomorphism[p2;p1]UR:BAn!1AB)F(calledtheswitchcmorphism)thatcommruteswiththeprojections.Itsinrverseis[proj7T2;proj7 T1]UR:A&B!nBEA:2.8.Equalizers.src:5665Cats.texsrc:5669Cats.texIfAandB*aresetsandf;gD:n An !B*arefunctions,itisanimpSortanrttasktocollectallsolutionsaUR2Aoftheequation썒xfG(a)UR=gn9(a):#src:5672Cats.texThisismoregeneralthatsolvinganequationfG(a)UR=0sinceBeٹdoSesnotnecessarilyconrtainsomeelemenrt0.src:5674Cats.texAgainwrewanttoapplytheextensionprincipleinthiscase.color push Black2.8.1.FDe nition.} color popsrc:5677Cats.texIfAandBҹaresetsandf;gË:URAn!1BareFfunctions,gtheeffqualizerEqx(f;gn9)isthesubsetEq(f;gn9)URA꨹consistingofallelemenrtsaUR2A꨹forwhichfG(a)UR=gn9(a);inshort,QEq(f;gn9)UR=fa2AjfG(a)=g(a)g:src:5682Cats.texTVogetherwiththesetEq(f;gn9)thereistheinclusionfunctionj%:UREqk(f;gn9)URn!1A.src:5685Cats.texTVoEUmakreETthisintoacategoricalETconceptandapplytheextensionprinciple,\wre rstobservrethatEq(f;gn9)isasubsetofA.SoithasapropSertrythatcannotdirectlybSetransferedtoisomorphicNsets.pButthereMisaunivrersalpropSertyMconnectedwiththisnotionthatwillgivreusthecorrectconcept.color push Black2.8.2.Prop`osition. color popsrc:5688Cats.texLffet+Aand+Bƺbesetsand+f;g:!}A!|!eBƹbefunctions.OTheequalizerEq2(f;gn9)toffgetherwiththeinclusionmapj':IUEq{n(f;gn9)IT!Asatis esthefollowinguniversalprffoperty:' color push Black color pop%src:5690Cats.texfj%=URgj; color push BlackG color pop>ՠY[썍color push Black62ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popn썍 color push Black color pop%src:5691Cats.texfor*kevery*jsetT0andeverymaphUR:T]!A,,-suchthat*kfh=gX h,,,therffeis*jaunique%map35ko:URBXV!Eq#0(f;gn9)suchthatthediagrffamU}Eq (f;gn9)W_AT32fdPά-^bښj(BY@Rfd*ά- Ufyyfd*ά-  gbY|pT Ǘktׁ ֆt ̆t †t ?>?> H򋢟Ǡ*FfeԟǠ? qTh)S%src:5701Cats.texcffommutes,35i.e.fijW{ko=URh.Jcolor push BlackPrffoof. color pop#Rsrc:5706Cats.texWVef rsteshorwtheuniquenessofthemapko:URT!eEq$(f;gn9):?SuppSosethatj%:UREqk(f;gn9)!|A istheinclusionfunction:ujӹ(a)c =cafora2c Eq&(f;gn9).GGivrenT*andh.Ifkg;k20d:c T^!Eq2(f;gn9)FaremapssucrhFthatj\ko=URh=jkg20|/thenFforanryFtUR2T蟹weFhavekg(t)UR=:a2Eqk(f;gn9)andDkg205V(t)UR=:a20#2Eqk(f;gn9).ThenwregetDa=jӹ(a)=(j,WYkg)(t)=h(t)=(j-kg205V)(t)=jӹ(a209)=a20,hencekg(t)UR=a=h(t)=a20#=k205V(t)andko=URk205V.8Thisshorwstheuniquenessofthemapk.src:5710Cats.texExistence:FVromtheuniquenessproSofwreobtainareasonablede nitionofkg.*FVort2Twrede ne nkg(t)UR:=h(t).xThisisa omapfromT5toEq=(f;gn9)sinceh(t)satis esfG(h(t))UR=(f*h)(t)=(gh)(t)UR=gn9(h(t)).8ThenwregetjW{ko=URh.V%src:5715Cats.texObrviously4any3pair(E;)isomorphicto(Eq2(f;gn9);jӹ)3satis esthesameunivrersalpropSertyV.InfactgivrenanisomorphismiUR:E i"!xHEq#a(f;gn9)suchthatyEq(f;gn9) AIܞ32fdPά-^bZjbY XE\fiׁ ۍ|>ۍ|> H *Ǡ*Ffe \Ǡ?9")src:5724Cats.texcommrutes.rLetTRIbSeasetandh:TGai!AbSeamapsucrhthatfy\1^h=gh.rLetk 6:T!ZEq!'s(f;gn9)bSetheuniquemapthatsatis esjFkB=h.Thenthemapi21UFkB:T}!rEsatis esc;(i21 kg)UR=jD;ii21ko=URjDk=URh. Itciscaneasyexercisetoshorwthatthismapisunique Swiththis TpropSertryV.SotheunivrersalpropSertygiveninthetheorem Tsatis esthe rstpropSertryoftheextensionprinciple.TVode netheextensionofthepropSertryforarbitrarycategorieswreuseagainthespSecialdescriptionofequalizersinsetsasasubsetsofA.src:5730Cats.texInarbitrarycategorieswrecannotconstructanequalizeroftrwomorphismssincethereareno߁elemenrtsand߀wethuscannotconstructthe߀setofthoseelementsonwhich߀thetwomapscoincide.8Buttheextensionprinciple2.3.1(2)prorvidesthefollowingde nition.Jcolor push Black2.8.3.De nition. color popsrc:5733Cats.texLetAandB*bSeobjectsinacategoryCBCandf;gË:URAn!1B*bSemorphisms.AnobjectEqL(f;gn9)togetherwithamorphismsY:Eq(f;gn9)Ys/!Aiscalleda(cffategorical)effqualizer꨹off2andgn9,ifforallobjectsTninCݹthereisanisomorphismofsets 0i$iUR:MorOC(T;Eq2(f;gn9))P԰n:=Eq2(Mor5C(T;fG);Mor5C(T;gn9)) color push BlackG color pop?|Y[썍color push BlackEqualizers׊63G color popnsrc:5737Cats.tex(where Eq)"(Mor5C(T;fG);Mor5C(T;gn9))is theset-theoreticequalizerfrom2.8.1)sucrhthatthediagramE=poEq~ (Mor5C(T;fG);Mor5C(T;gn9))jMor$gC*l&(T;A)|32fd Pά- *BjHağ> HrǠ*FfeटǠ? $h3src:5765Cats.texcffommutes,35i.e.fiko=URh.color push BlackPrffoof. color pop#Rsrc:5769Cats.tex(=:!rLet!s(E;)bSeanequalizeroffirandgn9.@LetT9bSeanobjectinCԧandletkp2Mor5C(T;E). De ne]hչ:=Ck3:Tn &!TA. Then]fBhչ=fBk3=g|k3=ghand~thrus~MorC!(T;fG)(h)P=MorC۹(T;gn9)(h)~so~thathP2Eq8(Mor5C(T;fG);Mor5C(T;gn9)).Norw~wecan2de nei(kg):=h2Eq(Mor5C(T;fG);Mor5C(T;gn9))2andget2Morh۟C֚(T;)(kg)=k=h2Eq2(Mor5C(T;fG);Mor5C(T;gn9)).src:5772Cats.texItremainstoshorwthatiisbijective.8WVeconstructtheinversemapލQluUR:Eqk(Mor5C(T;fG);Mor5C(T;gn9))URn!1Mor).C/g(T;E)u(h)UR:=kߍsrc:5775Cats.texwhere0h2Eq(Mor5C(T;fG);Mor5C(T;gn9))0implies0MorfC԰(T;fG)(h)=MorCp(T;fG)(h). By0the0uni-vrersal{propSertyzoftheequalizerthereisauniqueko:URT!eLsucrhthatwxko=URh.WVeusethiskQŹforthede nitionofthemapu.src:5777Cats.texLet{hr2sEq+(Mor5C(T;fG);Mor5C(T;gn9)).YThen{(iRu)(h)r=i(kg)s=RRk`=hhence(iRu)r=1Eq DN(MorXX.C0!(TV;f);MorXX.C(T;gI{))b׹.src:5779Cats.texLetk2UMorݟC(T;E).9Then(ui)(kg)U=Uu(h)=u(kg)=k20 Qwherek205:UT0!gEistheuniquemorphismsucrhthatkg20=URkQŹhenceko=kg20and(ui)=1MorX6 C0!(TV;Er))ȹ.src:5781Cats.tex=):*IfMhO:T C![8AisamorphisminCǂsucrhthatNfMuOhO=guNh.Thenhisanelemenrtof Eq$(Mor5C(T;fG);Mor5C(T;gn9)),dsince MorCgǹ(T;fG)(h)W=MorTCk(T;gn9)(h). So there isauniquemorphism6ko:=URi21 \|(h)satisfying(j5bi)(kg)=horMor3C>(T;)(kg)=horbcko=h.dThrus(E;)isanequalizeroff2andgn9.Fvcolor push Black2.8.5.Prop`osition. color popsrc:5787Cats.texThe35familyofisomorphismsލcKiT i:URMorOC(T;Eq2(f;gn9))UR!Eq#C*(Mor5C(T;fG);Mor5C(T;gn9)) color push BlackG color pop@ Y[썍color push Black64ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popnsrc:5789Cats.texsuch35thatDOpoEq~ (Mor5C(T;fG);Mor5C(T;gn9))jMor$gC*l&(T;A)|32fd Pά- *BjH color popsrc:5803Cats.tex(1)ABInSet*$,c"anequalizerEXofthefunctions(x;yn9)UR7!x22+Py22o~andAA(x;y)7!1fromRRtoRisthecirclex22j+yn922=UR1.8Thearrorwj%:E i"!xHRRistheinclusion.src:5808Cats.tex(2)WGivrenXagraphG,DŽtheinclusionofthesetofloSopsinthegraphisanequalizerofthesourceandtargetfunctions.8ThisequalizerwillbSeemptryifthegraphhasnoloops.}:src:5813Cats.texAtheoremlikre2.7.6istrueofequalizersaswell.color push Black2.8.7.Prop`osition.Yo color popsrc:5817Cats.texIf/j,?:kE3!\Aandjӟ20x:lE20 h&!Aarffe0both/equalizersof0f;g:lAk!eDB,then35therffeisauniqueisomorphismiUR:E io!(E20for35whichjӟ20%iUR=j.color push BlackPrffoof. color pop#Rsrc:5823Cats.texWVetgivreutwoproSofs.ETheu rstusestheconceptofunivrersalelement.ELettCmbSethecategoryzmconrtainingtheequalizerszlgiven. /LetF.׹:C52op!#lSet<bSethezlfunctorforwhichF1(Cܞ)UR=fu:C1K{!Ajf9]:u=gs]9ug,htheGjsetofarrorwsfromC$whichGiequalizefiandgn9.vIfhUR:D!nC letoF1(h)(u)UR=uFh.(xThismakresnsense,GbSecauseifuUR2Fƹ(Cܞ),GthenfFuFhUR=gWFuh,souhUR2Fƹ(DS).src:5832Cats.texNotethatthismakresFasubfunctorofthecontravXarianthomfunctorMor (-;A).src:5835Cats.texThede nitionofanequalizeroffandg:canbSerestatedthiswray:anequalizeroffandgйisFanFelemenrtj2F1(E)forsomeobjectEsucrhthatforanryu2Fƹ(Cܞ)FthereisauniquearrorwEkWN:0CY!֋EsuchthatF1(kg)(jӹ)1=0u.IThismeansjxisauniversalEelementofF1,\dsobyPropSosition02.9.3,B%anrytwoequalizers0jyH2tFƹ(E)andjӟ20G2Fƹ(E20P)areisomorphic0bryauniquearrorwiUR:E i"!xHE20lsuchthatFƹ(i)(jӟ20{ )UR=jӹ.8Thatis,j%=URj20%i,asrequired.src:5845Cats.texHere*,is*-adirectproSofnotusingunivrersalelements:thefactthat*-fjӟ20<|=ogDjӟ209impliestheexistenceofauniquearrorwhUR:E20ע-!FEȹsucrhthatjӟ20^=j2_h.Thefactthatf1^j%=URgWjimpliestheexistenceofauniquearrorwh20#:URE i"!xHE20Csuchthatj%=URjӟ20 Th209.*ThenjThh20#=URjӟ20 h20=j%=URj[1E ^andtheuniquenesspartofthede nitionofequalizerimpliesthathh20#=UR1E-.BysymmetryV,h20xhUR=1Er؟0 O.T0src:5854Cats.texWVeaddsomemorepropSertiesofmonomorphismsandequalizers.color push Black2.8.8.Prop`osition.x' color popsrc:5857Cats.texLffet zj:ER!%Abe {anequalizer {ofthe zpairof zarrowsf;gT :AL;!2 B.ThenrjEisamonomorphism. Morffeover,Aanystworequalizersoff2qandgXbelongtothesamesubffobject35ofA.color push BlackPrffoof. color pop#Rsrc:5864Cats.texTVo see thatjH߹isamonomorphism,suppSoseh;ko:URC1K{!EP"withj h=j ko=lC.Thenfl=URfjQhko=URgjkN̹sothereisauniquearrorwmUR:C1K{!EƹwithjQhm=lC.7ButbSothh꨹andkQŹaresucrharrowsandsohUR=kg.src:5869Cats.texNorwgsuppSosehj:andjӟ20sareequalizersoffOfandgn9.InthenotationofPropSosition8.1.4,iandi21>are)the)arrorwsrequiredby)thede nitionofsubSobjectin3.3.12,ysincejӟ20itx=tyj֕andjW{i21ι=URjӟ20{ .ń color push BlackG color popA$ڠY[썍color push BlackEqualizers׊65G color popnsrc:5875Cats.tex8.1.6NMoreNgenerallyV,niff1;:::ʜ;fnDarearrorwsfromAtoB,nthenanobjectE togetherwithanarrorwmjSs:EZtB!Alisaneffqualizeroff1;:::ʜ;fn ¼ifithasthepropSertrythatanarbitraryarrorwhUR:C1K{!A꨹factorsuniquelythroughj{ifandonlyiff1jhUR=:::uD=fnRh.src:5882Cats.texHarvingequalizersofparallelpairsimplieshavingequalizersofall nitelists.0color push Black2.8.9.De nition. color popsrc:5886Cats.texAmonomorphisme:S]uw!!TinacategoryisrffegularŹifeisanequalizerofapairofarrorws.color push Black2.8.10.>@Prop`osition.i color popsrc:5891Cats.texA2nkZarrffowinacategorykYthatisbothanepimorphismkYandaregularmonomorphism35isanisomorphism.0color push BlackPrffoof. color pop#Rsrc:5896Cats.texLetf=:~?A! B4 bSebothanepimorphismandanequalizerofgn9;h~?:BD2!Cܞ.D5SincegD/f =hfrAand*CfrBisepi,:*g/ι=h.ThengD01B ӹ=h1B xso*Cthereisa*Bk(:B\v'!7Asucrhthatf_ko=UR1BN>.,Butthenf_kƝfQ=f=f_1A.,Butf ۹bSeingamonomorphismcanbecanceledfromthelefttoconcludethatkfQ=UR1A.color push Black2.8.11.Prop`osition. color popsrc:5904Cats.texEvery35monomorphisminSetOMisrffegular.color push BlackPrffoof. color pop#Rsrc:5908Cats.texAZmonomorphismɓinSet| isɔaninjectivrefunction(seeTheorem3.3.3),Nsoletf:A!nBtbSe0naninjectivrefunction.LetC bethesetof0mallpairsf(b;i)jbUR2B;i=0;1g0nandimpSosean1equivXalence1relationonthesepairsforcing(b;0)J=I(b;1)1ifandonlyifthereisanaI2JAwith|fG(a) =b(andnot}forcing(b;i)= (c;jӹ)}if|bandcaredistinct).]Sincef|isinjectivre,ifysucrhanaexists,thereisonlyone.Letgi:I0B7!FCVbygn9(b)I0=(b;0)yandhI0:B6!FCVbyh(b)%=&(b;1).KThen$!clearlygn9(b)=%h(b)ifandonly$"ifthereisana2&AwithfG(a)=&b.KNorwlet ko:URDk!B`withg]k=URh]kg.,WIt mrust bSethatforallxUR2DS,̑there isanaUR2A,̑andonlyone,5sucrhthatkg(x)j=fG(a).!fIfwreletlC(x)=a,5thenl :D ט!BAistheuniquearrorwwithfl=URkg.(color push Black2.8.12.Prop`osition. color popsrc:5925Cats.tex(1)35EverysplitmonomorphisminCjisarffegular35monomorphism.(2)35Everyrffegular35monomorphisminCjisamonomorphism.0color push BlackPrffoof. color pop#Rsrc:5930Cats.tex(1)JLetIf:A!=}BObSessplitmonomorphismwithleftinrverseJg1:B,F!؃A,2suchthatgafT = 1A.zWVeVclaimthat(A;fG)Visanequalizerof(f;gn9;1BN>).zWVeharveV(fGgn9)fT= f(gf) =fG1A <=X1BN>f./Norwh=h./Thenh=fG(gn9h)gn9;hC:AC!zBbe>a>pairof>morphismsthat>hasacffoequalizer>f:CBތD!Cܞ. If%〹(A;gn9;h)35isakernelpffairthenitisakernelpairoffG.acolor push BlackPrffoof. color pop#Rsrc:5965Cats.tex(1)Inthediagramf bA BέњњçğʹRfdpά-6ZϨ/hئyئyçğfdpά-g >Cğ:2fdά-df'iXՍPx؊4F`Ί4F`Ċ4F`  Π@fe<Π?Ս9uBΠ@feHtΠ?Սv YbǠ@fe”Ǡ?*ߌk >C+ y4?`4?`4?` src:5977Cats.texlet(C5;fG)bSethecoequalizerof(u;vn9).7Let(A;gn9;h)bSeakrernelpairoffG.7Thenthereisauniquemorphismxsucrhthatgn9xUR=u꨹andhxUR=v.src:5979Cats.texGivrenks:zVB\.!?Y3>withkgg萹=kh.=QThenku=kgn9x=khx=kvn9,sothatthereisauniqueyË:URC1K{!Ysucrhthatyn9fQ=kg.8Thrusf2isacoSequalizerofgXandh.src:5981Cats.tex(2)шLetч(A;gn9;h)bSeчakrernelpairofk8andlet(C5;fG)bSeacoSequalizerof(gn9;h).0ThenthereisauniquemorphismyXsucrhthatyn9fQ=URkg.src:5983Cats.texGivren,u;v3Ź:ŌXЙ!'BǝwithfGu=fvn9.Then,kgu=yfGu=ŋyfGv3Ź=kgv,=so,that,thereisauniquexUR:XF``!A꨹sucrhthatgn9xUR=u꨹andhxUR=v.8Thrus(A;g;h)isakrernelpairoffG.> src:5987Cats.tex0924.06.04acolor push Black2.8.16.I*Lemma.0C color popsrc:5990Cats.texf>/:/A0\!RB%isamonomorphismifandonlyif(A;1A;1A)isakernelpffairfor35fG.color push BlackPrffoof. color pop#Rsrc:5993Cats.tex"UTʍf2monomorphismUS()8u;vË:URT!eA:fGu=fvË=)u=vUS()8u;vË:URT!eA:fGu=fvË=)91ko:T!eA:1Ak=u;1Ak=vUS()(A;1A;1A)krernelpairoffG."kbcolor push Black2.8.17.Corollary. color popsrc:6003Cats.texIf35afunctorprffeserveskernelpairs,theitpreservesmonomorphisms.color push BlackPrffoof. color pop#Rsrc:6007Cats.texLetf_:aA`!4NB=bSeamonomorphism.^Then(A;A;1A)isakrernelpairforfG.^Thrus(Fƹ(A);1F.:(A) ;1F.:(A))isakrernelpairofFƹ(fG),henceF(fG)isamonomorphism.A5ԍ2.9.Universalelements.src:6012Cats.texsrc:6016Cats.texThere+is+asecondimpSortanrtway+ofde ningarepresenrtablefunctor.JWVewillshow+itsimpactwithanrumbSerofexamples.bcolor push Black2.9.1./&De nition." color popsrc:6019Cats.texLet/'F:C}!`Set-xbSeacorvXariant/'functor.[A/pair(A;x)withA2C5;x2F1(A)6iscalledauniversaly (ory!generic)objeffct6forF,IifforeacrhBq2CandyE2F1(B)thereexistsauniquefQ2URMorOC(A;B)sucrhthatF1(fG)(x)UR=yn9:IbYAn@B"Ǡ*Ffe2TǠ?`fHF1(A)4F1(B)bǠ*Ffe锟Ǡ?`AF((f)HC3URxc3URyǠ*FfeE4Ǡ?Ў feE4Ў? color push BlackG color popCVY[썍color push Black Univ9ersalTelements67G color popnsrc:6032Cats.texLetFc:URC"!wfSet,%7bSeaconrtravXariantfunctor.,MApair(A;x)withA2C5;x2F1(A)iscalleda(cffo-)universalH(or(co-)generic)objectOforF1,:ifforeacrhPB2}Candy2F1(B)therePexistsauniquefQ2URMorOC(B;A)sucrhthatF1(fG)(x)UR=yn9:Y^bYAn@B"Ǡ*Ffe2Tׁ 6`fHF1(A)4F1(B)bǠ*Ffe锟Ǡ?`AF((f)HC3URxc3URyǠ*FfeE4Ǡ?Ў feE4Ў?Tsrc:6046Cats.texThefollorwingpropSositionisavrersionoftheYVonedaLemmaandcouldalsobSederivredfromit.color push Black2.9.2.Prop`osition. E color popsrc:6049Cats.texFthasCauniversalelement(A;a)CifandonlyifFisrffepresentable,Hi.e.therffe35isanaturalisomorphism'UR:FPc԰K=1 Mor&g C+ȹ(A;)35(withaUR='(A)21 \|(1A)).color push BlackPrffoof. color pop#Rsrc:6055Cats.tex꨹=)N.:Themap"'_/'(B)UR:F1(B)3yË7!fQ2MorOC(A;B)with$F1(fG)(a)=ysrc:6056Cats.texisbijectivrewiththeinversemapzŏ n9(B)UR:MorOC(A;B)3fQ7!F1(fG)(a)2F(B):src:6060Cats.texInEfactwrehavey^7!f87!F1(fG)(a)=yandEf7!y^:=F1(fG)(a)7!gsucrhEthatF(gn9)(a)=ybut)then(F1(gn9)(a)UR=yË=F(fG)(a).&By)uniqueness(wregetfQ=URgn9.&Henceall'(B)arebijectivrewithinrversemap n9(B).8Itissucienttoshowthat Xisanaturaltransformation.src:6067Cats.texGivrengË:URBX !_7Cܞ.8Thenthefollowingdiagramcommutes] :MorCGϹ(A;Cܞ)"#F1(Cܞ)2Ԟ32fdBѐά-W` I{(C)HTMorQC&(A;B)H"cdF1(B)P{fdBpά-`\ I{(Bd)HǠ*Ffe3DǠ?`MorlX.C(A;gI{)H0nǠ*Ffe0ğǠ?`5TDF((gI{)(src:6071Cats.texsince n9(Cܞ)Mor5C(A;g)(fG)UR= n9(C)(gfG)UR=F1(gn9f)(a)=F1(gn9)F(f)(a)UR=F1(gn9) (B)(f):src:6074Cats.tex(:ܫLetܬAbSegivren. Leta:='(A)21 \|(1A). FVory82F1(B)wreܫgety8='(B)21 \|(fG)='(B)21 \|(fG1A)d='(B)21 \zMor"wC(6(A;fG)(1A)=F1(f)'(A)21 \|(1A)=F1(f)(a)PforOauniquelydeter-minedfQ2URMorOC(A;B).TPcolor push Black2.9.3.7Prop`osition.  color popsrc:6082Cats.texLffetHݹ(A;x)and(B;yn9)bffeuniversalelementsforF1.`Thenthereexistsaunique35isomorphismhUR:A!B;such35thatF1(h)(x)UR=yn9. color push BlackG color popDkY[썍color push Black68ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popn썍color push BlackPrffoof. color pop#Rsrc:6087Cats.texTheproSoffollorwsfromthefollowingcommutativediagramasintheproSofofTheorem2.7.6:Sٍq'ABjY *Ffe؜Y ?ohbYq'Aj`*Ffe؜`?<kHBjǠ*Ffe؜Ǡ?k|h b\gTu_`yR^:1X.A(꟮G feH\@s@sR*̟`0| ՠ01X.AIʟ G few| @|*@|*RR@F1(A)Q|F1(B)\Y *FfeܟY ?o5|F((h)HF1(A)\`*Ffeܟ`? ߿F((k6)HQ|F1(B)\Ǡ*FfeܟǠ?`|F((h)^b@ \gTu@_`1F(A) *G feH \ܟܟ =`0@ | @ՠ=_1F(BI)J G few | ** Ro?x+? yBJY *FfeB|Y ?BJ[ @ feB|[ @?HBJ`*FfeB|`?BJ׀ feB|׀??xj? yBJǠ*FfeB|Ǡ?BJЎ feB|Ў?kOcolor push Black2.9.4.;Examples. color popsrc:6118Cats.tex(1)Let2MsSetߑbe@󹬟>RHT_M:ڟǠ*Ffe Ǡ?` frdsrc:6126Cats.tex(2) [Givren \moSdulesMR andR NJ@(orvector \spacesMK EandK EN@).De neFnc:=RAbХ0!-'SetbryF1(A))k:=BilR3(M;N@;A).qThenF.isacorvXariantfunctor.qAdrepresentingobjectforFisgivrenbythetensorproSduct(M R GN; O:M۴N `!RM R HN@)withthepropSertrythat2forall1(A;f:NMrtN!A)thereexistsauniquegJ2NMor (Mr R h N;A)sucrhthatF1(gn9)( )UR=Bil.R"(M;N@;g)( )UR=g =fL%䍍{ȀMN{M R ;N0{fd Uά- H`޵ftׁ @t @t @t @@>@@>RHpA:F"Ǡ*FfeyTǠ?' +gresrc:6136Cats.tex(3)GivrenaK,`-moSduleVp.?xDe neF=߹: K-Alg@ Y!0ffSetH<#bryF1(A):= MorB(V;A).?xThenFisaxcorvXariantyfunctor.QABrepresentingobjectxforF특isgivrenbyxthetensoralgebra(Tƹ(Vp);s:V Ç!Tƹ(Vp))withthepropSertrythatforall(A;fU: V Ç!A)thereexistsauniqueg{2Mor5Alg"Β(Tƹ(Vp);A)sucrhthatF1(gn9)()UR=MorO(V;gn9)()=g=fJٍHbVHETƹ(Vp)V {fd!wЍά-H`:MfV ׁ @V @V @V @񜌟>@񜌟>RH˱A:Ǡ*FfeǠ?'lg color push BlackG color popE{РY[썍color push Black Univ9ersalTelements69G color popnsrc:6145Cats.tex(4)P`GivrenaPaK,`-moSduleVp.jDe neF3:vK-cAlg!n#!3SetJٹbryF1(A)u:=vMor8s(V;A).jThenPaFqisacorvXariantfunctor.ArepresentingobjectforFJisgivrenbythesymmetricalgebra(S׹(Vp);?:V X!S׹(Vp)) withthepropSertrythatforall(A;f`\:^V X!A)thereexistsauniqueg2Mor5cAlg&(S׹(Vp);A)sucrhthatF1(gn9)()UR=MorO(V;gn9)()=g=fKɍHďVHS׹(Vp)у${fd!ά-H`gefу$ׁ @ۃ$ @$ @$ @ɤ>@ɤ>RHA:ҟǠ*FfeǠ?'gSsrc:6154Cats.tex(5)GivrenaK,`-moSduleVp.8De neFc:URK-Alg!,oSetCbryTOxF1(A)UR:=ffQ2MorO(V;A)j8vn9;v 02URV¹:fG(v)f(v 0@ɤ>RHA:ҟǠ*FfeǠ?'g!src:6166Cats.tex(6)GivrenaK,`-moSduleVp.8De neFc:URK-Alg!,oSetCbryu>F1(A)UR:=ffQ2MorO(V;A)j8vË2V¹:fG(vn9) 2V=0g:src:6170Cats.texThenLF5]isacorvXariantLfunctor.AFrepresentingobjectforF5]isgivenbytheexterioralgebra(E(Vp);{:zVv!E(V))amwiththepropSertrythatalforall(A;fgz:zVv!A)suchthatfG(vn9)22~={0for֏allvË2URVrthereexistsauniqueg2URMorOAlg&#(E(Vp);A)sucrhthatF1(gn9)()UR=MorO(V;gn9)()=gn9UR=fE&H&VHE(Vp){fd ά- {H`-fׁ @ @ @ @`l>@`l>RHA:eǠ*Ffe̟Ǡ?'KLg!src:6178Cats.tex(7)_Let^KbSeacommrutativering.LetX72εSetbSe_aset.FŹ:δK,`-cAlg":$T]!5#SetH ,F1(A):=Map+Q(XJg;A)isacorvXariantfunctor. ArepresentingobjectforFisgivenbythepSolynomialringv(K,`[X];:Xj!LK[X])vwiththepropSertryV,*thatforall(A;f:Xj!LA)thereexistsauniquegË2URMorOcAlg)(K,`[X];A)sucrhthatF1(gn9)()UR=Map(XJg;gn9)(x)=g=fKȍH@̟>RHCA:Ǡ*FfeM,Ǡ?'gTsrc:6186Cats.tex(8)5Let6K"bSeacommrutativering.[LetX=2SetҹbSe6aset.FMʹ:K,`-AlgOi!0?SetCo",9F1(A):=Map+Q(XJg;A) is acorvXariantfunctor.!UArepresenting objectforFisgivrenby thenoncommuta-tivreNpSolynomialOring(K,`hXi;z,:Xk:!gKhXi)OwithNthepropSertryV,thatforall(A;f+:z+Xk:!hA) color push BlackG color popFY[썍color push Black70ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popn썹thereexistsauniquegË2URMorOAlg&#(K,`hXi;A)sucrhthatF1(gn9)()UR=Map(XJg;gn9)(x)=g=fJiHÈXHK,`hXiѰ<{fdά- {H`-fׁ @ @ @ @`l>@`l>RHA:eǠ*Ffe̟Ǡ?'KLgsrc:6194Cats.tex(9)(LetSϹbSe(aset.A(functionfb:bRc!RSiscalledofl|pfferiod21if(fG(x+2n9)b=cf(x)(forallx2R.De neQFٹ:SetVso!/&SetFbryPF1(S׹)=ffǹ:RS!Sjf2isofpSeriodB32n9g.ObrviouslyQFisUR 2nSן21ґ{fd)7ά-UwH`5f ׁ @ @ @ @Pt>@Pt>RHD8S :UǠ*FfeԟǠ?ƍ ;T]L\)f@src:6196Cats.tex(10)\yLetFbSeas\xin(9). SLetJ<:=fx2Rj0x<2n9g\yandt˹:RV!"JxbSe\ygivrenbyt(yn9):=xW()y;Rx=2n9nforsomen2Z.ўObrviouslytisafunctionofpSeriod2n9.FVoraUfunctionKffQ:URRn!1SRj⍒RJґ{fd+@ά- otH`5f ׁ @ @ @ @Pt>@Pt>RHD8S :UǠ*FfeԟǠ? ㎍ &a6cmex8er ;Tf4src:6198Cats.texByPropSosition2.9.3wreget(Sן21r;wR)PUR԰n:=(J:;t). uvsrc:6234Cats.tex0925.06.04uvcolor push Black2.9.5.&yProp`osition.E color popsrc:6237Cats.texLffetU~DbeaUcategory.EGivenaU~representablefunctorU~FX j:nC"!bSetfor@ effach@!X82GNDUV.+Givenanaturffaltransformation@!Fg L:GOFY v! EFX ]foreachg:GNX8=!Y(cffontravariant!)DsuchthatF+dependsfunctoriallyonX,Ri.e.DF1X.X6=UR1FX.X ;Fhg A=FgFhe.DThentherffepresentingobjects(AX;aX)forFX ydepffendfunctoriallyonX,i.e.GSforeachgË:URXF@!Ytherffe>is?auniquemorphismAg :AX mC!"AY (withFX(Ag)(aX)=Fg(AYP)(aY))?and>thefollowing\identities[holdA1X.X=1AX.X ;Ahg=AheAg.So\wegetacffovariantfunctorDQ&3Xfk!AX r2URC5.uvcolor push BlackPrffoof. color pop#Rsrc:6252Cats.texChoSoseg;arepresenrtingobjectg<(AX;aX)g;forFX ĹforeachXΞ2D(bytheaxiomofcrhoice).8ThenthereisauniquemorphismAg*P:URAX r f!AY ;ewithFX(Ag)(aX)UR=Fg(AYP)(aY)UR2FX(AYP);src:6255Cats.texforL2eacrhgË:URXF``!Y袹bSecauseFg(AYP):FY(AY)n!1FX(AY)L1isL2givren.WVehaveFX(A1)(aX)UR=F1(AX)(aX) =aX( =FX(1)(aX)NhenceMA1 ʅ= 1,andFX(Ahg )(aX)=Fhg (AZ8)(aZ)=Fg(AZ8)Fhe(AZ)(aZ)5=5Fg(AZ)FYP(Ahe)(aY)5=FX(Ah)Fg(AYP)(aY)5=5FX(Ah)FX(Ag)(aX)5=FX(AheAg)(aX)henceAhAg*P=URAhg forgË:XF``!Yandh:Y M!`ZFinDUV.\d color push BlackG color popG{Y[썍color push BlackTheTY:onedaLemma71G color popncolor push Black2.9.6.4Corollary.% color popsrc:6267Cats.tex(1)wMapm(XJg;M@)P԰=yMor&1vR-% (RJX;M@)wiswanaturffaltransformationwinM(andin35X!).fiInpffarticularSetqj3URXF7!RJX2RJ-L}MoSd!is35afunctor.src:6271Cats.tex(2)BilRtI(M;N@;A)P,԰E=Mor&(MA R _N;A)isanaturffaltransformationinA(andin(M;N@),2MoSd~-RRJ-L}MoSd\).fiIn35pffarticularMoSd-!GRRJ-L}MoSd! 3URM;N67!M r= N2Abވis35afunctor.src:6277Cats.tex(3)35RJ-L}MoSdZ-#S]S- MoSd d-$T3UR(M;N@)7!M SȊN62RJ-L}MoSdZ-Tis35afunctor.2.10.TheYonedaLemma.src:6283Cats.texsrc:6287Cats.texIfF:URC"!wfD@andG:C"!wfD@arefunctorsthenwredenotewithNat(FS;G)thesetofnaturaltransformationsfromFr̹toG.Actuallythisisanillegalset, itmarybSetoolarge.Inourapplications,@horwever,@it/will/bSeisomorphictoasetsothatwredon'truninrtoproblems.IfCLYis#a$smallcategorythentherearenoproblemseither,qsinceeacrhnaturaltransformationisafamilyofmorphismsindexedbryaset.color push Black2.10.1.gUTheorem.? color popsrc:6290Cats.tex(YoneffdaLemma)LetCYbeacategory.4GivenacovariantfunctorFZ:)Cfk!Set(and35anobjeffctAUR2C5.fiThen35themapepڌË:URNat(Mor5C(A;-33);F1)UR37!(A)(1A)2F(A)src:6295Cats.texis35bijeffctivewiththeinversemap{on9 1 :URF1(A)3a7!h aY!2Nat(Mor5C(A;-33);F);src:6298Cats.texwherffe35h2aϹ(B)(fG)UR=F1(f)(a).color push BlackPrffoof. color pop#Rsrc:6301Cats.texFVor @2@Nat(Mor5C(A;-);F1)wrehave amap(A)@:@MorvCĹ(A;A)@Y!F1(A),Shencewith,n9()UR:=(A)(1A)isawrellde nedmap.7 FVorn921wehavetocheckthath2aisanaturaltransformation.8GivrenfQ:URBX !_7CFinC5.ThenthediagramMHyrF1(B)F1(Cܞ)l32fdRά-W`/zF((f)H4Mor61C(A;B)HrMoroC#4.(A;Cܞ)ğ{fd3QPά-`ؕ!Mor(A;f)H}Ǡ*Ffe$Ǡ?`!^h-:a(Bd)H$rǠ*Ffe%Ǡ?`)$h-:a(C);src:6310Cats.texis!$commrutative. SIn!#factifg2MorOC!F(A;B)thenh2aϹ(Cܞ)Mor5C(A;fG)(gn9)=h2a(Cܞ)(fgn9)=F1(fGgn9)(a)UR=F(fG)F(gn9)(a)=F(fG)h2aϹ(B)(gn9).8Thrus21]iswrellde ned.src:6315Cats.texLetin921 ʵ(a)-Z=-[h2aϹ.Thenn921(a)-Z=-[h2aϹ(A)(1A)=F1(1A)(a)=a.Letin9()=(A)(1A)-Z=a.ThenIn921 ʵn9()=h2a MŹandh2aϹ(B)(fG)=F1(f)(a)=F1(f)((A)(1A))=(B)Mor5C(A;f)(1A)=(B)(fG),henceh2aY!=UR.Tcolor push Black2.10.2.Corollary. color popsrc:6323Cats.texGiven35A;BX2URC5.fiThenthefollowingholdsrc:6325Cats.tex(1)35Mori2C(A;B)UR3fQ7!MorOC(f;-33)2Nat(Mor5C(B;-33);Mor5C(A;-))35isabijeffctivemap.src:6328Cats.tex(2)Underthebijeffctivemapfrom(1)theisomorphismsinMor C(A;B)cfforrespondtonaturffalisomorphisms35inNats(Mor5C(B;-33);Mor5C(A;-)).src:6332Cats.tex(3)35Forcffontravariant35functorsFc:URCn!FSet,^wehaveNats(Mor5C(-;A);F1)P԰n:=F(A).src:6335Cats.tex(4)(Mor%C 4(A;B)]3\f%[7!MorYC (-35;fG)2]Nat(Mor5C(-35;A);Mor5C(-;B))(isabijeffctive)mapthatde nes),aone-to-onecfforrespondence),betweentheisomorphismsinMor_)C(A;B)andthenaturalisomorphisms35inNats(Mor5C(-;A);Mor5C(-35;B)).color push BlackPrffoof. color pop#Rsrc:6343Cats.tex(1)follorwsfromtheYVonedaLemmawithFc=URMorOC(A;-).src:6346Cats.tex(2)|{Observrethat||h2fw(Cܞ)(gn9)M=MorCD(A;g)(fG)=Mgf=MorCD(f;Cܞ)(g)|{hence||h2f ħ=MorCD(f;-).SincecwrehaveMorT`C(f;-)Mor5C(gn9;-)`=_Mor\CQ(gf;-)candMorT`C(f;-)_=`id xMorЛ6 C!%(A;-)9ifandonlyiffQ=UR1A Ȍwregettheone-to-onecorrespSondencebetrweentheisomorphismsfrom(1). color push BlackG color popHY[썍color push Black72ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popnsrc:6353Cats.tex(3)and(4)follorwbydualizing.+tcolor push Black2.10.3.+Remark.  color popsrc:6357Cats.texThemaprcisanatural*transformationintheargumenrtsAandF1.hMoreprecisely:8iffQ:URAn!1Band:Fc!BGֹaregivrenthenthefollowingdiagramscommuteM~xNatJ(Mor5C(A;-);G.)#4vG.(A)=32fd ά-7HNatʐ(Mor5C(A;-);F1)H"8F1(A)L<{fdmά-7HJǠ*Ffe(|Ǡ?`UNaty(MorX(A;-);)H/JǠ*Ffe0|Ǡ?`4(A)U(Nat1(Mor5C(B;-);F1)6F1(B):jL32fdά-ާHMǹNatp(Mor5C(A;-);F1)H!F1(A){fdmά-Hѹ*Ǡ*Ffe\Ǡ?`*NatN(MorX(fh;-);F()H/*Ǡ*Ffe/\Ǡ?`4F((f)src:6366Cats.texThiscanbSeeasilycrhecked.8Indeedwehavefor Ë:URMorOC(A;-)URn!1Ft"M!n7Nat(Mor5C(A;-);)( n9)UR=( )=( )(A)(1A)=(A) (A)(1A)=(A)( )tsrc:6370Cats.texandtʍ"|n7Nat(Mor5C(f;-);F1)( n9)UR=( n7Mor4C(f;-))=( n7Mor4C(f;-))(B)(1BN>)= n9(B)(fG)"|=UR n9(B)Mor5C(A;fG)(1A)=F1(f) n9(A)(1A)=F1(f)n9( ):ɍcolor push Black2.10.4.-kRemark.o color popsrc:6381Cats.texBythepreviouscorollary-jtherepresenrtingobjectAisuniquelydetermineduptoisomorphismbrytheisomorphismclassofthefunctorMor Cd(A;-).color push Black2.10.5.iProp`osition.@ color popsrc:6387Cats.texLffetG:-Ck6D w!.Set. beacovariantbifunctorsuchthatthefunctorG.(C5;-33)r}:r~D.>!Set,̖isBrffepresentableforBallCO2r~C5.ThenthereBexistsacffontravariantfunctorF5:C,!"D+suchthatGP԰Ӣ=Mor'JD.(F1-dF;-33)holds.IFurthermorffeFisuniquelydeterminedbyGup35toisomorphism.color push BlackPrffoof. color pop#Rsrc:6396Cats.texFVor6eacrh6Cg2C*choSosean6objectF1(Cܞ)2DKandan6isomorphismC :G.(C5;-)P԰׹=Mor5D`(F1(Cܞ);-).Givrenf:C;!hOC20finCn޹thenletF1(fG):F(Cܞ20׹)Ҝ!F(Cܞ)bSetheuniquelydeterminedmorphism(brytheYVonedaLemma)inD?suchthatthediagramQ􍍍/G.(Cܞ20;-)Mor4D`(F1(Cܞ20׹);-)ƈL32fdpά-ΧLCjPG0HG.(C5;-)HfMorD}(F1(Cܞ);-)l{fd ά-iX.CHǠ*FfeLǠ?`eGv(fh;-)H Ǡ*Ffe LǠ?`Mor!c(F((f);-)src:6404Cats.texcommrutes.BBecauseoftheuniquenessofF1(fG)andbSecauseofthefunctorialityofG6itiseasy)toseethatF1(fGgn9)z=F(gn9)F(fG))andF(1C)z=1F((C)uhold)and*thatFJ:isaconrtravXariantfunctor.src:6409Cats.texIfOF120:iC(!ϓDisOgivrenwithGP԰=WMor'DTD.(F120J-;-)then:Mor7fD ɹ(F1-;-)Ph԰P=X(Mor&%D-݈(F120J-;-).h/Hencebry3Lthe3MYVonedaLemma n9(Cܞ):F1(C)P԰߹=EF120J(C)3Mis3LanisomorphismforallC2C5.Withtheseisomorphismsinducedbrythediagram color push BlackG color popIשY[썍color push BlackTheTY:onedaLemma73G color popnsrc:6415Cats.texF eMor{'DwU(F120J(Cܞ20׹);-)$=Mor9s D@p(F1(Cܞ20׹);-)32fde ά-knMorFu( I{(C-:0B});-)HgYMor|Dq(F120J(Cܞ);-)H%-Mor:*DB)(F1(Cܞ);-){fdhά-`FMorY( I{(C);-)H*Ǡ*FfeH\Ǡ?nX6Morg(F(-:0~(f);-)HI*Ǡ*FfeJ,\Ǡ?`NMor^7s(F((f);-)src:6424Cats.texcommrutes.8HencethediagramMHyF1(Cܞ)^F120J(Cܞ)ڜ32fd!ά-W` I{(C)H{F1(Cܞ20׹)HBF120J(Cܞ20׹){fdά-n4 I{(C-:0B})HjǠ*FfeǠ?n)F(-:0~(f)HAǠ*FfeuǠ?`'F((f){src:6428Cats.texcommrutes.8Thus Ë:URFc!BF120isanaturalisomorphism.e܊color push Black2.10.6.^Remark.;- color popsrc:6433Cats.texThe^YVonedaLemmasarysinprinciplethatwe^canrecover(allpropSertiesof8)WanobjectWAfromtheconrtravXariantWfunctorMorߟC(-;A).Corollary2.10.2sarysthatwrecanalsohrecorvergamorphismfffromthenaturaltransformationMordCF#(-;fG).`MoreimpSortanrtlyanrydnaturaltransformation'%u:%vMor[sC2(-;A)?!dwMor+tC13(-;B)disoftheform'%v=%uMor[rC1(-;fG)forsomefQ:URAn!1B.8SowregetthefollowingTheorem.܉color push Black2.10.7.:TheoremTH(TheYonedaTGEmb`edding). color popsrc:6437Cats.texLffetC] bea(small)cffategory. JThenthefunctorh2:1Cg!Func3lx(C52op R;Set)withh(A)=1Mor1.C(-35;A)andh(fG)1=Mor1/C(-35;f)isfullandfaithful.fiIn35pffarticularCjisequivalenttoafullsubcategoryofFunc (C52op R;Set).color push Black2.10.8.Theorem(Caryley). color popsrc:6440Cats.texEvery35grffoupGisisomorphictoagroupofpermutations.܉color push BlackSketch35ofPrffoof. color popVsrc:6443Cats.tex1. First,de ne theCaryleyrepresentation \-z D ӍGofG tobSethefollorwinggroupofpSermrutations:theSunderlyingSsetof\-z D ӍG극isjustG,mandforeacrhgu/2G,mweShavetheSpSermutationdzKg a,mde nedforallhUR2G꨹bry:8dzKg Gp(h)=gh:NorwcheckthatdzKg N=UR: zÊ himpliesgË=URh.2.8Nextde nehomomorphismsiUR:Gn!1\-z D ӍG!bryi(gn9)=dzKg c,andj%:\-z D ӍGP!!^/Gbryjӹ(dzKg)=gn9.3.8Finallyshorwthatij%=UR11\)G @andjW{i=1G.Gcolor push Black2.10.9.Remark.0 color popsrc:6455Cats.texWVarning:Notethetrwodi erentlevelsofisomorphismsthatoSccurintheproSofofCaryley'stheorem.cTherearepermrutationsofthesetofelementsofG,whichareisomorphisms&inSet ,andthereis%theisomorphismbSetrween&Gand\-z D ӍG ѹ,whicrhisinthecategoryGroups꨹ofgroupsandgrouphomomorphisms.src:6460Cats.texCaryley's+theoremsaysthatanyabstractgroupcan+bSerepresentedasa\concrete"one,;i.e.apgrouppofpSermrutationsofaset.NThetheoremcanbSegeneralizedtoshorwthatanrycategorycanbSerepresenrtedasonethatis\concrete",i.e.8acategoryofsetsandfunctions.܉color push Black2.10.10.rTheorem. color popsrc:6465Cats.texEvery cffategoryCis isomorphictooneinwhichtheobjeffctsaresetsandthe35arrffowsarefunctions.fi(OneshouldreallyrequireherethatCjissmall.)color push BlackSketch35ofPrffoof. color popVsrc:6469Cats.tex ¹De nethe CaryleyrepresentationofCtobSethefollowing concretecategory:s2 color push Black color pop%src:6473Cats.texobjectsaresetsoftheform:eI\-z D ӍCGF=URffQ2C5jcoSd(fG)=Cܞg%src:6475Cats.texforallC12URC5, color push BlackG color popJY[썍color push Black74ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popn썍 color push Black color pop%src:6476Cats.texarrorwsarefunctionsW1dzKg֕n:UR\-z D ӍCO!!^.\-z  ӍD+s5;Í%src:6478Cats.texforgË:URC1K{!D>6inC5,de nedbrydzKg 8(fG)=gf.src:6480Cats.texk!2.11.AlgebraicStructures.src:6485Cats.texsrc:6489Cats.texAlgebraic`astructures``arede nedbryopSerations,}i.e. by``composition`amapsfromproSductsofa#settothesetitself,1togetherwithadditionalequations.TheseopSerationsleadtonaturaltransformations.8Againmonoidsarethe rstinrterestingexample.src:6495Cats.texWVeconsiderthecategoryMon$uBofmonoidsandtheunderlyingfunctorU:5Mon$d&~/!7)fSetJI.Firstwretranslatethede nitionofamonoidintoacategorytheoreticalversion.Rcolor push Black2.11.1.,De nition.x color popsrc:6501Cats.texLetCbSea,categorywith niteproducts.!A,kmonoidinCisatriple(M;mrult|;eM )where color push Black|(1) color pop%src:6504Cats.texM+isanobjectinC5, color push Black|(2) color pop%src:6505Cats.texmrult(:URMM6!M+isamorphisminC5, color push Black|(3) color pop%src:6506Cats.texeM B:UR1n!1M+isamorphisminCݹwith1aterminalobject.src:6509Cats.texsucrhthatthefollowingdiagramscommute:DiԠiMMMԠMM:2fd-6ά-MmrultMM%cMaT32fdHά-:mrultϲǠ@feǠ?.*mrult\#M+Ǡ@fe+$Ǡ?*0emrult=src:6517Cats.texand=ЍԠP԰=MP6԰=@M1Ԡ9MML:2fd5npά-򷍒+1M .eMz.MMGDMܞ32fd ά-:g-mrultԠ٥1M;:Ǡ@fenlǠ?zkJeM .1MM`Ǡ@feM,Ǡ?*RFmrultzタ1M,ۿ`X,?`X,`X,?`X,`X,?`X,`X,?`X,`X$,?`X.,`X8,?`X:/,X:/,zRsrc:6529Cats.texWVeBnoteBthattheunitelemenrtisreplacedbryavXariableelemenrteM B:UR1n!1A.IntheBcategorySetofsetsaterminalobjectisaone-pSoinrtset(orsingleton).!XAnelemenrtinmUR2Mde nesa[Iunique[JmapmM :1.!CM@,wrin[IfactM-andM@(1)areisomorphicsets.IncaseoftheunitelemenrtBmUR=ethisleadstoeM B:fgn!1M$'witheM ()=e2M@.6hSoinCthecaseofsetsthismapmakresthelastdiagramcommutative.src:6539Cats.tex0901.07.04src:6541Cats.texTheconditionsfora(homo-)morphismofmonoidsfp:xrMU!KTN֕translatetocommrutativediagramsCꍍ(15)ԠfMMԠM5e:2fd%Wά-μ:mrulth NNNTe32fd()`ά-:VmrultzßǠ@fezǠ?냀YTffCǠ@feLuǠ?냀fuMand >1 jTlMH Q:2fd`ά-ߍPyeM>1kONH Q32fdά-ߍQ5eNAwǠ@feAǠ?&11V=URfG20ppǠ@fepǠ?냀uVaf=src:6558Cats.texIttisteasytoseethatthecompSositionofmorphismsofmonoidsisagainamorphismofmonoids.Onealsohasthattheidenrtitymorphism1M ͹inCMisamorphismofmonoidsforallmonoids(M;mrult|;eM )inC5.src:6563Cats.texSowrecande nethecffategory35ofmonoidsMonC(QIinanarbitrarycategoryC5. color push BlackG color popKY[썍color push BlackRPAlgebraicTStructuresT75G color popnsrc:6573Cats.texAllotheralgebraicstructuresaslongastheyarede nedbryopSerationsandequations(effqua-tionallyMde neffdalgebraicstructures)KcanJbSetreatedinthesamewrayV.ExamplesKabound:semigroups,groups,abSelianCgroups,rings,vrectorspacesoveraB(set-theoretic) eldK,K-algebras,RJ-moSdules,Liealgebras,Jordanalgebras,semirings,etc.src:6581Cats.texAneasyexampleofanalgebraicstructureisthecaseofunaryopSerationsu:SJ!3SZasdiscussedPinO1.7.21.TheseopSerationsplaryanimpSortanrtroleinthestudyofendomorphismsofvrectorspaces,i.e.8ofsquarematrices.color push Black2.11.2.Remark(VVectorspaces). color popsrc:6587Cats.texThecaseofK-vrectorspacesandRJ-moSdulescontainsaninterestingvXariant. @SinceKwillnotbSeanobjectinCingeneralthequestionariseshorwtode netheactionofKonvrectorspaces.;uThisisdonebryconsideringeacrhelement jX2VKasanendomorphismforthevrectorspace objectVxinC5,soeacrh 2tKinduces :sV9So!VyinC5.TherelevXanrtequationsforavrector5space4arethenwrittenasequationsofmorphisms.6FVorthispurpSosewre rstconsiderthestructureofanabSeliangrouponVp.color push Black2.11.3.EUDe nition..N color popsrc:6600Cats.texLetCbSeacategorywith niteproducts.HAE>grffoupinacategoryEUCisaquadruple(V;+;0;)where΍ color push Black|(1) color pop%src:6603Cats.texVisanobjectinC5, color push Black|(2) color pop%src:6604Cats.tex+UR:VGV M!`Visamorphism,theaddition, color push Black|(3) color pop%src:6606Cats.tex0UR:1n!1Visamorphism,theneutrffal35elements, color push Black|(4) color pop%src:6608Cats.texUR:V M!`Visamorphism,theinverse,ύsrc:6610Cats.texsucrhthat>JYԠVGVVԠVGVt:2fd)Vά-Ͳ鍒ZVG+VGVAV32fdAhЍά- 9Pݰ+FǠ@feyDǠ?+V$8Ǡ@fe$kDǠ?냀)Ĺ+MDԠPS԰;=VP԰ =kVG1Ԡ9#VGV:2fd;ά-򷍒c1V p0wcVGVEyV32fdά-ư+ԠBh1VǠ@feBǠ?zsչ01VJ5JǠ@feJh|Ǡ?냀O+z1V|ۿ`X|?`X|`X|?`X|`X|?`X|`X |?`X|`X |?`X*|`X4|?`X7|X7|zJ򵍍 RV K1_zf:2fd K0ά-˰jKhi K1 yVv:2fd K0ά-ɝ0FvVGVhVGVk֞32fd5P`ά- 7s1V pWԟǠ@feWBǠ?냀,W\[/1VV;1V]ԟǠ@fe4?`6냀憹+iand 5V f$1Bׂ:2fd K0ά-˰NCghi f$1 Vp :2fd K0ά-ɝ}4$0)VGVVGVN32fd5P`ά- 7V1V:kǠ@fe:"Ǡ?냀x[1VV;1V]]Ǡ@fe"?`6냀C+Usrc:6644Cats.texAgroupiscalledabffelianorcommutativeifinadditionthefollorwingdiagramcommutesHWԠKVGVԠ KVGV8t:2fd5P`ά-˰U[ݙ.p2;p1]%V냀+ ?`@ ?`@ ?`@بD@بDR냀 +D?`D?`D?` src:6652Cats.texwhere[.4p2;p1] 8istheswitcrhmorphismof2.7.13. color push BlackG color popLΠY[썍color push Black76ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popnsrc:6656Cats.texThis de nitionallorws ustode negroupsinmanrycategories.ExamplesaregroupsinTVop,called8:topffologicalegroups,groupsinthecategory89ofanalyticalmanifolds,calledanalyticffalgrffoups,groupsinthedualcategoryofthecategoryofcommrutativealgebras,calledcffommu-tativeIFHopfalgebrffas.WVedenotethecategoryofgroupsresp.abSeliangroupsinC߹bryGr̔Cresp.8AbC5.Zcolor push Black2.11.4.]!Lemma.:t color popsrc:6666Cats.texLffetmV=*(V;+;0;)bffeanA2beliangroupinC5.ThenMorjAb&SC2^(V;Vp)isaring35withunit.color push BlackPrffoof. color pop#Rsrc:6671Cats.texTheadditionisgivrenbyvf+gË:=UR(VC[1X.Vn;1X.V]_  !%PVGVh%fgJ G!oVV2 N4+p G!oVp):ۍsrc:6675Cats.texThemorphism[1VV;1V]isusuallyabbreviatedbry.Itmakesthefollowingdiagramcom-mrutative::ԠnVԠPVGVb<:2fdAhЍά-9"J^VGV@-VGVVz32fd)Vά- {O1V pǠ@fe)ܟǠ? 誟Ǡ@fe ܟǠ?붳\1V|src:6684Cats.texi.e.8itiscffoassociative.Then,ۍʍVڮ(f+gn9)+hԧ=UR+((f+gn9)h)ԧ=UR+((+(fgn9))h)ԧ=UR+(+1VVȹ)(fgh)(1V)ԧ=UR+(1V p+)(fgh)(1V)ԧ=URf+(g+h):5tmsrc:6696Cats.texSince@Wwre@Vwillproveamore@Vgeneralresultin???wreleave@Wittothereadertocrheckthat@WVC N4hi_ G!aX12 0pUR !V\5istheneutralelemenrtfortheadditiononMorŸAb%w:C1q(V;Vp)andthatVh fJ G!oV2 N4p G!VistheadditivreinverseoffG.src:6704Cats.texThe[mrultiplication[onMorAb&oC2(V;Vp)isde nedtobSethecompSositionofmorphisms,xPsoitisassoSciativrewithunitelement.src:6708Cats.texThemrultiplicationisdistributivesince'.ʍf(g+h)gd=URf+(gh)gd=UR+(ffG)(gh)gd=UR+((fgn9)(fh))gd=UR(fgn9)+(fh);'/src:6717Cats.texbrythefactthatf2isamorphismofabSeliangroups,andʍo(f+gn9)h)=UR+(fgn9)hչ=UR+(fgn9)(hh)=UR+((fh)(gh))=UR(fh)+(gh);src:6725Cats.texbryaneasypropSertyof.Gx src:6728Cats.texSoaK-vrectorspaceinCݹcanbSede nedasfollows:Zcolor push Black2.11.5.6De nition.u color popsrc:6731Cats.texLetKbSea eld.A5veffctor,space6inacategory6C:with niteproductscon-sists$HofanabSeliangroupV2URC|togetherwitharinghomomorphism:Kn!1Mor).Ab6{CBݹ(V;Vp). color push BlackG color popM+Y[썍color push BlackRPAlgebraicTStructuresT77G color popnsrc:6737Cats.texSo]Qwre]PgetaunaryopSerationforeacrhelement]P , 2{K.ThisexampleshorwsthattheremarybSein nitelymanrydi erentopSerationsonanalgebraicstructureinC5.src:6741Cats.texThere:/isanotherpSoinrtofviewthatproduces:0manrynaturaltransformations.'uAgainweusetheGbexampleofmonoids.OObservre rstthatthereisanunderlyingfunctorU4 :'MonaC(bG*{!:nClikreinthecaseofsetsandordinarymonoids.8Thenthediagrams15canbSerewrittenasDL3H/U@(M)U@(M)U@(M):2fd!;ά-μ:mrultJɃU@(N)U@(N)JU@(N)32fd$+@ά-:"ϹmrultnǠ@feo'Ǡ?냀(U@(fG)U(fG)挟Ǡ@feǠ?냀>U@(fG)Vand\1CU@(M)f?Z:2fdά-ߍieM\1>vU@(N)f?Z32fdά-ߍjeN_Ǡ@fe_Ǡ?&4֓11V=URfG20Ǡ@feǠ?냀ujU@(fG)src:6762Cats.texThese׊diagrams׉commruteforany׉choiceofmonoid׉morphismfQ:URM6!N@.2Theyshorwthatmrult and7iearenaturaltransformations.$mrult"* isanaturaltransformationfromthefunctorUoU6:URMoncC'&)@(!8|CtotheunderlyingfunctorU:URMoncC'&)@(!8|C5.ItiseasythecrheckthatUoUis-afunctorinone.vXariable.oTheinrterpretationoftheseconddiagramisabitmoresubtle.As rstfunctorwreusetheonepSoinrtfunctorEU:MonC')7!9{CԹwithE((M;mrult|;e)):=1foranrymonoidinCLandE(fG) :=11,rtheidentityV.,Thenitisclearthate :1!CMPde nesalsoanaturaltransformationeUR:E i"!xHU@.src:6775Cats.texAgain"manryopSerationofanyequationallyde ned"nalgebraicstructurecanbSeconsideredasanaturaltransformation.src:6778Cats.texWVeclosethissectionwithatheoremthatleadsusbacrktotheextensionprinciple.qcolor push Black2.11.6.Theorem.M color popsrc:6782Cats.texLffetCCbeCacategorywith niteCproducts.nA2nobjectCGinCisagrffoupifandonlyifthecffontravariantfunctorMorC|(-35;G)G:C;|!*/Set/ cffanbefactoredthroughthecffategoryeofgrffoups,ri.e.LthereeiseacffontravariantefunctorGiB:CfI̴!ɹGr(frffomC tothecffategoryGr!of35grffoupssuchthatMori2C(-;G)UR=UG.,35whereU6:URGrt!&0OSet=Lgistheunderlyingfunctor.q src:6785Cats.texThe;construction:givreninthefollorwingproSofwillshorwmore,=namelythatthereisabijectionbSetrweenthegroupstructuresonGandthedi erenrtpossiblefactorizationsG..src:6787Cats.texThestatemenrtoftheTheoremalsoholdsforanryotherequationallyde nedalgebraicstruc-tures.src:6789Cats.texA#givren$ factorizationG7of$ MorZCƹ(-;G)canalsobSe$ viewedasagroupstructure$ forG,Ksoweseeanother^exampleoftheextensionprinciple. 8ThisvXarianrt^ofade nitionforagroupstructurecan@also?bSegivrenwithoutany? niteproSducts,&sothatitisinfactmoregeneralthanthede nition,wrehavegivenforagroupinacategoryV.׍color push BlackPrffoof. color pop#Rsrc:6792Cats.texThe@YVoneda@Lemmade nesabijectionbSetrween@thesetofmorphismsfQ:URXF``!YandthesetofnaturaltransformationsfG(-)I:X(-)!hYp(-)bryfG(Zܞ)H=MorFCK(Z5;f).WInparticularwrehavemX r۹=URMorOC(XJg;m)UR=m(X).8ThediagramPH(G(-)G(-)G(-)H WG(-)G(-){fd ά-ʍmi?-j1DG(-)G(-)FG(-)m32fd9Ѝά-YXmi?-HBǠ*FfeOtǠ? 1mi?-H(̂Ǡ*Ffe(Ǡ?(-4mi?-insrc:6805Cats.texcommrutes?ifandonlyif?MoruߟC㞹(-;m(m䯹1))d=eMorbC!(-;m)(Mor5C(-;m)1)e=dm̹-j(m̹-OW䰹1)=m̹-j(1`m̹-)=Mor*CY(-;m)(1`Mor ]C(-;m))=Mor*CZ(-;m(1_`m))H>ifandonlyifm(m1)= color push BlackG color popN<ѠY[썍color push Black78ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popnm(1m)ifandonlyifthediagramKYkGGGY~GG${fdQά-)-dm1 GGv>GĞ32fd*Fά-ÍmHoǠ*FfeͣǠ?͝T1mHbǠ*FfeǠ?]CmzՍsrc:6817Cats.texcommrutes.8InasimilarwayoneshowstheequivXalenceoftheotherdiagram(s).5 src:6822Cats.tex0902.07.04v color push Black2.11.7.YRemark. color popsrc:6825Cats.texLetCbSeaXcategorywith niteproSducts.1qARmorphismfQ:URGn!1G20inCisahomomorphismofgroupsifandonlyifHY¬GGY ZGZğ{fd@ά-܂mKG20xG20KG20,D32fdNά-.7m-:0HǠ*FfeFǠ?`ffH "Ǡ*Ffe TǠ?`fesrc:6834Cats.texcommrutes.vcolor push Black2.11.8.De nition. color popsrc:6838Cats.texAcffogroup(comonoid)GinC.isagroup(monoid)inC52op R,Ni.e.inacategoryC5.SoonecaninrtroSducevectorK>spacesandcorvectorK=spaces,monoidsandcomonoids,ringsandcoringsinacategoryC5.&ThestructurescanbSedescribedbrymorphismsinCݹifCisacategorywith nite(co-)proSducts. ;color push Black2.11.11.Prop`osition.Q color popsrc:6918Cats.texLffet;Ge2eCypbeagroupalsobSe>described>asageneralizationofasettheoreticconstructionwiththeextensionprinciple.WVeݒwill,Mhorwever,useݒtheshortݓwrayݒandgivreadirectde nitionandcorverݒtherelationtolimitsonsetsbryanextrapropSosition. <color push Black2.12.1.De nition.> color popsrc:6958Cats.tex(1)Let DDdbSea(shape)graph andF:\D$˯!(CBbea diagram.FA limitorprffojective35limit꨹ofFnconsistsof{F color push Black color pop%src:6960Cats.texanobjectlim c⡎ItisindeedaspSecialcaseofthe0uniquenessofa0univrersalelement(PropSosition2.9.3). The0connectionwithauniversalelemenrtwillbSegivenbythenexttheorem.ōcolor push Black2.12.3.Examples. color popsrc:7002Cats.tex(1)LetDQbSeanemptrygraph.kThenalimitofadiagramconsistsofanobjectTE,ofsucrhthatforeachobjectTthereisTauniquemorphismgxK: Tc!wE.wtThisisthede nitionofaterminalobjectE.src:7004Cats.tex(2)cLetDbSecasetoftrwocverticeswithoutcanyedges. ThenadiagramcconsistsoftwoobjectsAҹandB.(_AlimitconsistsofanobjectAB*عandtrwomorphismspA LW:ntAB y#!zB*عandpB :URABX !_7B.GThe%univrersalpropSertysaysthatforeachobjectTǣandanytwomorphismsfA 36:URT!eAandĀfB :T!A\B_thereisaĀuniquemorphism(f;gn9)UR:T!A\B_sucrhthatpA (fA;fBN>)=fA (zandJpB :7(fA;fBN>)=fB.XSoJthisgivresJthede nitionofaproSductoftrwoobjects.src:7006Cats.texIfDRݹhasanarbitrarysetI ofverticesandanemptysetofedges,>thenalimitofF7:upDR!YCistheproSductQ?i2IAiOwithAi,:=URFƹ(i).src:7008Cats.tex0908.07.04Msrc:7010Cats.tex(3)LetD?consistoftrwovertices1andtwoandtwoedgesݍϰ1ݍ2:WW,Rfd Pά-/̍Iicc,fd Pά- "*jZSsrc:7016Cats.texThenalimitofadiagram-ϗAkB,soitisuniquelydetermined.`Thetriple(AC YB;pA;pBN>)satis estheforwwlowinguniversalpropSertryV.GivenyanyobjectTminC,ܹandtrwomorphismsyqA &:HT~ !LAandqB :HT~ !BsucrhthatAf12qA 36=URgk3qB )(againwreneednot@givethethirdmorphismqC t=URf22qA 36=gkqBN>)AthenthereisauniquemorphismqË:URT!eAC @BsucrhthatjZBuNCW32fdPά-gۍgrǠ@feǠ?냀$f:3 AC @B:3/A$:2fdPά-nۍ{pArǠ@feǠ?+$pB'@T+q^F`@^F`@^F`@D@DR+qAȖdF`HҖdF`HܖdF`HdF`HdF`HdF`HHjqiqBAԟF`AAԟF`AAԟF`AAԟF`AAԟF`AAԟF`AAԟF`At`At`UYsrc:7057Cats.texcommrutes.8Thislimit(AC @B;pA;pBN>)iscalleda brffe35product꨹orapullbffack.src:7059Cats.tex(5)|ThelimitFd¹:DR1!Set/:ofashapSegraph}DҹwithvrertexsetV_l=Vp(DUV)andedgesetE i=URE(DUV)canbSedescribedasfollorws.8Thesetlim c⡎tw.\L?AkpA#ԟM`#ԟM`#ԟM`#ԟM`#ԟM`OO tKL20v̝p20bA׳ ֏ԟQw֏ԟQw) \LƳk̝pAΠP׳yKP֏ԟP֏ԟifKL20ߧvp20bA#ԟǠ@#ԟǠ@#ԟǠ@#ԟǠ@#ԟǠ@@Is)ՠ@fe\4ՠ?**h)Π@fe\4Π?*nk)Ǡ@fe\4Ǡ?* hs 4ŸΠM@fe gΠ?wt1LBǠM@fePtǠ?wY1L0s2src:7163Cats.texSincelrpAkhUR=pA 36=pAݹ1L IforlralllqA2DȹwregetlrbyuniquenesslqkhUR=1LGع.Symmetricallywregethko=UR1L0,thushisanisomorphismwiththerequiredpropSerties.P*gUTG09.07.04 color push BlackG color popTѠY[썍color push Black84ӒRepresen9tableTfunctorsandtheY:onedaLemmaG color popn썍r3.v$Adjointfunctorsandmonads3.1.Adjointfunctors.src:7184Cats.texȍcolor push Black3.1.1.CDe nition.[ color popsrc:7185Cats.texLetCxandDDDbSecategories.FLetF:])C_)!DDandG:]*D !)5CybSeCcorvXariantfunctors.2kFyisIcalledHleft!fadjoint!gtoGandGiscalledright!fadjointtoFyifthereisanaturalisomorphism(naturalinC12URCݹandD2DUV)%Fx'(C5;DS)UR:MorODڲ(FC;DS)P԰n:=Mor%5C*(C;GDS)src:7187Cats.texorsimply _xJMorD(Fƹ-n;-)PUR԰n:=Mor%5C*(-;G-)UR:C5 op @D3!Set*h:Ǎcolor push Black3.1.2.dProp`osition.= color popsrc:7192Cats.texLffetFŤ:#C=~!a^DbeleftadjointtoG#޹:Dy4ߟ!C5.ThenGdeterminesFuniquely35uptoanaturffalisomorphism.color push BlackPrffoof. color pop#Rsrc:7196Cats.texAssume*that+alsoFƟ20Q:URC"!wfDIisleftadjoinrttoG.Thenwrehave+naturalisomorphisms~ƩMorDL (Fƹ-n;-)PUR԰n:=Mor%5C*(-;G-)PUR԰n:=Mor%5D,[(FƟ 0o-Z;-):%Fsrc:7198Cats.texBytheYVonedaLemmaandPropSosition2.10.5wregetFP԰=FƟ20o..Ǎcolor push Black3.1.3.Corollary.[ color popsrc:7202Cats.texLffetFi飹:C7i!#3D,kbeleftadjointtoGi飹:D@!TCJfori=1;2.RLffet X:G1fk!&G2 }bffexanaturalytransformation.w2Thentherexisauniqueynaturaltransformation F :F2fk!F19such35thatthediagrffamWfMorD(F1-9;-33)mMor(C.[(-35;G1-9)Ȗd:2fdFWpά-˰'1(-35;-33)fMorD(F2-9;-33)mMor(C.[(-35;G2-9)Ȗd32fdFWpά- Vp'2(-35;-33) bǠ@fe=Ǡ?냀e˹Mor{!ȟDq+( O-݄;-33)1bǠ@fe2(Ǡ?냀6MorLCQ~й(-35; -FĹ))hcolor push BlackPrffoof. color pop#Rsrc:7212Cats.texGivrenRA;BX2URDUV.%ThenthereQisauniquemorphism O(A):F2An!1F1ARsucrhthatthefollorwingdiagramcommutes`Mor]DG(F1A;-)sMor*pC0m/(A;G1-)8:2fdB0ά-˰n'1(A;-)`Mor]DG(F2A;-)sMor*pC0m/(A;G2-)832fdB0ά- Vpn'2(A;-)ʟǠ@feǠ?냀\Morr0Dy( O(A);-)6zʟǠ@fe6Ǡ?냀;`|MorPyCV8(A; -7) color push BlackG color popUmY[썍color push BlackɲLAdjoin9tTfunctorsrP85G color popnsrc:7219Cats.texWVe2harvetoshowthat ,:F2 B \4!F1 isanaturaltransformation. *Letfʥ:A0!BbSeamorphisminDUV.8Then\OvMMorbMDi(F1B;-)v MorMɟC$(B;G1-)EsH2fdpaЍά-m@'1(B;-)MMorbMDi(F2B;-) MorMɟC$(B;G2-)E:2fdpaЍά-]p@'2(B;-)soAŸΠM@feotΠ?!=Mor7):D>x( O(B);-)s+%ŸΠM@fe+XΠ?s0 tMorEAqCJ0(B; -7)Mor՟Do8(F1A;-)PMorfCk(A;G1-)`dA2fdq0ά-'1(A;-)Mor՟Do8(F2A;-)PMorfCk(A;G2-)`d32fdq0ά- Vp'2(A;-)BǠM@fetǠ?BΠ@fetΠ?i!Mor~WD\( O(A);-)qBǠM@feqtǠ?vMorC$(A; -7)sMorKD(F1f;-){Ʉ QɄQɄM^QɄQ䟙0Q䟙0ssUMork/Cp`(f;G1-)7 QAQKM^QUQ[y䟙0Q[y䟙0s냀IMor^Df1K(F2f;-){Ʉ QɄ攴QɄ?^QɄQ0Q0s냀MorC kϹ(f;G2-)7 QA攴QK?^QUQ[y0Q[y0s 5ksrc:7240Cats.texTherenAisanequivXalenrtde nitionofadjointfunctorsthatwewanttonBgivenow.hFirstweneedsomepreparation.7color push Black3.1.4.Lemma. color popsrc:7243Cats.texLffet35F:URCn!FDandG:D!fgCjbffefunctors.fiThenthemap[M?Nat`P(Id =C1;GFƹ)UR37!G--2Nat(Mor5D`(F-;-33);Mor5C(-35;G-))src:7245Cats.texis35bijeffctivewithinversemap=ιNatQw(Mor5D`(F-;-33);Mor5C(-35;G-))UR3'7!'(-35;F-)(1F.:- B)2Nat(Id =C1;GFƹ):src:7249Cats.texGivren'a۹:aMorןD:(Fƹ-n;-){f!CMor*@C/(-;G-)asafamily'(C5;DS)a:Mor؟D;(FC;DS)a{e!BMor*?C/(C;GDS).TVakre0D:=[FCܞ.Thenweget(Cܞ)\:=['(C5;FC)(1F.:C ):C!GFC.WVe0shorwthat[:IdC!nGFnisanaturaltransformation.src:7251Cats.texFVorfQ:URC1K{!Cܞ20thediagramcommrutes:IjO0Mor0-D8=(FC5;FCܞ)MorD=(FC5;FCܞ20׹)nul:2fdLά-˰nPMorD(FC5;FfG)behMorweD~ȹ(FCܞ20;FCܞ20)E:2fdI0^Оά˰չMor&JҟD-5(Ff;FCܞ20׹)'Mor1$C7H(C5;GFCܞ)MorۆCIE(C5;GFCܞ20׹)m32fdNά-o=MorsCE(C5;GFfG)cR_Morx\C}(Cܞ20;GFCܞ20)U,32fdK0}Оά̹Mor'7ɟC,(f;GFCܞ20׹)C)JǠ@feC\|Ǡ?냀 qD'(C5;FCܞ)ʟǠ@feǠ?냀 '(C5;FCܞ20׹)JǠ@fe+|Ǡ?냀'(Cܞ20;FCܞ20)src:7261Cats.texHencewreget47Jʍj(Cܞ20׹)f=UR(Mor5C(f;GFCܞ20׹)'(Cܞ20;FCܞ20))(1F.:C0`)=UR('(C5;FCܞ20׹)Morय़D0(Ff;FCܞ20׹))(1F.:C0`)=UR'(C5;FCܞ20׹)(FfG)=UR('(C5;FCܞ20׹)Morय़D0(FC5;FfG))(1F.:C )=UR(Mor5C(C5;GFfG)'(C;FCܞ))(1F.:C )=URGFf(Cܞ):6|src:7270Cats.texConrverselyletUR:IdCܠ+!(KGFnbSeanaturaltransformationandlet A&w'(C5;DS)(fG)UR:=Gf(Cܞ)=(Mor5C((C);GDS)G)(fG)UR:CC1(C)_!GFChs[GfJ1K{!GD color push BlackG color popVY[썍color push Black86F:oundationsG color popnsrc:7271Cats.texfor9fd:dFC!LDS.ДWVeshorwthat'e:MoraD 0Ĺ(Fƹ-n- w)!pVMor*SC0(-;G-)9isa:naturaltransformation.GivrengË:URC1K{!Cܞ20thenE͍u8"MornD(FCܞ20;DS)ZLMor1ID8߬(FC5;DS)l:2fdT0ά-˰@|MorvyDܹ(Fgn9;DS)v%Mor[Cչ(Cܞ20;GDS)GCMor2}@C7(C5;GDS)32fdV0ά--sMorcpC/(gn9;GDS)-Ǡ@fe`̟Ǡ?냀il'(Cܞ20;DS)>Ǡ@fe>LǠ?냀Cz'(C5;DS)src:7278Cats.texcommrutessince3ٍʍKl('(C5;DS)Morय़D0(Fgn9;DS))(fG)4=UR'(C5;DS)(fFgn9)4=URG(fFgn9)(Cܞ)4=URGfGFg(Cܞ)4=URGf(Cܞ20׹)g4=URMorOC(gn9;GDS)(Gf(Cܞ20׹)4=UR(Mor5C(gn9;GDS)'(Cܞ20;DS))(fG):5osrc:7287Cats.texNorwletgË:URDk!DS20 obSegiven.8ThethediagramE΍s%Mor "D[(FC5;DS)ևMor- D4[(FC5;DS20!ǹ)"ԟ:2fdUA`ά-˰XMor܎D (FC5;gn9)tMorCfع(C5;GDS)~Mor-{C3g:(C5;GDS20!ǹ)2T32fdW"`ά-EMor{Cs(C5;Ggn9)Ǡ@feD$Ǡ?냀iņ'(C5;DS);xrǠ@fe;Ǡ?냀@^$'(C5;DS20!ǹ)src:7294Cats.texcommrutessinceP3.2.MonadsorTriples.src:7298Cats.texsrc:7302Cats.texWVenorwdescribSeastructurebasedonanendofunctorwhicrhhasturnedouttobSeanimpor-tanrtetechnicaletoSolinstudyingtopSosesandrelatedtopics. UItisanabstractionoftheconceptofadjoinrtandinasenseanabstractionofunivrersalalgebra(seetheremarksin neprinrtattheendof10.2.3bSelorw).color push Black3.2.1.JGDe nition.0 color popsrc:7310Cats.texLetAbSeacategoryandR^:A! AJGbeanendofunctor.WAnRJ-algebrffaisapair(A;a)whereal:RJA|!oAisanarrorwofA.bAhomomorphism?bffetween?RJ-algebras(A;a)and(B;b)isanarrorwfQ:URAn!1BofAsuchthat?O RJA {A\,:2fd0ά-ōaΠRJBxB\32fdЍά- !b׶ZǠ@fe錟Ǡ?냀RJfZǠ@fe⌟Ǡ?냀 fysrc:7320Cats.texcommrutes.8Thisconstructiongivesacategory(Rn:URA)ofRJ-algebras.color push Black3.2.2.SDe nition. color popsrc:7325Cats.texA?monadTUR=(T;n9;)SonacategoryAconsistsTofafunctorT:URAn!1A,togetheriYwithtrwoiYnaturaltransformationsN:id!)QT and൹:TƟ22 B\ ! 6TƟ22 :2fd@ά-q&BTP6TƟ22PAH8T 32fdά-gۍ+^jǠ@feǠ?roHTEWjǠ@feEǠ?+J= color push BlackG color popWY[썍color push Black;F:actorizationsTofamonad87G color popnsrc:7345Cats.texHere,6n9Tand&T3arede ned&asin&1.7.56and1.7.57.Thetransformation3istheunitofthemonadM andisthemultiplicffation.`Theleftdiagramconstitutesthe(leftandrighrt)unaryidenrtitieshandtherightonetheassoSciativeidentityV.%ThereasonforthesenamescomesfromtheanalogybSetrweenmonadsandmonoids.3ThiswillbSemadeclearin3.2.4.Anotherwidelyusednameformonadis`triple'.src:7356Cats.texAnadjoinrtpairgivesrisetoamonadonthedomainoftheleftadjoint.n5color push Black3.2.3.Prop`osition.6 color popsrc:7360Cats.texLffetAU6:URB*!n~AandF:A!B bffeAfunctorssuchthatFbisleftadjointtoU\with"Ë:URid!U@Fand!":FU6!Qidthe"unitandcffounit,respectively.^cThen(U@FS;n9;U"Fƹ)is35amonadonA.src:7366Cats.texNotethatU@"F:URUFUF!eUFƹ,3asrequiredforthemrultiplicationofamonadwithfunctorU@Fƹ.src:7369Cats.texConrverselyV,'|everyRmonadarisesinthatwrayRoutofsome(generallyQmanry)adjointpair.SeeSection3.3fortrwowaysofconstructingsuchadjoints.n4color push Black3.2.4.Example.ہ color popsrc:7373Cats.texLetMgbSeamonoid. BrTherffepresentationQmonadT¹=0(T;n9;)onthecategoryofsetsisgivrenbylettingTƹ(S׹)R=RMPS2forasetS.n9Sɹ:RSS!rGTƹ(S)=MPStakresanelementsUR2So͹tothepair(1;s).)WVede neSoιby(S׹)(m1;m2;s)UR=(m1m2;s)forsUR2S׹,m1;m22M@.Thrustheunitandmultiplicationofthemonadarisedirectlyfromthatof%{themonoid.YTheunitaryandassoSciativitry%zequationscaneasilybeshorwntofollowfromthecorrespSondingequationsforthemonoid.src:7383Cats.texThestandardwrayofgettingthismonadfromanadjoinrtpairisbyusingtheunderlyingandfreefunctorsonM@-sets(see4.2.1???).1IfSandTvareM-sets,>thenafunctionfQ:URS)!!wTvissaid,tobSe,M@-effquivariantiffG(ms)=mf(s),form2M@,=rs2 S׹.FVor,a, xedmonoidM,=rtheM@-setsandtheM-equivXarianrtfunctionsformacategoryV,calledthecffategory35ofM-sets.src:7391Cats.texThefreeM@-setgeneratedbrythesetSTisthesetMh''CSTwithactiongivrenbym209(m;s)=(m209m;s).UsingZTheoremZ9.3.5???,w|onecanshorwimmediatelythatthisdeterminesafunctorleftoadjoinrtptotheunderlyingsetfunctoronthecategoryofM@-sets.q6ThemonadassoSciatedtothisadjoinrtpairistheonedescribSedaborve.color push Black3.2.5.Example.K color popsrc:7401Cats.texLetT:URSet!+fSet@bSethefunctorwhicrhtakesasetAtotheKleeneclosureA2kandafunctionfQ:URAn!1BFtothefunctionfG2 ]U:URA2V .!5B2 de nedinSection2.5.7???.#Letn9Azr:A!qA޹takreanelementatotheone-elementstring(a),andletAzr:A2 zz! yA2 VbSethe6 atteningxopfferationtaking6astring(s1;s2;:::ʜ;snP)6ofstrings6totheconcatenatedstrings1s2:::sn !۹inyA2 9obtainedyine ectbryerasinginnerbracrkets:Vthus((a;b);(c;d;e);();(a;a))goSesto(a;b)(c;d;e)()(a;a)UR=(a;b;c;d;e;a;a).src:7411Cats.texIn-particular, NA((a;b))andforeacrhmorphismD!.Fƹ(Cܞ)thereisanobjectC20x2kLD gandmorphismsf:C520 !r@s4>RHFƹ(Cܞ)xbǠ*FfeǠ?`^Fƹ(fG)src:7589Cats.texcommrutes.color push Black3.5.3.Theorem. color popsrc:7593Cats.texLffetCbeacomplete,IlocallysmallcffategoryandletFҹ:m C B !D4bea(cffovariant)35functor.fiAssumethatCjhasacogenerator.Fhas35aleftadjointifandonlyifs2 color push Black color pop%src:7596Cats.texFprffeserves35limitsand color push Black color pop%src:7597Cats.texFhas35solutionssets.՘color push Black3.5.4.>>De nition.{ color popsrc:7602Cats.texAnobjectC12URCsiscalledacogenerator,`ifforanrytwomorphismsf;gË:URA!nBwithfQ6=URgXthereisamorphismh:BX !_7CFsucrhthathfQ6=hgn9.color push Black3.5.5.Theorem. color popsrc:7606Cats.texLffetCbeacomplete,IlocallysmallcffategoryandletFҹ:m C B !D4bea(cffovariant)35functor.fiAssumethatCjhasacogenerator.Fhas35aleftadjointifandonlyifFprffeserveslimits. color push BlackG color popZ6Y[썍color push Black90F:oundationsG color popn썒Referencescolor push BlackK`y cmr10[Backus,UU1981a] color popHsrc:7626Cats.texBackus,AEJ.:e=3p0J cmsl10The