2007), Components, Complements and Reflection Formulas, preprint

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

CLAUDIOPISANI

Abstract.Weillustratetheformula(↓p)x=Γ!(x/p),whichgivesthereflection↓pofacategoryp:P→XoverXindiscretefibrations.Oneofitsproofsisbasedona“complementoperator”whichtakesadiscretefibrationAtothefunctor¬A,rightadjointtoΓ!(A×−):Cat/X→Setandvaluedindiscreteopfibrations.Someconsequencesandapplicationsarepresented.

1.Introduction

The“classical”formulas(see[Lawvere,1973]and[Par´e,1973])

(↓p)x=Γ!(x/p)

orbetter

↓p=Γ!(−/p)

;

↑p=Γ!(p/−)

(2)

whichdisplaythepresheavescorrespondingtothereflectionsofacategoryp:P→XoverabasecategoryXindiscretefibrationsandindiscreteopfibrationsascomponentsof“comma”categories,donotappearatafirstsightparticularlypregnantorself-explicatory.However,notingthatx/pistheproductx/X×pinCat/X(andsimilarlyp/x=X/x×p)andthatx/XandX/x(correspondingtotherepresentablepresheaves)arethereflections↑xand↓xoftheobjectx:1→X,weget

(↓p)x=Γ!(↑x×p)

;

(↑p)x=Γ!(↓x×p)

(3)

;

(↑p)x=Γ!(p/x)

(1)

Theseareexactlytheset-valuedversionoftheformulas

x∈↓p

⇐⇒

Γ!(↑x∩p)

;

x∈↑p

⇐⇒

Γ!(↓x∩p)

(4)

whichclearlygivethereflectionsofasubsetpofaposetinloweranduppersubsets.(HereΓ!isthetwo-valuedcorrespectiveofthecomponentsfunctor,andgivesfalseontheemptysetandtrueelsewhere).Remarkably,alsothemostnaturalproofof(4),

20

CLAUDIOPISANI

basedontheclassicalcomplementoperatorwhichtakeslowersetsintouppersets(andconversely)andontheconsequentlaw

Γ!(↓p∩q)

⇐⇒

Γ!(p∩↑q)

(5)

generalizesalmoststraightforwardlytotheset-valuedcontext.(See[Pisani,2007]foradetaileddiscussionoftheposetcase,whichprovidesusefulinsightandmotivations.)Recallthatthefundamentaladjunctions

Γ!⊣Γ∗⊣Γ∗:Cat→Set

betweenthecomponents,discreteandpointsfunctors,canbegeneralizedto

Γ!⊣Γ∗⊣Γ∗:Cat/X→Set

(7)(6)

whereforp:P→X,Γ!pisgivenbythecomponentsofthetotal(ordomain)categoryP,whileforS∈Set,Γ∗SisthefirstprojectionoftheproductofXandthediscretecategoryonS.Inthepresentcontext,the(partiallydefined)“complementoperator”isparametrizedbysets:

¬:Set×(Cat/X)op→Cat/XIttakesadiscretefibrationAintothe“exponential”functor¬A:=(Γ∗−)A:Set→Cat/Xwhichisvaluedindiscreteopfibrations(andviceversa)andallowstoprovethelaw

Γ!(↓p×q)⇐⇒Γ!(p×↑q)(8)fromwhichthereflectionformulaiseasilydrawn.(Arelateddefinitionof“negation”is

proposedin[Lawvere,1996]).

AfterpresentingsomebasicfactsaboutcategoriesoverabaseinSection2,wedevelopthisandotherproofsofthereflectionformulainSection3.InSection4wetreatcolimitsinXasgivenbythe(partiallydefined)reflectionofCat/Xinprincipal(orrepresentable)discretefibrations.Thus↓(−)isanintermediatestepofthisreflection,andwecaneasilyderiveimportantpropertiesof(co)limitsfollowing[Par´e,1973].InSection5weconsiderthosecategoriest:T→XoverXsuchthat

hom(t,A)∼=ten(t,A):=Γ!(t×A)

(9)

foranydiscretefibrationordiscreteopfibrationA.Againmotivatedbythetwo-valued

case,wecallthem“atoms”.AnyidempotentarrowinXisanatom,andthereflectionsofatomsare,aspresheavesonX,theretractsofrepresentablefunctors;sotheygeneratetheCauchycompletionofX,displayingitastheKaroubienvelopeofX.Finally,inSection6weshowhowthereflectionformulacanbeusedtoobtaininaverydirectwaythereflectionofgraphsin(idempotent,bijectiveorn-periodic)evolutivesets.

SomeofthesetopicshavebeenpresentedattheInternationalConferenceonCategoryTheory(CT06)heldatWhitePointinJune2006,andunderaslightlydifferentperspec-tive,alsointhepreprint[Pisani,2005].Thepreprint[Pisani,2007],towhichwewilloftenrefer,containsmoredetailsandhasamoredidacticalstyle.

Acknowledgements.Theauthorisgratefultotherefereeforhishelpfulremarks.

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

21

2.Categoriesoverabase

Wereviewsomefactsaboutcategoriesoverabasethatwillbeusedinthesequel.Thoughmostofthemarestandard,othersseemnottobewidelyknown.

2.1.Discretefibrationsandstrongdinaturality.LetXbeafixedcategory

op

andy:X→SetXbetheYonedaembedding.Letusdenotebyithefunctor

i:=y/−:SetX

op

→Cat/X(10)

whichtakesapresheafA:Xop→Setintothecategoryofelementsy/Awithitspro-jectionoverX.ThecategoriesoverXisomorphictosomeiAarethediscretefibrations.Thefunctoriisfullandfaithful:

op

SetX(A,B)∼=Cat/X(iA,iB)

(11)

Notethattherighthandsideisdiscreteevenwhenthe2-structureofCat/Xisacknowl-edged.Wedenoteby

op

(12)↓(−):Cat/X→SetXaleftadjointofi;thusi↓(−)givesthereflectionofCat/Xinthefullsubcategoryof

discretefibrations.Similarly,wedefinei:SetX→Cat/Xand↑(−)⊣i.2.2.Remark.Foranyobjectx:1→X,therearebijections

op

Cat/X(x,iA)∼=SetX(X(−,x),A)=Ax∼

op

naturalinA∈SetX.Soweget↓x∼=X/x,the=X(−,x).SincefurthermoreiX(−,x)∼

reflectioni↓xofanobjectindiscretefibrationsistheslicecategoryX/x.Similarly,givenanarrowλ:2→Xofthebasecategory,withdomainxandcodomainy,↓λ∼=X(−,y);andtheinclusionsofthedomainandthecodomainbecomeX(−,λ)andtheidentityrespectively.

Theconstructionofthecategoryofelementsadmitsthefollowinggeneralization.Let

op

Din∗×X→SetasobjectsandthestrongXthecategorythathasthefunctorsX

dinaturaltransformations(alsoknownas“Barrdinatural”,see[Par´e&Roman,1998]and[Ghani,Uustalu&Vene,2004])asarrows.GivenafunctorH∈Din∗X,wedefineacategoryiHoverXasfollows:

•theobjectsoverx∈XaretheelementsofH(x,x);

•givenλ:x→yinX,thereisatmostonearrowfroma∈H(x,x)tob∈H(y,y)overλ,andthisisthecaseiffH(x,λ)a=H(λ,y)b∈H(x,y).

Thenoneeasilyverifies(see[Pisani,2007])thatthisconstructionsistheobjectmapofafullandfaithfulfunctor

i:Din∗/X(13)X→Cat

22

op

CLAUDIOPISANI

thatextendsbothi:SetX→Cat/Xandi:SetX→Cat/X(whichcomeupwhenHisdummyinonevariable).Weareparticularlyinterestedinthefollowingcase:givenA:Xop→SetandD:X→Set,letH(x,y)=Ax×Dy,thatisHisthecomposite

Xop×X

A×D

Set

(14)

TheniHoverXistheproductiA×iDinCat/X.Furthermore,inthiscase

DinX(H,K)∼=Din∗(H,K)∼=Cat/X(iH,iK)

X

thatis,thedinaturaltransformationswithdomainHarealsostronglydinatural,forany

K.

2.3.Changeofbaseandcomponents.Letf:X→Ybeafunctor.Asinanycategorywithpullbacks,itgivesrisetoapairofadjointfunctors

f!⊣f∗:Cat/Y→Cat/X

(15)

wheref!isgivenbycompositionwithf,whilef∗isobtainedbypullingbackinCat.Thepairf!⊣f∗satisfiestheFrobeniuslaw,thatisthemorphism

f!π1∧(ε◦f!π2):f!(p×f∗q)→f!p×q

(16)

isanisomorphismforanyp∈Cat/Xandq∈Cat/Y,εbeingthecounitoftheadjunction.Inparticular,wegetthefibersoverobjectsorarrowsofXofacategoryoverX:

Px

P

p

Pλ

P

p

(17)

X

X

Thepullbackofadiscretefibrationisadiscretefibration;moreprecisely,thelefthanddiagrambelowcommutes(uptoisomorphisms),andsoalsotherighthandsquareofleftadjointscommutes:

Set

iXop

Set

i

Xop

∃f

(18)

f!

(Inparticular,thefiber(iA)xofthediscretefibrationiAisthediscretecategoryonthesetAx.)Wethenobtainthatinthediagrambelow

SetXLL

LLLLLLLSetf

LLiLL

LLLLop

(19)

SetY

op

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

23

↓(−)◦f!⊣i◦Setf,andsinceiisfullandfaithfulalso↓(−)◦f!◦i⊣Setf,thatistheleftKanextensionofA:Xop→Setalongfopcanbecomputedby:

(20)∃fA∼=↓(f!(iA))InthespecialcaseY=1,thediagrams(18)abovebecome

Set

iXop

Colim

Set

i

Xop

(21)

tot

Inparticular,wehavethefunctors

Γ!⊣Γ∗:Set→Cat/X

(22)

Givenp:P→XinCat/X,Γ!pisthesetofcomponentsofthetotalcategoryPwhilefor

asetS,Γ∗SistheprojectionX×S→XoftheproductofXandthediscretecategoryonS.Furthermore,thediscretefunctorΓ∗hasarightadjointΓ∗,givingthesetofpointsofp,thatisitssections.

Theformula(20)nowbecomes

(23)ColimA∼=Γ!(iA)=π0(tot(iA))∼whichexpressesthecolimitofapresheafbythecomponentsofitscategoryofelements.

(Similarly,LimA=Γ∗(iA).)Thiscanbegeneralizedasfollows.Letusdenoteby

Coend∗:Din∗X→Set

aleftadjointtothefunctor∆:Set→Din∗X,definedintheusualway.Then

Din∗XJ

i

J

JJJJJJ∆JJJJJJJJJ

(24)

commutes,andasaboveweget

Coend∗H∼=Γ!(iH)

(25)

WhileingeneralCoend∗HandtheusualCoendHaredifferent(see[Pisani,2007]),by

theremarkattheendofsection2.1,theycoincideforH(x,y)=Ax×Dy:

(26)A⊗D∼=Γ!(iA×iD)=Γ!(iH)∼ThusweareledtoconsiderΓ!(iA×iD)asageneralizedtensorproduct,andwepose

ten:=Γ!(−×−):Cat/X×Cat/X→Set

callingitthe“tensorfunctor”.

(27)

24

CLAUDIOPISANI

2.4.Exponentialsandcomplements.ThecategoryCatisnotlocallycartesianclosed,thatisexponentialsinCat/Xmaynotexist.Whentheydo,theobjectsofpqoverxarethefunctorsPx→Qx,whilethearrowsofpqoverλarethefunctorsPλ→Qλover2(seediagram17).

Discretefibrationsandopfibrationsareexponentiable.Thefollowingparticularcasewillbeneededinthesequel(see[Pisani,2007]):

2.5.Proposition.IfiAisadiscretefibrationandiDadiscreteopfibrationoverX,thentheexponential(iD)iAinCat/Xisadiscreteopfibration(anddually(iA)iDisadiscretefibration).

X×X

thatis,(iD)iAx=DxAxand

A×D

Set(28)

(iD)iAf=DfAf:DxAx→DyAy

h→Df◦h◦Af

2.6.Definition.Givenp:P→XinCat/X,arightadjointtoten(p,−)=Γ!(p×−):Cat/X→Setiscalled“thecomplementofp”andisdenotedby¬p:

ten(p,−)⊣¬p:Set→Cat/X

(29)

Itiseasytoseethatphasacomplementifftheexponential(Γ∗S)pexistsforanysetS.Inthiscasewehave

¬p∼(30)=(Γ∗−)pInparticular,sinceΓ∗SisbothadiscretefibrationandadiscreteopfibrationforanysetS,

Proposition2.5givesthefollowingcorrespectiveofthefactthatclassicalcomplementationonthesubsetsofaposettakeslowersetsintouppersets(andconversely):

2.7.Corollary.AnydiscretefibrationiAhasacomplementvaluedindiscreteop-fibrations(andconversely).Explicitly,asacovariantpresheaf(¬iA)S=(Γ∗S)iA=Set(A−,S),thatis:

(¬iA)Sx=SAx

(¬iA)Sf=SAf:SAx→SAy

h→h◦Af

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

25

2.8.Remark.Theadjunctionten(iA,−)⊣¬iA:Set→Cat/Xrestrictsto

A⊗−⊣Set(A−,):Set→SetX

aparticularcaseoftheclosedstructureofthebicategoryofdistributors.

Wenowprovean“adjunction-like”propertyofthetensorfunctoronCat/Xwhichwillallowustoderivedirectlythereflectionformula.

2.9.Proposition.LetXbeacategory,iAadiscretefibrationandiDadiscreteopfi-brationonX.Thenforanyp:P→XinCat/Xtherearenaturalbijections

ten(p,iA)∼=ten(i↑p,iA)

;

ten(p,iD)∼=ten(i↓p,iD)

Proof.Weprovethefirstone,theotherbeingsymmetrical.ForanysetS

ten(p,iA)→S

i↑p→(¬iA)S

Thefollowingpropositioncanbeinterpretedasthefactthatcomplementationin

Cat/Xisclassical,whenrestrictedtodiscretefibrationsanddiscreteopfibrations;inparticular,itispossibleto“recover”adiscretefibration(orpresheaf)fromitscomplement(see[Pisani,2007]):

2.10.Proposition.IfiAandiBarebothdiscretefibrations(orbothdiscreteopfibra-tions),thenthereisanaturalbijection

hom(iA,iB)∼=hom(¬iB,¬iA)

26

CLAUDIOPISANI

3.1.Proposition.Theleftadjoint↓(−)⊣iisgivenonap:P→Xby

↓p∼=ten(−/X,p)

orequivalently↓p∼=Γ!(−/p).

3.2.Proposition.Therightadjointi⊣(−)◦isgivenonap:P→Xby

p◦∼=hom(X/−,p)

WebeginwithaproofofProposition3.1,bymeansofthecomplementoperator,which

hasastrikingsimilaritywiththat(straightforward)ofProposition3.2.

In[Pisani,2007]itischeckeddirectlythattheaboveformulasactuallygivethedesiredadjoints.Fortheleftadjoint,thischeckisheresupersededbyreviewingotherproofsofProposition3.2,thatrestonstandardcompletenessproperties;namelyonKanextensionsofsetfunctorsandoncolimitsofpresheavesrespectively.

3.3.Thereflectionformulaviacomplementation.WebeginbynoticingthatforanydiscretefibrationiA

Ax∼=ten(x,iA)∼=hom(x,iA)

(32)

Indeed,ingeneralforanyp:P→X,ten(x,p)=Γ!(Px)andhom(x,p)=Γ∗(Px)are

thecomponentsandtheobjectsofthefibercategoryoverx;sinceiAhasdiscretefiberstheresultfollows.

3.4.Proposition.Givenacategoryp:P→XoverX,thepresheaf↓p:Xop→Setactsonobjectsasfollows

(↓p)x=ten(x/X,p)

Proof.

(↓p)x

ten(i↑x,i↓p)

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

27

Itisworthstressingthestrongsimilaritybetweentheabovederivationofthereflectionformulaandthefollowingderivationofthecoreflectionformula:

3.5.Proposition.Givenacategoryp:P→XoverX,thepresheafp◦:Xop→Setactsonobjectsasfollows

(p◦)x=hom(X/x,p)

Proof.

(p◦)x

hom(i↓x,ip◦)

Tocompletetheproofsofpropositions3.1and3.2,notethattheactionofthearrowsλinXonthefibersfollowsfromtheformofthereflection↓λ(seeRemark2.2).3.6.ThereflectionformulaviaKanextension.WebeginbynotingthattheusualcoendformulafortheleftKanextensionofapresheafA:Xop→Setalongafunctorf:X→Y

(33)(∃fA)y∼=A⊗Y(y,f−)mayberewrittenas

∃fA∼=ten(iA,−/f)

(34)

Indeed,by(26),A⊗Y(y,f−)∼=y/f.=ten(iA,i(Y(y,f−)))andi(Y(y,f−))∼

Bythesecondofdiagrams(18)

∃f↓p∼=↓(f!p)

foranyp:P→X.Inparticular

↓p∼=∃p∆1=∃p↓1P∼=↓(p!1P)∼

(36)(35)

where1PistheterminaldiscretefibrationidP:P→PoverP.Sobythe(34)abovewe

conclude

(37)↓p∼=Γ!(−/p)=Γ!(1P×−/p)∼=ten(i∆1,−/p)∼=∃p∆1∼asdesired.(Conversely,thereflectionformulacanbeusedtoderivethecoendformula(33)

or(34),asshownin[Pisani,2007].)

28

CLAUDIOPISANI

3.7.Thereflectionformulaviacolimitsofpresheaves.Webeginbyobservingthatforanyp:P→Xthereisabijection

Cone(p,x)∼=Cone(1,X(p−,x))=Cone(1,Setp↓x)

naturalinx,andthatbyYoneda

A∼=Sety↓A

(39)(38)

foranypresheafA:Xop→Set(ontherighthandside,Aisconsideredasanobjectof

op

SetX).Thenwehavethefollowingchainofbijections,naturalinA:

Cat/X(p,iA)

Cat/P(1P,p∗(iA))SetP(∆1,SetpA)SetP(∆1,Sety◦p↓A)

opop

Cone(y◦p,A)

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

29

4.Colimitsasreflections

Foranyfixedp:P→X,wehavethefollowingbijections,naturalinx:

Cat/X(p,X/x)

Cat/P(1P,p∗(X/x))

Cat/P(i∆1,iX(p−,x))

Cone(1,X(p−,x))

pbj

(Compositionispreservedautomatically.)

jjjjλb

jjjx

Sop:P→XhasacolimitiffthereisauniversalarrowfromptoX/−.Ifthisisthecase,theuniversalarrowisalimitingconep→X/Colimp.Lettingpvary,weinfacthavetwodifferentmodules“cone”

Cone:XP→X

;

Cone:Cat/X→X

bothrepresentableontheright,andsoalsotwodifferentoperativedefinitionsofthecolimitfunctor:eitherasthepartiallydefinedleftadjoint

Colim:XP→X

tothefunctor∆:X→XP,orasthepartiallydefinedleftadjoint

Colim:Cat/X→X

tothefunctorX/−:X→Cat/X.Dually,wehavetwolimitfunctors

Lim:XP→X

;

Lim:(Cat/X)op→X

respectivelyrightadjointto∆:X→XPandto−/X:X→(Cat/X)op.

30

CLAUDIOPISANI

4.2.Remark.Thetwocolimitfunctors(whichagreeoneachsinglep:P→Xasanobjectoftwodifferentcategories)canbemergedinasingle

Colim:Cat/X∗→X

(see[MacLane,1971],[Par´e,1973]and[Kan,1958])whereCat/X∗istheGrothen-dieckcategoryassociatedtothe2-representablefunctorCat(−,X):Cat→Cat(whichincludesbothCat/XandalltheXPassubcategories).Indeed,wehavethefurthermodule“cone”(whichincludestheotherones)

Cone(p,x):=Cat/X∗(p,δx)

whereδ:X→Cat/X∗isthefullandfaithfulfunctorwhichsendsanobjectx∈XtothecorrespondingcategoryoverX.Theisomorphisms

Cone(p,−)∼=Cone(i↓p,−)=Cat/X(i↓p,X/−)∼=Cat/X(p,X/−)∼

showthatthecolimitsofafunctoraredeterminedbyitsreflection:Colimpexistsiff

Colim(i↓p)exists,andifthisisthecasetheyareisomorphic.Thus,ifpandqinCat/Xhaveisomorphicreflectionsthen

(43)Colimp∼=Colimqeitherexistingiftheotheronedoes.Morethanthat,thesameremainstrueaftercom-posingwithanyfunctorf:X→Y:

4.3.Proposition.Twocategoriesp:P→Xandq:Q→XoverXhaveisomorphic

reflectionsi↓p∼=i↓qifandonlyifforanyf:X→Y

Colim(f◦p)∼=Colim(f◦q)eithersideexistingiftheotheronedoes.

Proof.Onedirectionisadirectconsequenceofequation(40).Theotherfollowsfrom

theisomorphismsCone(f◦p,−)∼=Cat/X(i↓p,f/−)=Cat/X(p,f∗(Y/−))∼=Cat/Y(f!p,Y/−)∼

∼=Cone(f◦(i↓p),−)=Cat/Y(f!(i↓p),Y/−)∼Alternatively,onecoulduse(35)and(43).

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

31

Soafunctorhasanabsolutecolimitiffthe“intermediatestep”i↓(−)ofthereflectionofacategoryoverXinprincipaldiscretefibrations,isinfactalreadythefinalstep.4.5.Remark.SinceColim⊣X/−∼=i◦yandiisfullandfaithful

SetXJJ

JJJJJJyJJiJJ

JJJJJ

op

(44)

X

alsoColim◦i⊣y,sothattheleftadjointtotheYonedaembeddinghasthewell-known

form:ittakesapresheafAtothecolimitColimiAofitscategoryofelementsoverX.Bycomposingtheadjunctionsf!⊣f∗andColim⊣Y/−

f!⊥f∗

Cat/Xweget

Cat/YY/−

Y

(45)

Colim(f◦−)⊣f/−:Y→Cat/X

Andsincef/−∼=i◦Setf◦y

SetXJJ

JJJJJJSetf◦yJJiJJ

JJJJJ

asaboveweget

op

(46)

(47)

Y

(48)

Colim(f◦i−)⊣Setf◦y

wheretheleftadjointtakesapresheafAtotheweightedcolimitA∗f∼=Colim(f◦iA),

displayingitasacolimit.

IntheparticularcaseY=Set,theadjunction(46)isthe(dualof)ten(A,−)⊣¬Aofsection2.4,whiletheadjunction(48)becomesthe(dualof)A⊗−⊣Set(A−,).

5.Atomsandtheirreflections

Wesaythatacategoryt:T→XoverXisa“leftatom”iftherearebijections

ten(t,iA)∼=hom(t,iA)

32

op

CLAUDIOPISANI

naturalinA∈SetX.Dually,tisa“rightatom”if

ten(t,iD)∼=hom(t,iD)

naturalinD∈SetX.Wesaythattisanatomifitisbothaleftandarightatom.We

shallseethatthedistinctionbetweenleftandrightatomsisillusory.Observethatanyobjectx:1→XofthebasecategoryXisanatom(see(32)).5.1.Proposition.Foranyfunctorf:X→Ytherearebijections

tenX(p,f∗q)∼=tenY(f!p,q)

naturalinp∈Cat/Xandq∈Cat/Y.

Proof.UsingtheFrobeniuslaw(16),wehave:

tenX(p,f∗q)=Γ!(p×f∗q)∼=Γ!(f!p×q)=tenY(f!p,q)=Γ!(f!(p×f∗q))∼

(49)

Wenowshowthatidempotentarrowsofthebasecategoryareatoms.Thisisessen-tiallythefactthatinthegraphcorrespondingtoanidempotentendomapping,thefixed

points(orloops)correspondtothecomponents.Letebethemonoidwhichrepresentstheidempotentarrowsofcategories,thatistheonewhoseuniquenon-identityarrowisidempotent.

5.3.Proposition.Anyidempotente:e→XinXisanatom.ForanydiscretefibrationordiscreteopfibrationDonX,ten(e,iD)∼=hom(e,iD)isthesetfixDeoftheelementsofDxfixedbyDe:Dx→Dx.

Proof.ForanydiscretefibrationordiscreteopfibrationiD,

ten(e,iD)∼=Γ!(e×iD)∼=Γ!(e∗(iD))∼=Γ!i(SeteD)∼=Colim(SeteD)hom(e,iD)∼=hom(1e,e∗(iD))∼=Γ∗(e∗(iD))∼=Γ∗i(SeteD)∼=Lim(SeteD)Butforanyfunctore:e→C,thelimitandthecolimitofe,whentheyexist,are

canonicallyisomorphic(see[Borceux,1994]).IfC=Setthesearegivenbythefixedpointsoftheidempotentmapping.

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

33

Notethatinthiscontextitisimportanttodistinguishbetweenidempotentarrowsasdefinedabove,andarrowse:2→Xwhichhappentobeidempotentendomorphisms;anarrowλ:2→Xisanatomiffitisanisomorphism.5.4.Proposition.Foranyt:T→X,tisarightatomiff

↓t⊗−∼=Nat(↑t,−):SetX→Set

Dually,tisaleftatomiff

op−⊗↑t∼=Nat(↓t,−):SetX→Set

Inparticular,foranyidempotentatome:e→X,

↓e⊗D∼=fixDe=Nat(↑e,D)∼

;

A⊗↑e∼=fixAe=Nat(↓e,A)∼

Proof.RecallingProposition2.9,onehasthefollowingbijections,naturalinD∈SetX:

Nat(↑t,D)∼=hom(t,iD)=hom(i↑t,iD)∼↓t⊗D∼=ten(i↓t,iD)∼=ten(t,iD)

ByYoneda,anyidempotentinSetX

op

onarepresentableX(−,x0)hastheform

X(−,e):X(−,x0)→X(−,x0)

forauniqueidempotente:x0→x0inX.

5.6.Corollary.LetA:Xop→SetbeapresheafonX.ThenAisaretractinSetX

oftherepresentablefunctorX(−,x0),associatedtotheidempotentX(−,e):X(−,x0)→X(−,x0),ifandonlyifA∼=↓e.Proof.TheretractAisthelimitofX(−,e):e→SetX,andthusisgivenpointwisebyAx∼=fixX(x,e).TheresultthenfollowsbyCorollary5.5.

op

op

34

CLAUDIOPISANI

5.7.Proposition.LetA:Xop→SetandD:X→Setbesuchthat

op

−⊗D∼=Nat(A,−):SetX→Set

ThenAisaretractinSetXofarepresentablefunctor.

Proof.Letu∈A⊗D∼=Γ!(iA×iD)beauniversalelementof−⊗D.Thenuisthecomponentofapair󰀜a,d󰀝over,say,x0∈X:

u=[󰀜a,d󰀝],

a∈Ax0,d∈Dx0

op

op

Letι:A→X(−,x0)betheuniquemorphisminSetX

suchthat(ι⊗D)u=[󰀜idx0,d󰀝]:

[󰀜idx0,d󰀝]=(ι⊗D)u∼=Γ!(ι×iD)[󰀜a,d󰀝]=[󰀜ιa,d󰀝]

andletρ:X(−,x0)→AbetheuniquemorphisminSetX

op

suchthatρidx0=a.Then

(ρ◦ι)⊗D∼=Γ!((ρ◦ι)×iD):[󰀜a,d󰀝]→[󰀜a,d󰀝]

sothatρ◦ι=idA,asrequired.

5.9.Remark.In[Kelly&Schmitt,2005]itisshown,inanenrichedcontext,theequiv-alencebetween1and2andthefactthatAandDareadjointmodules.

ByProposition5.4andtheequivalencebetween1and2inProposition5.8,itfollows5.10.Corollary.Anyrightatomisalsoaleftatom,andviceversa.

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

35

ByProposition5.8,foranyatomt:T→Xthereexistsanidempotente:x→xinXsuchthat↑t∼=↑eand↓t∼=↓e.Thisidempotentisnotunique,sinceforexampleife

ri

splitsasx→y→x,then↓e∼=↓y.5.11.Corollary.ForanatomT→Xthefollowingareequivalent:1.thasalimit.2.thasacolimit.3.thasanabsolutelimit.4.thasanabsolutecolimit.

Proof.Indeed,alltheaboveareequivalentforanye:e→X(see[Borceux,1994]),andsobypropositions4.3and4.4theyareequivalentalsofort.

t

6.Graphsandevolutivesets

Asaparticularcaseofthereflectionformula,considerX=N,themonoidofnaturalnumbers,asthebasecategory.Thenwehavetheadjunction

↑(−)⊣i:SetN→Cat/N

withtheusualformula:foranyp:P→N,

(↑p)⋆∼=ten(N/⋆,p)

(51)(50)

36

CLAUDIOPISANI

where⋆istheonlyobjectofN,sothatN/⋆is(oppositeof)theposetofnaturalnumbers,withitsprojectiononN.Theactionisgivenbytherightshift:

k:[n,a]→[n+k,a]

(a∈P)

AmongthecategoriesoverNtherearetheuniquefactorizationlifting(UFL)functors(see[Bunge&Niefield,2000]),whichincludediscretefibrationsanddiscreteopfibration,andwhichcanbeidentifiedwith(irreflexive)graphsasfollows.ForanyG∈GphwehavetheUFLfunctorF!:FG→FL∼=N,whereListheterminalgraph(theloop),andF:Gph→Catisthefreecategoryfunctor;slightlyimproperly,wedenotebyFalsotheresultingfunctorF:Gph→Cat/N.Conversely,foranyUFLfunctorp:P→NwegetagraphGbythepullbackbelow(inGph):

G

|P|

|p|

(52)

|N|

thatis,thearrowsofGarethoseof|P|whichareover1∈N.ItiseasytoseethatwesoobtainanequivalencebetweenGphandthefullsubcategoryofCat/NofUFLfunctors.Furthermore,sinceUFLfunctorsareclosedunderpullbacks,thefunctorF:Gph→Cat/Npreservesproducts:F(G×H)∼=FG×FH.Andsinceagraphandthefreecategoryonithavethesamecomponents,F:Gph→Cat/Nalsopreservescomponents:Γ!G∼=Γ!FG.Thusintheparticularcasethatp:P→NisanUFLfunctorFG→N,thereflectionformula(51)takesthefollowingform:

(↑FG)⋆∼=ten(N/⋆,FG)∼=ten(FA,FG)∼=Γ!(FA×FG)

∼=Γ!(A×G)=Γ!(F(A×G))∼

whereA∈Gphistheinfiniteanti-chain:

••

(53)

•

•

•

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

37

6.2.Remark.Similarly,onegetsthereflectionformulaforgraphsoverabasegraphGingraph(op)fibrationsoverG(see[Boldi&Vigna,2002]);orequivalently,theleftadjointtotheinclusionSetFG→Gph/G(see[Pisani,2007]and[Pisani,2005]).6.3.Examples.1.LetGbethegraph

•

••,wherein

themissingcodomainsinGhavebeenadded.Ontheotherhand,therearenochainsinG,sothatthecoreflectionG◦isvoid:thenodeswithnocodomainshavebeendeleted.

whichisnotanevolutivesetbecause2.LetGbethegraph•

therearetwoarrowsoutofonenode.Applyingthereflectionformula,wemultiplyGbytheanti-chainA,gettingthetwo-componentsgraph

•/•

•//////////

////////

///////

////•/////•@@/@@/@@/@@/

@@//@@//@@//@@//

@@/@@/@@/@@/

@/@/@/@/

•/

••••

SothereflectionofGhastwonodes.Furthermore,theactiononitisgivenagain

byrighttranslation,sothatthesecondcomponentisafixedpointandweget

G−=•

whereinthemultiplecodomainsinGhavebeenidentified.Ontheotherhand,therearefourchainsinGsothatG◦hasfournodes:

G◦=

•

•

thatis,thenodeswithmultiplecodomainshavebeensplit.

38

3.IfG=•

CLAUDIOPISANI

•−−

andG3=,thenG−•1,G2andG3

◦

arealltheloop(identificationprevailsinG−1).Asforcoreflections,G1istheloop,

◦

G◦2isthesumoftheloopandtheanti-chainwithaloopaddedatitsend,andG3isthesetofsequencesinatwo-elementset,undertheactions→s(1+).

Now,letethe“idempotentarrow”categoryofSection5,andf:N→ethefunctorwhichtakes1∈Ntothenon-identityarrowofe.Thecomposite

Set

hasaleftadjoint

e

Setf

Cat/N

l:=∃f◦↑(−)∼=↑(−)◦f!:Cat/N→Sete(lp)⋆∼=tene(e/⋆,f!p)∼=tenN(f∗(e/⋆),p)

(54)

(seediagrams18).Then(recallingProposition5.1)

(onlynon-where⋆istheonlyobjectofe,sothate/⋆isthecategory••

identityarrowsdrawn)withitsprojectionone,andf∗(e/⋆)∼=FEwhereEisthegraph••.Thus,asabove,thenodesofthereflectionG−ofthegraphGinidempotentevolutivesetsarethecomponentsoftheproductE×GinGph.Theactionisgivenagainbythe“shift”inE.(Ofcourse,onehasalsothecorrespondingcoreflectionformula:Gph(E,G)givesthenodesofthecoreflectionG◦.)

Similarly,toobtainthenodesofthereflectionsofagraphGinbijectiveorn-periodicevolutivesets,wehavetotakethecomponentsoftheproductsZ×GandZn×Grespec-tively,withthegraphsZandZnbelow

Z=

•

••

•

(narrows)(56)

COMPONENTS,COMPLEMENTSANDTHEREFLECTIONFORMULA

39

6.4.Examples.

1.ItiseasytoseethatifGisconnected(thatis,Γ!G=1)thenE×Ghasn+1components,wherenisthenumberofnodesthatarenotcodomainsofanyarrow.Sothereflectioninidempotentevolutivesetsactsoneachcomponentbymaintainingsuchnodes,andcollapsingtherestofittothefixedpoint.2.ThereflectionG−ofagraphGinn-periodicevolutivesetsisobtainedbytakingthecomponentsofZn×G.Since,asitiseasilychecked,

Zk×Zn=gcd(k,n)·Zlcm(k,n)

wededucethatZ−khasgcd(k,n)nodesandso,beingconnected,

Z−k=Zgcd(k,n)

Sinceanybijectiveevolutivesetisasumofcycles,G=reflectionisgivenby

G−=

∞󰀁󰀄k=1

󰀃∞

k=1

Sk·Zk,itsn-periodic

Sk·Zk

󰀂−

=

∞󰀄k=1

Sk·Z−k=

∞󰀄k=1

Sk·Zgcd(k,n)

6.5.Remark.ConsideringGphasapresheafcategory(ratherthanasubcategoryof

Cat/N),alltheabovereflectionsbecomeinstancesofKanextensions.Butthepresentapproachgivesamoredirectandintuitivewayofcomputingthem.

References

F.Borceux(1994),HandbookofCategoricalAlgebra1(BasicCategoryTheory),Encyclo-pediaofMathematicsanditsapplications,vol.50,CambridgeUniversityPress.M.BungeandS.Niefeld(2000),ExponentiabilityandSingleUniverses,J.PureAppl.

Algebra148,217-250.N.Ghani,T.UustaluandV.Vene(2004),Build,AugmentandDestroy.Universally,Pro-ceedingoftheAsianSymposiumonProgrammingLanguages,LNCS3302,Springer,Berlin,327-347.D.M.Kan(1958),AdjointFunctors,Trans.Am.Math.Soc.87,294-329.

G.M.KellyandV.Schmitt(2005),NotesonEnrichedCategorieswithColimitsofsome

Class,TheoryandAppl.Cat.17,399-423.J.LambekandP.J.Scott(1986),IntroductiontoHigherOrderCategoricalLogic,Cam-bridgestudiesinadvancedmathematics,vol.7,CambridgeUniversityPress.

40

CLAUDIOPISANI

M.LaPalmeReyes,G.E.Reyes,H.Zolfaghari(2004),GenericFiguresandtheirGlueings,

PolimetricaS.a.s.,Monza.F.W.Lawvere(1970),EqualityinHyperdoctrinesandtheComprehensionSchemeasan

AdjointFunctor,ProceedingsoftheAMSSymposiumonPureMathematics,XVII,1-14.F.W.Lawvere(1973),MetricSpaces,GeneralizedLogicandClosedCategories,Rend.

Sem.Mat.Fis.Milano43,135-166.RepublishedinReprintsinTheoryandAppl.Cat.No.1(2002)1-37.F.W.Lawvere(1989),QualitativeDistinctionsbetweensomeToposesofGeneralized

Graphs,ProceedingsoftheAMSSymposiumonCategoriesinComputerScienceandLogic,ContemporaryMathematics,vol.92,261-299.F.W.Lawvere(1996),AdjointsinandamongBicategories,Proceedingsofthe1994Con-ferenceinMemoryofRobertoMagari,Logic&Algebra,LecturesNotesinPureandAppliedAlgebra,180:181-189,Ed.UrsiniAglian`o,MarcelDekker,Inc.Basel,NewYork.S.MacLane(1971),CategoriesfortheWorkingMathematician,GraduateTextsinMath-ematics,vol.5,Springer,Berlin.R.Par´e(1973),ConnectedComponentsandColimits,J.PureAppl.Algebra3,21-42.R.Par´eandL.Rom´an(1998),DinaturalNumbers,J.PureAppl.Algebra128(1),33-92.C.Pisani(2005),BipolarSpaces,preprint,math.CT/0512194.

C.Pisani(2007),Components,ComplementsandReflectionFormulas,preprint,math.-CT/0701457.P.Boldi,S.Vigna(2002),FibrationsofGraphs,DiscreteMath.243,21-66.viaGioberti86,10128Torino,Italy.

Email:pisclau@yahoo.it

Thisarticlemaybeaccessedathttp://www.tac.mta.ca/tac/orbyanonymousftpatftp://ftp.tac.mta.ca/pub/tac/html/volumes/19/2/19-02.{dvi,ps,pdf}

THEORYANDAPPLICATIONSOFCATEGORIES(ISSN1201-561X)willdisseminatearticlesthatsignificantlyadvancethestudyofcategoricalalgebraormethods,orthatmakesignificantnewcontribu-tionstomathematicalscienceusingcategoricalmethods.Thescopeofthejournalincludes:allareasofpurecategorytheory,includinghigherdimensionalcategories;applicationsofcategorytheorytoalgebra,geometryandtopologyandotherareasofmathematics;applicationsofcategorytheorytocomputerscience,physicsandothermathematicalsciences;contributionstoscientificknowledgethatmakeuseofcategoricalmethods.

ArticlesappearinginthejournalhavebeencarefullyandcriticallyrefereedundertheresponsibilityofmembersoftheEditorialBoard.Onlypapersjudgedtobebothsignificantandexcellentareacceptedforpublication.

Fulltextofthejournalisfreelyavailablein.dvi,PostscriptandPDFfromthejournal’sserverathttp://www.tac.mta.ca/tac/andbyftp.Itisarchivedelectronicallyandinprintedpaperformat.

Subscriptioninformation.Individualsubscribersreceiveabstractsofarticlesbye-mailasthey

arepublished.Tosubscribe,sende-mailtotac@mta.caincludingafullnameandpostaladdress.Forin-stitutionalsubscription,sendenquiriestotheManagingEditor,RobertRosebrugh,rrosebrugh@mta.ca.

Informationforauthors.

AThetypesettinglanguageofthejournalisTEX,andLTEX2e

stronglyencouraged.Articlesshouldbesubmittedbye-maildirectlytoaTransmittingEditor.Pleaseobtaindetailedinformationonsubmissionformatandstylefilesathttp://www.tac.mta.ca/tac/.

Managingeditor.RobertRosebrugh,MountAllisonUniversity:rrosebrugh@mta.caTEXnicaleditor.MichaelBarr,McGillUniversity:mbarr@barrs.orgTransmittingeditors.

RichardBlute,Universit´ed’Ottawa:rblute@uottawa.caLawrenceBreen,Universit´edeParis13:breen@math.univ-paris13.frRonaldBrown,UniversityofNorthWales:r.brown@bangor.ac.ukAurelioCarboni,Universit`adellInsubria:aurelio.carboni@uninsubria.itValeriadePaiva,XeroxPaloAltoResearchCenter:paiva@parc.xerox.com

EzraGetzler,NorthwesternUniversity:getzler(at)math(dot)northwestern(dot)eduMartinHyland,UniversityofCambridge:M.Hyland@dpmms.cam.ac.ukP.T.Johnstone,UniversityofCambridge:ptj@dpmms.cam.ac.ukG.MaxKelly,UniversityofSydney:maxk@maths.usyd.edu.auAndersKock,UniversityofAarhus:kock@imf.au.dk

StephenLack,UniversityofWesternSydney:s.lack@uws.edu.au

F.WilliamLawvere,StateUniversityofNewYorkatBuffalo:wlawvere@acsu.buffalo.eduJean-LouisLoday,Universit´edeStrasbourg:loday@math.u-strasbg.frIekeMoerdijk,UniversityofUtrecht:moerdijk@math.uu.nlSusanNiefield,UnionCollege:niefiels@union.eduRobertPar´e,DalhousieUniversity:pare@mathstat.dal.caJiriRosicky,MasarykUniversity:rosicky@math.muni.cz

BrookeShipley,UniversityofIllinoisatChicago:bshipley@math.uic.eduJamesStasheff,UniversityofNorthCarolina:jds@math.unc.eduRossStreet,MacquarieUniversity:street@math.mq.edu.auWalterTholen,YorkUniversity:tholen@mathstat.yorku.caMylesTierney,RutgersUniversity:tierney@math.rutgers.edu

RobertF.C.Walters,UniversityofInsubria:robert.walters@uninsubria.itR.J.Wood,DalhousieUniversity:rjwood@mathstat.dal.ca