The Royal Swedish Academy of Sciences

1、the royal swedish academy of sciences image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, proposit

2、ionsastypes steveawodey andrejbauer institutmittag-le er theroyalswedishacademyofsciences june2021 abstract imagefactorizationsinregularcategoriesarestableunderpull-backs,sotheymodelanaturalmodaloperatorindependenttypethe-ory.thisunarytypeconstructorahasturneduppreviouslyinasyntacticformasawayoferas

3、ingcomputationalcontent,andformal-izinganotionofproofirrelevance.indeed,semantically,thenotionofasupportissometimesusedassurrogatepropositionassertinginhab-itationofanindexedfamily. wegiverulesforbrackettypesindependenttypetheoryandpro-videcompletesemanticsusingregularcategories.weshowthatdepen-dent

4、typetheorywiththeunittype,strongextensionalequalitytypes,strongdependentsums,andbrackettypesistheinternaltypetheoryofregularcategories,inthesamewaythattheusualdependenttypetheorywithdependentsumsandproductsistheinternaltypetheoryoflocallycartesianclosedcategories. wealsoshowhowtointerpret rst-orderl

5、ogicintypetheorywithbrackets,andwemakeuseofthetranslationtocomparetypetheorywithlogic.speci cally,weshowthatthepropositions-as-typesinter-pretationiscompletewithrespecttoacertainfragmentofintuitionistic rst-orderlogic.asaconsequence,amodi eddouble-negationtrans-lationintotypetheory(withoutbrackettyp

6、es)iscompleteforallofclassical rst-orderlogic. msc2000classi cation:03g30,03b15,18c50 keywords:categoricallogic,typetheory,regularcategories,brackettypesdepartmentofphilosophy,carnegiemellonuniversity,pittsburgh,usa,e-mail: imfmdepartmentofmathematics,universityinljubljana,slovenia,e-ma

7、il:andrej.bauer 1 image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, acknowledgement.wegratefully

8、acknowledgethesupportofthein-stitutmittag-le er,theroyalswedishacademyofsciences,wherethisresearchwasconducted.wealsothankpeteraczel,larsbirkedal,thierrycoquand,nicolagambino,millimaietti,permartin-lof,grigorimints,erikpalmgren,frankpfenning,danascott,andantonsetzerfortheircontributions.thisworkispa

9、rtofthelogicoftypesandcomputationprojectatcarnegiemellonuniversityunderthedirectionofdanascott.1introduction accordingtooneconceptionofthetheoryoftypes,propositionsandtypesareidenti ed: propositions=types. thisideaiswell-knownundertheslogan“propositionsastypes”,andhasbeendevelopedbymartin-lofml84and

10、othershow80,tai.inthisre-portwedistinguishpropositionsandtypes,butstaywithinatype-theoreticframework.weregardsometypestobepropositions,butnotnecessarilyallofthem.additionally,eachtypeahasanassociatedpropositiona.thisgivesusacorrespondence propositionstypes whichisinfactanadjunction.sinceitwillturnou

11、tthatp=pforanypropositionp,thepropositionsareexactlythetypesintheimageofthebracketconstructor .wecallthesetypesathebrackettypes.thepictureisthensimply propositions=types. theseideasarenotnew.ourworkoriginatedwithfrankpfenningsbrackettypesforerasingcomputationalcontentpfe01.speakingsomewhatvaguely,th

12、eideaistouseabrackettypeforhidingcomputationalcontentofatype.asasimpleexample,considerthecomputationalcontentofatermpoftype n:nm:neq(2m,n)+m:neq(2m+1,n). givenanaturalnumbern,thenpn= i,m ,wherei0,1andmn,suchthatn=2m+i.bybracketingthetwodependentsums,weobtainthetype .n:nm:neq(2m,n)+m:neq(2m+1,n) 2 im

13、age factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, atermqofthistypehidestheinformationthatisprovide

14、dbythedependentsumssothatqniseither0or1,dependingonwhethernisevenorodd.intheextremecase,atermroftype n:nm:neq(2m,n)+m:neq(2m+1,n) doesnotcarryanycomputationalcontentatallitjustwitnessesthefactthateverynumberisevenorodd. thebrackettypeswhichweconsiderareessentiallythesameasthemonotypesofmaiettimai98,

15、inasuitablesetting.palmgrenpal01formulatedabhkinterpretationofintuitionisticlogicandusedimagefactorizations,whichareusedinthesemanticsofourbrackettypes,torelatethebhkinterpretationtothestandardcategory-theoreticinterpretationofproposi-tionsassubobjects.aczelandgambinoag01havepromotedwhattheycalllogi

16、c-enrichedtypetheoryinwhichtheyseparatethelogicfromtypethe-ory.thebrackettypescanbeusedtotranslatetheprimitivelogicbackintotypetheory(theusualtranslationof“propositionsastypes”worksaswell).alreadyinhisdialecticaarticle,lawverelaw69proposedacategoricaltreatmentofprooftheorythatiscloselyrelatedtobrack

17、ettypes. thereportisorganizedasfollows.insection2weintroducethebrackettypes.insection3wegivethesemanticsofbrackettypesinregularcat-egories,andproveitssoundnessandcompleteness.insection4westudysomepropertiesofbrackettypes.insection5weshowhowbrackettypesareusedinconjunctionwithotherdependenttypestode

18、nethelogicalconnectivesandquanti erswithintypetheory.insection6weusebrackettypestocomparetwointerpretationsoflogic:thestandard“propositionsastypes”interpretation,andtheusual rst-orderone. 2brackettypes weconsideramartin-lofstyledependenttypetheoryml84,ml98.fortheformulationofbrackettypeswedonotneedd

19、ependentsumsorproducts,butwesometimesassumethattheyarepresentinthetypetheory.weworkinatypetheorywithstrongandextensionalequalityandstrongdependentsums,cf.jac99.forreference,welisttherulesinappendixa. amongthetypes,therearesomethatsatisfythefollowingconditionof“proofirrelevance”: ptype q:p p=q:p p:p(

20、1) inwords,thismeansthatanytwotermspandqofsuchatypepare(extensionally)equal.wecallthetypessatisfyingproofirrelevanceproposi-tions.theywerecalledmonotypesbymaiettimai98,andthereareotherequivalentformulations. 3 image factorizations in regular categories are stable under pullbacks, so they model a nat

21、ural modal operator in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, ifpandqarepropositionsinthissense,thenclearlysoare 1,pq,pq,x:ap whereinthelastexpressionpmaydependonanarbitrarytypea.inlogicalterms,this

22、meansthatpropositionsarealreadyclosedunderthefollowinglogicaloperations: t,pq,p= q, x:a.p. insection5wewillseehowtode netheremaining rst-orderlogicaloper-ations. becauseofproofirrelevance,ifapropositionpisinhabited,thenitissobypreciselyoneterm(uptoextensionalequality).thus,atypingjudgment p:p islike

23、astatementofpstruth, ptrue aspdoesnotplayanyroleotherthanuniquelywitnessingthefactthatpholds. weintroduceanewtypeconstructor whichassociatestoeachtypeaapropositiona,calledtheassociatedpropositionofa.theaxiomsgiveninfigure1weredesignedwiththefollowingadjunctioninmind,foranytypeaandpropositionp: x:a p

24、:p x :a p :p(2) ingtherulesprovidedinfigure1,wecantakep =(pwherex=x ),sincetheequalityconditiononp:pforeliminationissatis edbyproofirrelevance(1).seeremark5insection7forconsiderationofalternateformulationsofbrackettypes. asanexample,letusshowthatthetermformingoperation isepicinthefollowingsense: ,x:

25、a sx/u=tx/u:b ,u:a s=t:b(3) ifwethinkofaterm,x:a r:basanarrowabintheslicecategoryover,aswewillinsection3,thenwehavethefollowingsituationover: a as tb 4 image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. this unary t

26、ype constructor a has turned up previously in a syntactic form as a way of erasing computational content, brackettypes atypeformation atype q:a btype a:aintro a:a,x:a b:b,x:a,y:a b=by/x:belim bwherex=q:b p:a q:aequality p=q:a conversions bwherex=a bx/uwherex=q=ba/xbq/u freevariables fv(a)=fv(a) fv(a

27、)=fv(a) fv(bwherex=q)=(fv(b)x)fv(q) substitution at/x=at/x at/x=at/x (bwherex=q)t/y=bt/ywherex=(qt/y) (providedx=yandcaptureofxintisavoided) compatibilityrules a=a a=a b=b q=q = = = a=a a=a (bwherex=q)=(b wherex=q ) figure1:brackettypes 5 image factorizations in regular categories are stable under p

28、ullbacks, so they model a natural modal operator in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, now(3)saysthats =t impliess=tforarbitrarys,t:ab,whichmeansthat isepic.toprove(3),observe rstthatbytheequali

29、tyrulewehave ,x:a,y:a x=y:a therefore ,x:a,y:a sx/u=sy/u:a whichmeansthatwecanformthetermsx/uwherex=u.similarly,wecanformthetermtx/uwherex=u.nowweget s=(sx/uwherex=u)=(tx/uwherex=u)=t. thesecondequalityfollowsfromtheassumptionsx/u=tx/uandthecompatibilityruleforwhereterms. aconsequenceof(3)isthefollo

30、wingconversion,calledexchange:bwherex=(pwherey=q)=(bwherex=p)wherey=q.theruleisvalidwheny=xandyfv(b).by(3)itsu cestoverifytheexchangeruleforthecaseq=zwherez:aisafreshvariable.wethenget(bwherex=p)wherey=z= = =bz/ywherex=(pz/y)bwherex=(pz/y)bwherex=(pwherey=z) inthesecondequalitywetookintoaccountthefa

31、ctthatydoesnotoccurfreelyinb,andinthethirdequalityweappliedtheruletothesubtermpz/y,whichwecandobecauseofthecompatibilityrules. 3categoricalsemanticsofbrackettypes inthissectionwepresentasemanticsforbrackettypesinregularcategories,seee.g.bor94forthelatter.therulesinfigure1aresoundandcompleteforsuchse

32、mantics. de nition3.1aregularcategorycisacategorywith nitelimitsinwhich 1.everykernelpairhasacoequalizer,and 2.thepullbackofaregularepimorphismisaregularepimorphism. 6 image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theo

33、ry. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, the rstconditionstatesthatinaregularcategorywecanformquo-tientsbyequationallyde nedequivalencerelations,andthesecondconditionrequiressuchquotientstobehavewellwithrespectto niteli

34、mits. letus rstrecallhowtointerpretdependenttypetheorywithdependent sumsandstrongextensionalequalityeqinacategorywith nitelimits.weusethesemanticbracketxtodenotetheinterpretationofx,wherexcouldbeatype,aterm,acontext,orajudgment.whennoconfusioncanarise,weomitthesemanticbrackets,especiallyindiagrams,i

35、nordertoimprovereadability.weusuallydenotetheinterpretationofacontextx1:a1,.,xn:anas(a1,.,an)insteadofx1:a1,.,xn:an. theemptycontextisinterpretedastheterminalobject1.theinter-pretationofatypeinacontext atype isgivenintheslicecategoryc/byanarrow,calledadisplaymap, ,x:a a wherewehereabbreviatedthename

36、ofthearrow.itsdomainistheinter-pretationofthecontext,x:a. aterminacontext t:a isinterpretedbyapointof(,a)intheslicec/ () t:abbbbbb=b ()(,a)xxxxxx axx inotherwords,aterm t:aisinterpretedasasectionoftheinterpre-tationof atype.normally,wewritejusttortinsteadof t:a. weinterpretsubstitutionsofatermaforav

37、ariablex, a:a,x:a btype ba/xtype a:a,x:a t:b ta/x:ba/x 7 image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computationa

38、l content, asindicatedinthefollowingpullbackdiagram: ()(,x:a)mmmiiiimmmiita/xmmmtiimmmiiiimmmiimmm(,x:a,b),ba/x_= ba/x,x:a ba()(,a) theinterpretationofadependentsumformedas ,x:a btype x:abtype isthecompositionofthearrows (,a,b) ,a b (,a) a ab () thisgivesusaconnectionbetweentheinterpretationofcontex

39、ts andde-pendentsums,becauseitmustbethecasethat,a,b=,x:ab. theinterpretationofanequalitytypeformedas s:a t:a eqa(s,t)type istheequalizerofsandt,asinthefollowingdiagram: (,eqa(s,t) eqa(s,t)()s t(,a) whensandtarethesameterm,theequalizeristrivialandwehave ,eqa(t,t)= fromthisweobtaintheinterpretationofa

40、re exivityterm t:a r(t):eqa(t,t) 8 image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, simplyasthe

41、identityarrow ()r(t)=1()=(,eq(t,t)a next,wegivetheinterpretationofthe rstandthesecondprojectionfromadependentsum.considertheterms p:x:ab p:x:ab 1(p):a 2(p):b1(p)/x weinterpret1(p)asthecompositionofarrows ()p(,a,b),a b(,a) and2(p)asinthefollowingdiagram:()nnnn2(p)nnnnnnp =(,b1(p)/x)_(,x:a,b) ,a b ()1

42、(p)(,a) thearrow2(p)istheuniquearrowobtainedfromtheuniversalpropertyofthedisplayedpullbackdiagram.adependentpairformedas a:a,x:a btype b:ba/x a,b :x:ab (,a,b) ,a bisinterpretedasthecompositionofbwiththetoparrowinthediagram(,ba/x)_b ba/x ()(,a) this completestheoutlineoftheinterpretationofdependentty

43、petheorywithandeqtypesina nitelycompletecategory. remark3.2itiswellknownthatcertaincoherenceproblemsarisewhenweinterpretdependenttypetheoryasabove.theproblemsarecausedbythefactthatingeneraltheresultofsuccessivepullbacksalongar-rowsg:bcandf:abisonlyisomorphictothepullbackalong 9 image factorizations

44、in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, thecompositiong f,whereasforacompletelywater-tightinterpretationequ

45、alityisrequired. thereareseveralstandardwaysofresolvingthisproblem,mostnotablybyinterpretingthetypetheoryinasuitable beredcategoryjac99,andthenapplyingtechnicalresultspertainingtothesehof95.wedonotwishtoobscuremattersbyemployingsuchtechnicaldevices.theinterestedreadermayeithertranslateourpresentatio

46、nintoasuitable beredsetting,orassumesomeotherremedy,suchasmakingacoherentchoiceofpullbacks.(forthesyntacticcategoryinsection3,suchpullbackscanbechosensimplyassubstitutions.) wenowproceedwiththeinterpretationofbrackettypes.aregularcategorychasstableregularepimonoimagefactorizations.everyarrowf:abcanb

47、efactoreduniquelyuptoisomorphismasaregularepifollowedbyamono af eeeeeebyyyyyy im(f) thefactorizationisobtainedbytakingthecoequalizerqofthekernelpair(1,2)off,asinthefollowingdiagram: aba1 2addddqddfbzzzzzzi im(f) thearrowi:im(f)bexistsandisuniquewithi q=fbecausefcoequalizesitsownkernelpair.itcanmoreo

48、verbeshownthatiisalwaysmonic. abrackettype atype atype isinterpretedastheimageof a: (,a),a=im( a)oooooooooo a aooooooo () 10 image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. this unary type constructor a has turne

49、d up previously in a syntactic form as a way of erasing computational content, theregularepipartofthefactorizationisusedintheinterpretationoftermbracketing a:a a:a theinterpretationofaisthecomposition ()a(,a) (,a) itremainstointerpretthewhereterms.consider q:a,x:a b:b,x:a,y:a b=by/x:b bwherex=q:b th

50、evarioustermsandtypesoccurringaboveareinterpretedinthesliceover,asshowninthefollowingdiagram: (,x:a,y:a)x (,a)q()(,a)iiwiiwwiiwwiiwwiwbiiiw(bwherex=q)i (,a,b) byassumption,thearrowlabelledbcoequalizesthetwoprojections.theregularepi isthecoequalizerofthosetwoprojections,therefore bfactorsuniquelythro

51、ugh via.theinterpretationof(bwherex=q)isthecomposition q. theorem3.3theinterpretationofbrackettypesinregularcategoriesissound. proof.weomittheroutineproofofsoundnessoftheinterpretationofdependentsumsandequalitytypes,andconcentrateontheinterpretationofbrackettypes.weneedtoverifytheequalityrule,twocon

52、versionrules,thesubstitutionrulesandthecompatibilityrules. whentheequalityruleistranslatedintothesemantics,itstatesthatthearrowspandqinthefollowingdiagramareequal: ()(,a)eeeeeee a=eeeeeep () 11 image factorizations in regular categories are stable under pullbacks, so they model a natural modal opera

53、tor in dependent type theory. this unary type constructor a has turned up previously in a syntactic form as a way of erasing computational content, sincepandqaresectionsofthemono atheymustbeequal.next,considerthe-rule bwherex=a therelevantdiagramis jjjjjjj (bwherejbjjjj(,a,b)(,a)=ba/x.(,a)a()x=a) th

54、earrowistheuniquefactorizationofbthrough .byconstruction,thelower-lefttrianglecommutes,andtheright-handarrowisde nedtobethecomposition a,whichimpliesthattheupper-righttrianglecommutes.thisispreciselywhatthe-rulestates. toverifythe-rule bx/uwherex=q weconsiderthefollowingdiagram: (,x:a) =bq/u kkkkkkkkkbx/ukkkk(,u:a)bq (,a,b)(bx/uw()wherex=q) thearrowbx/uisthecompositionof andb.thereisauniquefactorizationofbx/uthrough ,andtheinterp