The Royal Swedish Academy of Sciences(16)

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,

Proof.Inordertoprovethetheoremwe buildasyntacticcategorySfromthedependenttypetheoryDwith1,,Eq,and[ ]types.WethenshowthatSisaregularcategory,andthattheinterpretationofDinSvalidatespreciselyalltheprovableequationsbetweenterms.

TheobjectsofSaretheclosedtypesofD.ThearrowsfromaclosedtypeAtoaclosedtypeBarerepresentedbyterms

x:A t:B

wheretwosuchtermssandtrepresentthesamearrowif,andonlyif,Dprovesthattheyareequalx:A s=t:B(sinceweareworkingwithextensionalequalityitdoesnotmatterwhichsenseof‘equal’wetake).Furthermore,twotermsinacontextwillbeconsideredequalifwecanobtainonefromtheotherbyrenamingboundandfreevariablesinacapture-avoidingway.

Thecompositionofarrowsx:A t:Bandy:B s:Cisthearrowx:A s{t/y}.Thatcompositioniswell-de nedandassociativefollowsfromthepropertiesofsubstitution.TheidentityarrowonAisrepresentedbyx:A x:A.

Sincetermsrepresentingthesamearrowmustbeprovablyequal,itsuf- cestoshowthatSisregular.Letusprove rstthatithas nitelimits.Theterminalobjectis1.Indeed,foranytypeAwehaveanarrowx:A :1,andforanyotherarrowx:A t:1wehavex:A t= :1bytheequalityaxiomfortheunittype.Itisfairlyeasytoverify thatShasbinaryproducts:theproductofAandBisthetypeA×B=x:AB.

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科The Royal Swedish Academy of Sciences(16)全文阅读和word下载服务。