A criterion for the existence of subobject classif

AcriterionfortheexistenceofsubobjectclassiersHiroshiWatanabeMailBox1503,SemanticsGroupElectrotechnicalLaboratoryTsukuba305-8568,JapanJune30,1998AbstractWegiveacriterionfortheexistenceofsubobjectclassiersofco-completecategorieswithasmall,densesubcategory.(keyword:sub-objectclassier,cocomplete,dense,topos,AMSClassication:18B25,18A40,68Q55)1IntroductionItoftenoccursthatacocompletecategoryEhasasmallanddensesubcat-egoryC.Inthiscase,thereisanadjunctionbetweenthecategoryEandthecategorySetCopofpresheavesoverC,whichenablesustoconstructEobjectsfrompresheavesoverC.Inthispaper,wegiveacriterionfortheexistenceofasubobjectclassierinEexpressedasaconditioninthepresheafcategory.Moreoverwegivethesubobjectclassierconcretelybyusingthepresheavesifthereexistsasubobjectclassier.Thiscriterionisusedheavilyintheproofoftheexistenceofsubob-jectclassierinthecategoryoffunctionalbisimulations[6].Weexpectthisapplicabletoothersimilarproblems.ThisworkwasdonewhentheauthorwasinDepartmentofMathematics,HokkaidoUniversity.1Weproceedasfollows.InSection2werecallgeneralfactsonthead-junctionbetweenacocompletecategoryEandthecategoryofpresheavesoverthesmallcategoryCwhenthereisafunctorfromCtoE.Here,wedonotassumethatCisasubcategoryofE.Thenweintroducethenotionofdensefunctors.WhenafunctorAfromCtoEisdense,thecategoryEisareectivesubcategoryofthepresheafcategoryofC.HenceEisacompletecategorysincepresheafcategoryiscomplete,andthusasubobjectfunctorSub:Eop!Setexists.InSection3wegiveacriterionfortheexistenceofsubobjectclassierofE,totheeectthatthepresheafSub(A())isinE,i.e.,thereexistsanobject2EsuchthatSub(A())=E(A();)holds.Whenwearedealingwithaconcretecategory,itisusuallydiculttondconcretelyinEitselfaspecicwhichsatisestheabovecondition.WeexplainamethodofconstructingEobjectsviapresheavesoverCbymakinguseoftheaboveadjunction,inSection4.Asanexampleofthisconstruction,wegiveaterminalobjectinE.InthecasethereexistsasubobjectclassierinE,wegiveitbyusingpresheafcategory.Thisenablesustomodifythecriterionslightly,whichismoreeectiveforcheckingitinconcretecases.2AbasicadjunctionLetA:C!EbeafunctorfromasmallcategoryCtoacocompletecategoryE.DeneafunctorR:E!SetCopbyR(E)=E(A();E).Proposition2.1([4,pp.41-42]).ThefunctorRhasaleftadjointL:SetCop!E.ThefunctorLisgivenforeachpresheafPbyLP=Colim(ZPP!CA!E):RecallthatthecategoryRPofelementsofapresheafPisdenedasfollows.Itsobjectisapair(C;p)ofanobjectC2Candp2P(C).2Anarrowu:(C;p)!(C0;p0)isaCarrowu:C!C0suchthatp0u=p,wherep0u:=P(u)(p0).ThefunctorP:RP!Cistheprojection(C;p)7!C,andthecompo-sitionoffunctorsZPP!CA!E(1)isadiagraminEwiththeindexingcategoryRP.Weoftenwritethediagram(1)simplybyAP.Outlineofproof.FirstwedeneabijectivecorrespondenceSetCop(P;R(E))=E(LP;E)foreachpresheafPandanobjectE2E.Let2SetCop(P;R(E)).ConsiderthediagramAPandtakeacocone~:AP!Ewith~(C;p)=C(p)foreachobject(C;p)2RP,whereCisthecomponentofthenaturaltransformationatC2C.SincethecategoryEiscocomplete,thereexistsauniversalcocone:AP!Colim(AP)=LP.Bytheuniversalityofthecocone,wehaveauniqueEarrowg:Colim(AP)!Esatisfyingg(C;p)=~(C;p)foreachobject(C;p)2RP.Itiseasytoshowthatthecorrespondence7!gisbijectiveandnaturalforPandE.Denition2.2.ForeachobjectE2E,wecallthefunctor(A()=E)@!CA!EthecanonicaldiagramofE.HereA()=Eisthecommacategory.ItsobjectisapairofC2CandanEarrowf:A(C)!E,anditsarrowfrom(C;f:A(C)!E)to(C0;g:A(C0)!E)isaCarrowu:C!C0suchthatf=gA(u).Thefunctor@:(A()=E)!Cistheprojection:(C;f)7!C.ForeachobjectE2E,therealwaysexistsacocone:A@!Edenedby(C;f)=fforeachobject(C;f)2A()=E,whichwecallthecanonicalcoconeofE.3Denition2.3.AfunctorA:C!EiscalleddenseifthecanonicalcoconeofEisuniversalforeachobjectE2E.Wecallasubcategoryisdensewhentheinclusionfunctorisdense.NotethatthecanonicaldiagramofEisnothingbutthediagramAR(E):RR(E)!E.HenceifthefunctorA:C!Eisdense,thenLR(E)=Colim(ZR(E)R(E)!CA!E)=Colim((A()=E)@!CA!E)=E:ThefollowingfactontheaboveadjunctionLaRisknown.Proposition2.4(See[2]).LetLaRbetheadjunctionofProposition2.1.Thenthefollowingthreeconditionsareequivalenttoeachother.1.ThefunctorA:C!Eisdense.2.TherightadjointfunctorRisfullandfaithful.3.Thecounit:LR!IdE:E!Eoftheadjunctionisanaturalisomorphism,i.e.,theE-componentE:LR(E)!EisisomorphicforeachobjectE2E.Proof.Becausetheequivalencebetween2and3iswell-known,wehaveonlytoshowtheequivalencebetween1and3.BytheadjunctionLaRinProposition2.1,wehavethebijectivecorrespondenceSetCop(R(E);R(E))=E(LR(E);E)forobjectE2EandR(E)2SetCop,andthecounitE:LR(E)!EcorrespondstotheidentitytransformationidR(E)underthisbijectivecor-respondence.IfweassumeAisdense,thenwehaveEisisomorphic.ConverselyifweassumeEisisomorphic,thenthecanonicalcoconehastheuniversality.Hence1and3areequivalent.WhenthefunctorAisdense,thefunctorR:E!SetCopisfullandfaithfulbyProposition2.4.ConsequentlythecategoryEisareective4subcategoryofSetCop.SincethecategorySetCopiscomplete,weobtainbyusing[1,Proposition3.5.3]:Proposition2.5.IfthefunctorA:C!EisdensefromasmallcategoryCtoacocompletecategoryE,thenthecategoryEiscomplete.Henceacocompletecategorywitha