DOC

Relative Properties of Frame Language

By Juanita Carter,2014-09-22 16:10
14 views 0
Relative Properties of Frame Languageof,Frame,frame

    Relative Properties of Frame Language

V01.14No.4J.Comput.Sci.&TechnolJuly1999

    ;RelativePropertiesofFrameLanguage

    ;FUYuxi(傅育熙)

    ;DepartmentolComputerScience,ShanghaiJiaoTongUniversity,Shanghai200030,P.R.China

    ;ReceivedNovember25,1997;revisedmay6,1998.

    ;AbstractThepaperdiscussessemanticsofencodingsinlogicalframeworks ;whereequalitiesinobjectcalculiarerepresentedbyfamiliesoftypesLsthecasein

    ;ELFThenotionofLeibnizequalityinacategoryisintroduced.Twomorphismsin

    ;acategoryareLeibnizequaliftheyareseensobyaninternalcategory.Theusual ;categoricalpropertiesarethenrelativizedtor-propertiesbyrequiringmediating

    ;morphismstobeuniqueuptosomeLeibnizequality.Usingtheseterminologies,

    ;itisshown,byanexample,thatthetermmodeloftheencodingofanadequately ;representedobjectcalculusisr.isomorphictothetermmodeloftheobjectlanguage.

    ;Keywordslogical~amework,categoricalsemantics,syntacticaladequacy ;1Introduction

    ;Alogicalframeworkisatypedcalculusinwhichothertypedcalculiorlogicsformulated

    ;astypedcalculicanbefaithfullyrepresented[1,2J.Atypica1situationgoeslikethis:onefrst

    ;givesatypetheoreticalformulationofanobjectlanguage;onethendevisesasignaturethat

    ;codesuptheconstantsandoperatorsofthelanguage;finallyoneprovesanadequacytheorem

    ;statingthatwhathasbeenencodedisafaithfu1representationoftheobject1anguage.Inthis

    ;coding-upprocess,therearetwoimportantquestions.Oneishowthevariablesoftheobject

    ;languagearerepresentedinthelogicalframework.Themostwidelyadoptedapproachisthe

    ;oneusedbyMartinLSf.whichistoidentifythevariablesoftheobject1anguagewiththose

    ;oftheframework.?

    cal1itthevariableconvention.Theviewtakenbythisapproach ;isthattheobjectlanguageisasublanguageofthelogicalframeworkenrichedwiththe

    ;encoding.Thisintensionalattitudedoesnotautomaticallyguaranteethefaithfulnessofany

    ;encodingofcourse.Theotherquestionishowequalityinanobjectlanguageisinterpreted

    ;intheframework.Onewayistoformulatethedefinitionalequalityofanobjectcalculusin

    ;termsofthedefinitionalequalityoftheframework.Wewillcallittheequalityconvention.

    ;ThisiswhatisusedindefiningamonomorphicMartinL6ftypetheory.Theu

    nderlying

    ;ideaofthemethodisthattheframework,whenextendedwiththesignaturecodingupthe

    ;objectcalculus,isaconservatireextensionoftheobjectcalculus.Insummary,theanswers

    ;tothetwoquestionsarebasedupontheviewthattocodeupanobject1anguageistoenrich

    ;theframeworkwithasignaturesothatthelatterbecomesaconservativeextensionofthe

    ;former.Theadequacytheoremassuresusthatourintensionisfulfiled. ;Themodeltheoreticalimplicationofthevariableandequalityconventionsisinvestigated

    ;inI31.Itispointedoutinthatpaperthatamodelofanadequatelyrepresentedcal

culusis

    ;notonlyafullsubmodelofamodelofthelogicalframeworkbutalsoaninternalmodelin

    ;thelattermode1.Tocapturethisdoublerelationship,internaldefinabilityisintroducedin

    ;loc.cit.asanotionthatcharacterizestherelationship.Thisnotionamountstoidentifying

    ;aninternalcategoryinthebasecategoryofthetermfibrationofthe1ogicalframeworkand

    ;relatetheexternalizationfibrationtothetermfibrationoftheobjectcalculusthrougha

    ;pullback.Itisfurthermoredemonstratedinf31thatifthemodelsofanobjectcalculuspos.

    ;sesscategoricalpropertyS,saycartesianclosedness,thentheidentifiedinternalcategoryhas

    ;SupportedbytheNationalNaturalScienceFundofChina,grantnumber69503006

    ;

    ;No.4RelativePropertiesofFrameLanguage32l

    ;internalpropertyS.Thesesemanticresultsdependheavilyonboththevariableconvention

    ;andtheequalityconvention.

    ;Whiletheredoesn’tseemtobeabetteralternativetothevariableconvention,there

    ;&regoodreasonsnottousetheequalityconvention.Inalogicalframework,typechecking

    ;issupposedtobedecidable.Ifonerepresentsthedefinitionalequalitiesofobjectcalculi

    ;by1udgementa1rulesoftheframework,thenoneneedstoreexaminetheprooftheoretical

    ;propertiesoftheframeworkwheneveroneformulatesanobjectlanguage.Thisisagainst

    ;theideaofa1ogica1frameworkbeingaonceforaUmechanismforproof.

    checking.Sofrom

    ;apragmaticpointofview,onehasreasonstopreferalogicalframework,say,in ;whichequalityofanobjectcalculusisrepresentedbyafamilyoftypes.Butwhatthenis

    ;themodeltheory?Aslightlydifierentquestionis:canwerecoverthesemanticresultsin

    ;3

    inthisnonextensionalsetting?Thispapergivesapositiveanswer.Thetrade-offisthat

    ;wewillhavetorelaxthenotionofcategorica1properties.

    ;ThelogicalframeworkweareusinginthispaperisELFasitsprooftheoryhasbe

en

    ;properlyinvestigated.

    ;2RelativeCategoricalStructures

    ;TheproductofAandBisanobjectA×BwithtwomorphismsA×B.A×BB ;suchthatforanypairofmorphismsCA.B.thereisauniquemediating ;morphismsCA×Bsatisfyingm;7r0=fandm;71-1=

    .Ifmisnotunique,A×Bis

    ;aweakproduct.Inatypicalsituationconsideredlateroninthispaper,eventhenotion

    ;ofweaklimitsdoesn’thelpfortheredoesn’tnecessarilyexistamorphismmrendering

    ;m;71-0=,andm;71-1=

    .Butthereisusuallyanequivalencerelationoneachrelevant ;homset.Continuingtheexampleofbinaryproducts.thereexistsamorphismCA×B

    ;thatisuniqueuptotheequivalencerelationonthehomsetHom(C,A×B)suchthat(i)

    ;m;71-0and,belongtothesameequivalenceclassonHom(C,A),and(ii)m;71-1and9belong

    ;tothesameequivalenceclassonHom(C,B).T’hismotivatesthefollowingdefinition.

    ;Definition2.1.SupposeCisacategory.0isaclassofobjectsofCandacla88o

f

    ;binaryrelations{

    (generaldefinitionofsuchfunctorsdoesn’tseemplausibleas

    ;theireffectsonmorphismsarehardtodefine.Butthingsaremuchbetterinternally.Now

    ;fixaclassOofobjectsofCandanequivalencerelationforO.Intherestofthis

    sec.

    ;tion.weassumethatalltherelevantobjectsullbackofd0(d1)along ;dl(d0);(ii)the(co)domainofthecompositionofapairof ;composablearrowsisthe(co)domainofthefirst(second) ;arrow:7;do=H0;doand7;dl=?1;dl;(iii)id;do=id;dl=Idc0;(iv)idisaunitfor ;composition:(idx0Idc1);y一?1and(Idcl×0id);

    yHo;and(v)compositionisassociative:

    ;(×dc1);

    (Idc1×);.SupposeCandDaretwointernalr-categoriesinC.Aninternal ;

    functorFfromCtoDconsistsoftwomorphismsF0:C0D0andF1:C1D1suchthat

    ;(i)F0=Fx;d;(ii)d};F0=F1;d;(iii)idc;F1F0;idD;(iv)7c;F1

    F1XoF1;7D.

    ;LetGbeanotherinternalr.functorfromCtoD.

    ;:FGisamorphism:C0}Dlsuchthat

;Aninternalrnaturaltransformation

    ;(i);d=Fo;(ii);dP=Go;(iii)

    ;.1|#T?,,n,,

    ;

    ;322J.Comput.Sci.&TechnolVo1.14 ;(F1,d};)0;D(doC;,G1)0;D.Wethereforehavea2-categoryCat(C)ofinternal

    r

    ;categoriesinC.Thistwocategoricalstructureallowsustodefineinternaladju

    nctionsin

    ;thestandardway.AninternaladjunctionconsistsoftwointernalfunctorsF:CDand

    ;G:DCandtwointernalnaturaltransformationsE:FG=IdDand

    :Idc=GF

    ;IdId

    ;hasaninternalrightradjoint,whereTer

    ;suchthat(i)(Go;,E;G1)o;Go;idcand

    ;(ii)(;F1,Fo;E)0;,-yFo;idD.Everyobject ;inCgivesrisetoaninternalcategory

    ;A(,,,IdA,IdA,IdA,IdA,IdA,IdA) ;whoseonlymorphismsareidentities.Anin

    ;ternalcategoryChasinternalterminalob

    ;{ectiftheuniqueinternalfunctorC1-er

;istheterminalobjectinC.Chasinternalr

    ;productsiftheinternaldiagnal

    functor(Ac0,Ac1):cc×chasaninternalrightadjoint

    ;×.chaLsinterna1exp.nentia1siftheintema1funct.rCoxc’.’;rC

    ;oxchasan

    ;internalrightradjoint,whereiistheinternalinclusionrfunctor(Idc.,idc)fromCotoc.

    ;FinallyCisaninternalCCCifithasinternalterminalobject,internal

    productsand

    ;internalrexponentials.

    ;3LeibnizEquality

    ;LetCbeacategorywithfiniteproductsandOaclassofobjectsinC.

    ;Definition3.1.SupposePBisamorphisminC.AtBequalityfor0isa ;classfxXB}x?

    oofmorphismsindexedbytheobjectsin0satisfyingthefollowing

    ;conditions:

    ;(i)Reflexivity:ForX?0,Ax;=factorsthroughtBwhere?

    thediagnalmor

    ;phism;

    ;(ii)Symmetry:ForX?0,(71-1,7tX?0,aresaidtobe

    ;tBequal,notationf=tBg,(f,9);=,0ctorsthroughtB. ;Proposition3.3.SupposePtB>.Bis0morphisminCand{×B}x?ois0

    ;tBequalityfor0.Then=tBisanequivalencerelationfor0. ;GivenaLeibnizequahtyinaparticularcategory,therecould ;lationsdefinedfromit.WewillseeanexampleinSection5. ;SomeLeibnizequalitiesaxestrongenoughtoreflecttheexternal ;equality.

    ;Definition3.4.eLeibnizequality=tBextensionalthe

    ;diagram0nthevightsapullback/orallX?0.

    ;Clearly,if=tBisextensional,thenf=tB9ifandonlyiff=9. ;Thenicethingaboutextensionalequalitiesisthattheyallowus ;totalkabouttheexternalequalityininternallogic. ;4AnExampleEncoding

    ;bemanyequivalencere

    ———B

    ;=tB

    ;Weassumethereaderisfamiliarwiththesyntaxofthesimplytypedcalculus

    where

    ;(T).Hx:().prf(app.(abs,f)x=fx)

    ;eta:Ha:T.?T:T.nf:()}(T).prf(abs,(z:().app.fx)=f)

    ;surp:Ha:T.?T:T.Hx:t(aAT).prf(pair”(p0a’rx)(pla’rx):Az)

    ;pi0:Ha:T.?T:T.IIx:t(a).IIy:t(r).prf(poa~-(pair”xy)=z)

    ;pi1:Ha:T.?T:T.?z:().?:(T).prf(pla~-(pairxy)=Y)

    ;unit:IIx:t(o).r,,-f(x=o)

Report this document

For any questions or suggestions please email
cust-service@docsford.com