D &243;&242; &243; &242; &236;&24(3)

Byinspectionofthelexicalunfoldingrules,itcanbeobservedthatev-eryotherplus-nodeinaspanninglinkagehaseitheronenegativeoccur-renceoristheplus-daughterofonelambda-node,butnotboth.Sotheothershaveanin-degreeof1.

Inanon-spanningsublinkage,itcanhappenthataplus-nodeinthesublinkagehasanegativeoccurrence,butthenegativeoccurrencefallsoutsidethesublinkage.IntheLC-graphforthissublinkage,thisplus-nodehasanin-degreeof0.Byde nition,ifaplus-daughterisinasublinkage’sLC-graph,thensoisitslambda-nodeparent.

Proposition4.2ForeveryLC-graph,everyminus-nodeeither:

(i)isaminus-daughterofalambda-node,inwhichcaseithasanin-degreeof2,or

(ii)hasanin-degreeof1.

Proof.Byinspectionofthelexicalunfoldingrules,itcanbeobservedthateveryminus-nodeappearsinthelabelofoneaxiomaticformula.Sincealinkagemustbeacompletematchingofaxiomaticformulaebyaxiomlinks,everyminus-nodereceivesoneincomingarcfromanaxiomlink.Minus-daughtersadditionallyreceiveoneincomingarcfromtheirlambda-nodeparents.

Wesaythatanodeisarootnodeinalinkageiffithasanin-degreeof0inthatlinkage’sLC-graph.ByPropositionrootnodesarealwaysplus-nodes.Ifitlabelsapositiveterminalformula,thenindeferencetoPropo-sitionwecallitaproperrootnodeinanylinkageinwhichitappears.Ifitisaplus-nodewhosenegativeoccurrencefallsoutsideasublinkage,thenwecallitanimproperrootnode.

Proposition4.3ForeveryLC-graph,everyminus-nodehasanout-degreeof0.

Proof.Allarcspointfromaplus-nodetoeitheraminus-nodeoraplus-node.Minus-nodescorrespondtolabelsofterminalformulaearisingfromsequentpremisesandtoboundvariablesoflambda-terms.Theseareneverredexesforsubstitution.

A graph-theoretic construction for representing the derivational side-conditions in the construction of axiomatic linkages for Lambek proof nets is presented, along with a naive algorithm that applies it to the sequent derivability problem for the Lambek C

Proposition4.4ForeveryLC-graph,everylambda-nodehasanout-degreeof1or2.Inaspanninglinkage,everylambda-nodehasanout-degreeof2.Proof.Whetheralambda-nodehasanout-degreeof1or2dependsonwhetheroneorbothofitsdaughtersareinthelinkage.Ifthelinkageisaspanninglinkage,thenbothofitsdaughtersareinit.

Proposition4.5Inaspanninglinkage,everysimpleplus-nodehasanout-degreeofatleast1,i.e.,therearenoterminalplus-nodes.

Proof.Everysimpleplus-nodelabelsapositiveaxiomaticformula.Sincelinkagesarecompletematchingsofaxiomaticformulae,everypositiveax-iomaticformulahasanaxiomlink,fromwhicharisesintheLC-graphatleastoneoutgoingarcfromitsplus-nodelabel.

ByPropositioneverylambda-nodehasanout-degreeof1or2,sotherearenoterminalplus-nodes.

Simpleplus-nodeshaveunboundedout-degree.Thereasonforthisisthatsimpleplus-nodesowetheiroutgoingarcstoaxiomlinks.Axiomlinksmaptoallofthevariablesthatappearinthetermlabellinganegativeax-iomaticformula,andthereisnolimitonthenumberofvariablesinthatterm.Wecandistinguishoneparticularoutgoingarc,however:

Proposition4.6ForeveryLC-graph,everynon-terminalsimpleplus-nodehasexactlyoneoutgoingarctoaminus-node.

Proof.Thetermsthattheseaxiomlinksmaptocontainexactlyonefreeminus-node.Thiscanbeprovenbyinductiononthenumberoflexicalunfoldingstepsusedtoderivethem.Theonesthatwerecreatedbyapos-itiveunfoldingruleareminus-daughters,andthereforeconsistofasingleminus-node.Theonesthatwerecreatedbyanegativeunfoldingrulecon-sistofatermwithalowernumberoflexicalunfoldingstepsappliedtoanewplus-node.

4.2Paths

Proposition4.7ForeveryLC-graph,everypathbeginsataplus-nodeandpassesexclusivelythroughplus-nodes,terminatingateitheraplus-nodeoraminus-node.

Proof.AtrivialconsequenceofProposition4.3.

Proposition4.8Ifand

lambda-node,theneither,andisnottheminus-daughterofaor.

Proof.Ifisnotaminus-daughterofalambda-node,thenbyProposi-tion4.1andPropositionithasanin-degreeof1.Furthermore,byPropositioneveryintermediatenodeonthepathsandisaplus-node,andbyPropositionhasanin-degreeof1.

A graph-theoretic construction for representing the derivational side-conditions in the construction of axiomatic linkages for Lambek proof nets is presented, along with a naive algorithm that applies it to the sequent derivability problem for the Lambek C

Proposition4.9Givenaproperrootnode,thereisauniqueplus-nodela-bellinganaxiomaticformulawhichisaccessiblefromitbyapathpassingexclusivelythroughlambda-nodes.

Proof.Thisisthelabeloftheaxiomaticformulaobtainedbyfollowingthelexicalunfoldingofthepositiveterminalformulaalongitspositivedaugh-ters.

WecalltheaxiomaticlabelreferredtoinProposition4.9theaxiomaticre- ectionoftheproperrootnode.Ifapositiveterminalformulaisabasiccategory(andthusalsoanaxiomaticformula),thentheaxiomaticre ec-tionofitsproperrootnodeistheproperrootnodeitself.

4.3Correctness

Proposition4.10Ifaspanninglinkagesatis esI(2),thenitsatis esPN(2).Proof.SincetheLC-graphisacyclic,itsnodescanbetopologicallysorted.Ifwealwayschoosethemosthighlyrankedredexaccordingtothisordertoexpandnext,thentherankofthemosthighlyrankedredexstrictlyde-creasesateachstepofvariablesubstitution,andthusvariablesubstitu-tionterminates.

Proposition4.11Ifaspanninglinkagesatis esI(2)andI(3),thenitsatis- esPN(3).

Proof.GivenI(3),thereislikewiseanoccurrenceofin.Ifalsooc-curredoutside,thentherewouldbeapathfromsomeplus-node,suchthatneither(andthusexpandstoasubtermof)nor(withbeingasubtermoftheexpansionof).

ByPropositionthein-degreeofis2,withonearccomingfromitslambda-node,,andonearccomingviaanaxiomlinkfromsomeotherplusnode,.Ifthepathwerevia,thentherewouldbeapath

aswell.

Ifthepathpassedthrough,thentherewouldbeacycle

,whichisexcludedbyI(2).Thusthepathpassesthrough.Sinceisnotaminus-node,thenbyPropositionifthepathfromtopassesthrough,thenthereiseitherapathorapath,whichcontradictsourassumption.

Proposition4.12Ifaspanninglinkagesatis esI(1),thenitsatis esPN(1)andPN(4).

Proof.Ifthereisauniquenodewithin-degree0,thenbyPropositionthereisauniquepositiveterminalformula.Allnodesarepath-acc …… 此处隐藏：6022字，全部文档内容请下载后查看。喜欢就下载吧 ……