A proof of the church-rosser theorem for the lambd

AProofoftheChurh-RosserTheoremfortheLambdaCalulusinHigherOrderLogiPeterV.HomeierU.S.DepartmentofDefense,homeiersaul.is.upenn.edu~homeierAbstrat.ThispaperdesribesaproofoftheChurh-RossertheoremwithintheHigherOrderLogi(HOL)theoremprover.ThisfollowstheproofbyTait/Martin-Lof,preservingtheeleganeofthelassipresenta-tionbyBarendregt.Wemodelthelambdaaluluswithaname-arryingsyntax,asinpratiallanguages.Theproofissimpliedbyformingaquotientofthename-arryingsyntaxbythe-equivalenerelation,thusseparatingtheonernsof-equivaleneand-redution.1IntrodutionTheChurh-Rossertheoremstatestheonueneproperty,thatifanexpressionmaybeevaluatedintwodierentways,bothwillleadtothesameresult.Sinetherstattemptstoprovethisin1936,manyimprovementshavebeenfound,in-ludingtheTait/Martin-LofsimpliationandtheTakahashiTriangle.AlassipresentationmaybefoundinBarendregt[1℄.Theproofsinvolvesophistiatedindutivearguments,whosepatternshavealsointriguedresearhersinmehani-allyhekedproof.TherstmehanialproofwaspresentedbyShankar[9℄,andhasbeenfollowedbyHuet[5℄,Nipkow[7℄,Pfenning[8℄,Vestergaard/Brotherston[11℄,andFord/Mason[2℄.Ofthese,onlyNipkowextendstheworkbeyond-redutiontoproofsofonuenefor-and-redution.Onekeyissueintheseproofsiswhetherthesyntaxofthelambdaalulusisrepresentedusingnamesforvariables,oradeBruijnrepresentation,wherenumbersareusedfornames.ThedeBruijnsyntaxismoreagreeablefortheChurh-Rosserproof,asitevadestheproblemof-equivalene.However,thename-arryingsyntaxismorerealisti,asthisismorerepresentativeofpro-gramminglanguagesingeneraluse.Beauseofthegreaterfaility,manyofthemehanialChurh-RosserproofsmentionedproveonueneforthedeBruijnsyntax[5,7,8℄.However,asin[2℄,wewishtoaddresstheissuesofname-arryingsyntax,inordertorelatemorediretlytopratialprogramminglanguages.Thepreseneofnamesraisesaskeyissuesthedenitionsof-equivalene,substitution,and-redution.Intwooftheaboveproofswherenamesweretreated[9,11℄,onuenewasprovedforanarbitraryintermixtureof-and-redution.Thisintermixturebredanunfortunateomplexity.2P.V.HomeierTheelegantpresentationbyBarendregt[1℄axesthisomplexitybytheBarendregtVariableConvention(BVC).OuraimwastofollowBarendregtasloselyaspossible,inludingmehanizingtheBVC.Wedividedtheonsiderationof-and-redutionintotwolayers,forminganewmodelofthesyntaxasthequotientoftheoriginalname-arryingsyntaxdividedbythe-equivalenerela-tion.ThisquotientlayerisexatlyisomorphitothedeBruijnsyntaxandgreatlysimpliestheChurh-Rosserproof.ThisisthesameapproahasFord/Mason[2℄.Wefoundthattherewasatleastasmuhworkinvolvedinformingthequotientoftheoriginallanguageasinalltheremainingworkofprovingonuene.OurHOLproofofChurh-Rosserontains7maintheories,whihmake77denitionsandprove359theoremsin6minutes,54seondsona300MHzPentiumII.Theproofsheremayseemtobereasonedinnormallambdaalulus,butareatuallyinterpretationsoftheHOLtatisintomathematialEnglish.AfterprovingChurh-Rosserfor-redution,wetestedthelarityofthefoundationbyextendingthisworkintwoways:provingthediamondlemmabytheTakahashitriangle,andprovingChurh-Rosserfor-and-redution[1℄.Thersttookonehalfday,andtheseondtookfourdays.Spaepreludestheirpresentationhere,buttheHOLproofsareavailable[6℄.TheauthorwishestothankRandolphJohnson,BillLegato,BradMartin,SylvanPinsky,andFrankTaylorformanyhelpfulommentsandimprovements.2ThePre-LambdaCalulusWedenethepre-lambdaalulus(1),beginningwiththetypeofterms,term1.Thetypeofvariablesisvar.Wealsouse1toabbreviateterm1.Denition1.1::=varj11jvar:1Thisdenestermsinthelambdaalulusindutivelyaseitherbeingvari-ables,appliationsofatermrepresentingafuntiontoanothertermrepresentinganargument,orabstrationsoftermsbyavariable,whihrepresentfuntionsofoneargument.Thesetermsmaybeomparedforsyntatiequality(=).Wewilluset,u,e,M,andNastypialvariablesoftype1,w,x,y,andzastypialvariablesoftypevar,rforsetsofvariables,andsforsubstitutions.ThisdenitionisreatedintheHOLlogibytheodeval_=Hol_datatype‘term1=Var1ofvar|App1ofterm1=term1|Lam1ofvar=term1‘;Thisreatesterm1asanewonretereursivetypewithintheHOLlogi,andVar1,App1,andLam1asonstrutorfuntions.Whennoonfusionmayresult,wewillusexforVar1x,tuforApp1tu,andx:tforLam1xt.Whenterm1isreated,Holdatatypeautomatiallyprovesseveraltheoremsthatharaterizethebehaviorofvaluesofthisnewtyperegardingstruturalindution,funtionexistene,ases,andonstrutordistintivenessandone-to-oneproperties.TheChurh-RosserTheoreminHigherOrderLogi3Weusethefuntionexistanetheoremtodenethefollowingfuntionsbyprimitivereursion,byindutiononthestrutureofterms.Wehereusemaxasaninxoperatorthatyieldsthemaximumofitsarguments.Denition2(Heightofaterm).HEIGHT1(x)def=0HEIGHT1(tu)def=(HEIGHT1tmaxHEIGHT1u)+1HEIGHT1(x:u)def=HEIGHT1u+1Denition3(Freevariablesofaterm).FV1(x)def=fxgFV1(tu)def=FV1t[FV1uFV1(x:u)def=FV1ufxgWeexpresspropersubstitutiononatermusingexpliitsimultaneoussubsti-tutions,asaseparatedatastruture.Theseombineanitenumberofindividualsubstitutionsofexpressionsforvariablesintoonesubstitution,whereallareap-pliedsimultaneously.Theatualappliationofasubstitutiontoanexpressionisdonebyversionsofthe