A Logic for Contracts

UNIVERSITY

OF TRENTO

DIPARTIMENTO DI INGEGNERIA E SCIENZA DELL’INFORMAZIONE

38050 Povo – Trento (Italy), Via Sommarive 14

http://www.disi.unitn.it

A LOGIC FOR CONTRACTS

Massimo Bartoletti and Roberto Zunino

June 2009 (submitted), November 2009 (revised)

Technical Report #DISI-09-034

Massimo Bartoletti

DipartimentodiMatemati aeInformati a UniversitàdegliStudidiCagliari,Italy

Roberto Zunino

DipartimentodiIngegneria eS ienzadell'Informazione UniversitàdegliStudidiTrento,Italy

Abstra t

We investigatethelogi al foundationsof ontra ts indistributed ap-pli ations. A ontra t is anagreement stipulated between twoor more parties, whi hspe ies theduties and the rightsof the partiesinvolved therein.Wemodel ontra tsasformulaeinanintuitionisti logi extended witha ontra tualformofimpli ation

։

.Thissupportsforavariantof ModusPonens,wherefromapromise

a

։ b

todedu e

b

,onedoesnot needtoknow

a

;yet, itsu estohaveadualpromise

b

։ a

. Westudy theprooftheoryforourlogi . Inparti ular,weprovideitwitha Hilbert-styleaxiomatisation,whi hisshown onsistent,andwithaGentzen-style sequent al ulus, shownequivalentto theaxiomatization. We proveour logi de idable,viaa uteliminationproperty. Therightsandtheduties derivingfromanysetof ontra ts anthereforebeme hani allyinferred.

1 Introdu tion

Se urity,trustworthinessandreliabilityofsoftwaresystemsare ru ialissuesin therisingInformationSo iety. As newonlineservi es(e- ommer e,e-banking, e-government, et .) are made available, the numberand the riti ality of the problems relatedto non-fun tional properties ofservi eskeepsgrowing. From the lient pointof view, it isimportant to be surethat, e.g.,after apayment hasbeenmade,theneitherthepayedgoodsaremadeavailable,orafullrefund isissued. Fromtheproviderpointofviewitisimportanttobesure,e.g.,thata lientwillnotrepudiatea ompletedtransa tion,sotoobtainforfreethegoods alreadydelivered. Inotherwords,theintera tionbetweena lientandaservi e mustberegulatedbyasuitable ontra t,whi hguaranteesto bothpartiesthe propertiesondemand. The ru ialproblem is thenhowto dene the on ept of ontra t,and howto a tually enfor e it, in anenvironment-the Internet -whi hisbydenitionopenandunreliable.

Unfortunately,atthepresentnowidespreadte hnologyseemstogivea gen-eralsolutiontothisproblem. Typi ally,servi esdonotprovidethe lientwith any on reteguaranteeaboutthea tualfun tionalitytheyimplement. Atbest, theservi eprovider ommitshimselftorespe tsomeservi elevelagreement.

stepsagainsttheprovider(orvi eversa). Althoughthisisthenormalpra ti e nowadays,it ishighlydesirableto reversethis trend. Indeed, both lientsand servi es ouldin urrelevantexpenses duetotheneededlegaldisputes. Thisis impra ti al,espe iallyfortransa tionsdealingwithsmallamountsofmoney.

Contributions. Westudythetheoreti alfoundationsuponwhi h onstru t-ingaservi einfrastru turewhere ontra ts arry,besidestheusuallegal mean-ing, also a formal one. In other words, our ontra ts will be mathemati al entities, that spe ify exa tlythe rightsand theduties of lients and servi es. We envisage a world of servi es where lients and servi e providers anhave pre ise, mathemati al guarantees aboutthe implemented features, and about the assumedside onditions. In thes enarioweaim at, ontesting a ontra t willnotne essarilyrequiretoresorttoa ourt,yetitwillbeaneventmanaged automati ally,deterministi allyandinexpensively,bytheservi einfrastru ture itself. We allthisintera tion paradigm ontra t-based omputing.

In this paper we begin ourinvestigation on ontra t-based omputing, by studyingformalismstodes ribe ontra ts,andtoreasonaboutthem. A ontra t is a binding agreementbetween twoor more parties, that di tates the duties theinvolvedpartiesmustfulll,wheneversomepre onditionsaresatised. Our theory of ontra ts will be able to infer, in ea h possible ontext, the duties derivingfromagivensetof ontra ts. Toputthedevelopedtheoryatwork,we haveimplemented aproof sear h tool, whi h de ideswhether agiven formula isatautologyornot[26℄.

Summary. Thepaperisorganizedasfollows:

•

InSe tion2wegive,withthehelpofanexample,somemotivationsabout theneedforalogi for ontra ts.

•

InSe tion3wedeviseaminimalset of propertieswhi hare desirablein anylogi alformalizationof ontra ts.

•

In Se tion 4 we dene our logi for ontra ts, through a Hilbert-style axiomatization. Ourlogi satises allthe properties identied aboveas desirable.

•

InSe tion5wegivefurtherdetailsandexamplesaboutusingourlogi to modelavarietyof ontra ts.

•

InSe tion 6weprovide ourlogi with aGentzen-stylesequent al ulus, whi hisequivalentto theHilbert-styleaxiomatization.

•

InSe tion7weprovethemainte hni alresultaboutourlogi ,thatisits de idability. Thisisobtainedbyshowingthatoursequent al ulusenjoys uteliminationandthesubformulaproperty.

•

InSe tion 8 we study relations with other logi s, in parti ular with in-tuitionisti propositional logi IPC, with the modal logi S4, and with propositionallaxlogi .

•

In Se tion 9 we extend our logi with an indexed modality, to model prin ipals. Contra t agreements then ome in a ri her avour, be ause ofthe bindingbetweenthe ontra tingparties and their inferred duties, whi hisnowrevealed.

•

InSe tion 10wedis usssomerelatedwork.

•

InSe tion 11 we on lude, bydis ussing some possible future work and extensionsto ourlogi .

2 Motivations

Suppose thereare twokids, Ali eand Bob,who want to playtogether. Ali e hasatoyairplane,whileBobhasabike. BothAli eandBobwishtoplaywith ea h other's toy: Ali e wantsto ride Bob'sbike, and Bob wantsto play with Ali e'sairplane. Ali eandBobareverymeti ulouskids,sobeforesharingtheir toys,theystipulatethefollowinggentlemen'sagreement:

Ali e: I willlend myairplanetoyou,Bob,providedthat Iborrowyourbike. Bob: Iwilllend mybiketoyou,Ali e,providedthat Iborrowyourairplane. Wewanttomakepre isethe ommitmentsex hangedbyAli eandBob,so to beableto formallydedu ethat Ali eand Bob willindeed share theirtoys, providedtheyarerealgentlemen whoalwaysrespe ttheirpromises.

Letuswrite

a

fortheatomi propositionAli elendsherairplaneand

b

for Boblendshisbike. Using lassi alpropositionallogi ,astraightforwardyet naïveformalizationoftheabove ommitments ouldbethefollowing. Ali e's ommitment

A

isrepresentedastheformula

b

→ a

(ifBob lendshisbike,then Ali elendsherairplane)andBob's ommitmentastheformula

a

→ b

(ifAli e lends herairplane,thenBoblendshis bike):

A = b → a

B = a → b

where the symbol

→

denotes lassi alimpli ation. Under thehypothesis that Ali eandBobalwaysrespe ttheirpromises,bothformulas

A

and

B

aresound withrespe ttoours enario. Fortheformula

A

,itistruethatwhenever

b

holds (Bob lends his bike),then

a

will also hold (Ali elends her airplane). Forthe formula

B

, it is truethat whenever

a

holds (Ali elends her airplane), then

b

willalsohold (Boblendshisbike).

So, why are we unhappy with the above formalization? The problem is that,in lassi alpropositionallogi ,theabove ommitmentsarenotenoughto dedu ethatAli ewilllendherairplaneandBobwilllendhisbike. Formally,it ispossibletomaketruetheformula

A∧B

byassigningfalsetobothpropositions

a

and

b

. So,Ali e and Bob will notbeable to play together, despiteof their gentlemen'sagreement,andofthehypothesisthattheyalwaysrespe tpromises. The failure to represent s enarioslike the one aboveseems related to the standardinterpretationoftheModusPonens. Inboth lassi aland intuition-isti prooftheories,theModusPonensruleallowsto dedu e

b

whenever

a

→ b

and

a

aretrue. Ba kto ours enario,we oulddedu ethatBoblends hisbike, but only after Ali e has lent Bob her airplane. One of the twoparties must

imply thepromised duties. In alogi formutual agreements,we would like insteadtomakeanagreementbe omeee tivealsowithouttheneedofsome partytakingtherststep(asweshallseeinawhile,su hpartymightnoteven exists in more omplexs enarios). That is,

A

and

B

are ontra ts,that on e stipulatedimplythedutiespromisedbyalltheinvolvedparties.

Te hni ally, we would like our logi ableto dedu e

a

∧ b

whenever

A ∧ B

is true. As we havenoti ed above, this does nothold neitherin lassi alnor in intuitionisti propositionallogi ,where thebehaviourofimpli ation stri tly adheresto ModusPonens.

Tomodel ontra ts,weextendtheintuitionisti propositionallogi IPC[30℄ with a newform of impli ation, that we denote with the symbol

։

. The re-sulting logi is alled PCL, forPropositionalContra tLogi . Forinstan e, the ontra tde lared byAli e, I will lendmyairplaneto Bobprovidedthat Bob lends hisbiketome,will bewritten

b ։ a

. Thisform of,say, ontra tual im-pli ation,isstrongerthanthestandardimpli ation

→

ofIPC. A tually,

b ։ a

implies

a

not only when

b

is true, like IPC impli ation, but also in the ase that a  ompatible ontra t, e.g.

a ։ b

, holds. In our s enario, this means that Ali e willlend her airplaneto Bob,provided that Bob agrees tolend his bike to Ali e wheneverhe borrows Ali e's airplane, and vi e versa. A tually, thefollowingformulaisatheorem ofourlogi :

(b ։ a) ∧ (a ։ b) → a ∧ b

Inotherwords,from thegentlemen'sagreement stipulatedbyAli eandBob, we an dedu ethat thetwokidswillindeed sharetheirtoys.

Tomakeours enarioabit moreinteresting,supposenowthat athirdkid, Carl,joins Ali eand Bob. Carl hasa omi book,whi h hewould share with Ali e and Bob, provided that he an play with the other kids' toys. To a - ommodate their ommitments to the new s enario, the three kids de ide to stipulatethefollowinggentlemen'sagreement(whi hsupersedestheoldone): Ali e: I will share myairplane,providedthat I anplaywith Bob'sbikeand

readCarl's omi book.

Bob: I willshare my bike,providedthat I anplaywithAli e's airplaneand readCarl's omi book.

Carl: Iwillsharemy omi book,providedthatI anplaywithAli e'sairplane andrideBob'sbike.

Let us write

a

for Ali e shares her airplane,

b

for Bobshares his bike, and

c

for Carlshares his omi book. Then, theabove ommitments anbe rephrasedas: Ali epromises

a

providedthat

b

and

c

,Bobpromises

b

provided that

a

and

c

,andCarl promises

c

providedthat

a

and

b

. Inour ontra tlogi , wemodeltheaboveagreementastheformula

A ∧ B ∧ C

,where:

A = (b ∧ c) ։ a

B = (a ∧ c) ։ b

C = (a ∧ b) ։ c

The proof systemof ourlogi will be ableto dedu e that the three kids will indeed sharetheirtoys,thatis, thefollowingis theoremofthelogi :

pli ation,withaspe i ationwhi huses,instead,standardimpli ation. Let:

A

′

= (b ∧ c) → a

B

′

= (a ∧ c) → b

C

′

= (a ∧ b) → c

Clearly,in this asewe annotdedu e

A

′

_{∧ B}

′

_{∧ C}

′

_{→ a ∧ b ∧ c}

. Thiss enario provideuswithafurtherinsightabout ontra tualimpli ation. Re onsiderfora momentthes enariowithonlytwo ontra tingparties,modelledwithstandard impli ation:

(a → b) ∧ (b → a)

. Wehaveshownabovethat,insu hasituation, asingleparty anmaketheagreementee tive,e.g.Ali e antaketherststep, andlendherairplanetoBob(then,byModusPonens,Bobwilllendhisbiketo Ali e). Instead,intheextendeds enario(modelledwithstandardimpli ation), it is nolonger the ase that asingle party antakethe rst stepand a hieve thesamegoal. Forinstan e,assumethatAli ede idesunilaterallytoshareher airplane. Evenbydoingthat,Ali ewillhavenoguaranteethat,eventually,she will beable to playwith theother kids' toys. This is be ause, withstandard impli ation,setting

a

totruewouldtransform

A

′

_∧B

′

_∧C

′

into

(c → b)∧(b → c)

, whi h learlyimpliesneither

b

nor

c

. Tomaketheiragreementee tive,atleast twoofthethreepartiesmustuse ontra tualimpli ationin their ommitments (whiletheotherone an usestandardimpli ation).

Thisobservation anbegeneralisedtoas enariowith

n

ontra tingparties, whereone anshowthatatleast

n−1

partiesmustuse ontra tualimpli ation.

3 Desirable properties

Wenowdis usssomedesirablepropertiesofalogi for ontra ts,aswellassome other properties that instead areundesirable. Inthe nextse tion, we will showanaxiomatisationthatenjoysallthepropertiesmarkedhereasdesired.

As shown in the previousse tion, a hara terizingpropertyof ontra tual impli ation is that of allowing two ontra ting parties to handshake, so to maketheiragreementee tive. This is resumed bythe followinghandshaking property,whi hweexpe tto holdforanylogi for ontra ts:

(p ։ q) ∧ (q ։ p) → p ∧ q

(1)

Ageneralisationoftheabovepropertytothe aseof

n

ontra tingpartiesis alsodesirable. Itisasortof ir ular handshaking,wherethe

(i + 1)

-thparty, in order to promise some duty

pi+1

, relies on a promise

pi

made by the

i

-th party. Inthe aseof

n

parties,wewouldexpe tthefollowing:

(p1

։

p2) ∧ · · · ∧ (pn−1

։

pn) ∧ (pn

։

p1) → p1

∧ · · · ∧ pn

(2)

Asa on reteexample, onsiderane- ommer es enariowhereaBuyer an buy items froma Seller,and paythem througha redit ard. Tomediate the intera tion between theBuyerand theSeller, there is aBank whi h manages payments. The ontra tsissuedbythethreeparties ouldthenbe:

Buyer: Iwill li kpay providedthat theSellerwillshipmyitem Seller: I willshipyouritemprovidedthat Igetthemoney

Letthe atomi propositions

ship

,

clickpay

, and

pay

denote respe tivelythe fa tsSellershipsitem,Buyer li kspay,andBanktransfersmoney. Then, thethree ontra tsabove anbemodelledasfollows:

Buyer

= ship ։ clickpay

Bank

= clickpay ։ pay

Seller

= pay ։ ship

Then,bythehandshakingproperty(2),weobtainasu essfultransa tion:

Buyer

∧ Bank ∧ Seller → pay ∧ ship

Notethat,inthespe ial asethat

n

equals

1

,theabove ir ular handshak-ingpropertyturnsinto aparti ularlysimpleform:

(p ։ p) → p

(3)

Intuitively,(3) anbeinterpretedasthefa tthatpromising

p

providedthat

p

, implies

p

(a tually,alsothe onverseholds,sothatpromiseisequivalentto

p

). Ageneralisationofthes enarioofthepreviousse tiontothe aseof

n

kids is alsodesirable. It isasort ofgreedy handshakingproperty, be ause nowa partypromises

pi

onlyprovidedthatall theotherpartiespromisetheirduties, i.e.

p1, . . . , pi−1, pi+1, . . . , pn

. Thegreedyhandshaking anthenbestatedas:

^

i∈1..n



(p1

∧ . . . ∧ pi−1

∧ pi+1

∧ . . . ∧ pn) ։ pi



→ p1

∧ · · · ∧ pn

(4)

As shown by (1), a ontra t

p ։ q

be omes ee tive, i.e. implies the promise

q

, when itis mat hed bya dual ontra t

q ։ p

. Evenmore dire tly,

p ։ q

should beee tivealsointhe asethat thepremise

p

isalreadytrue:

p ∧ (p ։ q) → q

(5)

Inotherwords, ontra tualimpli ationshouldbestronger thanstandard impli- ation,i.e.weexpe t thatthefollowingisatheoremofanylogi for ontra ts:

(p ։ q) → (p → q)

(6)

Ontheotherhand,wedonotwantthat alsothe onverseholds, sin ethis wouldequatethetwoforms ofimpli ation:

(p → q) → (p ։ q)

NOTATAUTOLOGY

Wewant ontra tualimpli ationtosharewithstandardimpli ationa num-berproperties. Wedis usssomeofthembelow. First,a ontra tthatpromises true (written

⊤

) is always satised, regardlessof the pre ondition. Then, we expe t thefollowingtautology:

p ։ ⊤

(7)

However,dierentlyfromstandardimpli ation,wedonotwantthata on-tra twithafalsepre ondition(written

⊥

)alwaysholds.

Soseewhy,assumethatwehave

⊥ ։ p

asatautology,forall

p

. Then,itwould alsobethe asefor

p = ⊥

,andsobythebinaryhandshakingpropertywewould dedu ea ontradi tion:

(⊥ ։ ⊥) ∧ (⊥ ։ ⊥) → ⊥

.

Anotherpropertyofimpli ationthat wewantto preserveistransitivity:

(p ։ q) ∧ (q ։ r) → (p ։ r)

(8)

Ba k to ourprevious example,transitivity would allow the promiseof the Buyer

(ship ։ clickpay)

and the promise of the Bank

(clickpay ։ pay)

to be ombinedinthepromise

ship ։ pay

.

Contra tualimpli ationshouldalsoenjoyastrongerformoftransitivity. We illustrate itwith thehelp ofanexample. Supposeanair-ight ustomerwants tobookaight. Todothat,heissuesthefollowing ontra t:

Customer

: bookFlight ։ pay

The ontra tstates that the ustomer promises to pay the required amount, providedthatheobtainsaightreservation. Supposenowthatanairline om-pany startsa spe ial oer, in theform of afree drinkfor ea h ustomer that makesareservation:

AirLine

: pay ։ bookFlight ∧ freeDrink

Of ourse,thetwo ontra tsshouldgiverisetoanagreement,be ausetheairline ompanyis promising abetter servi e thanthe one required be the ustomer ontra t. Toa hievethat,weexpe ttobeabletoweaken the ontra tofthe airline ompany,tomakeitmat hthe ontra tissuedbythe ustomer:

AirLine

→ (pay ։ bookFlight)

Alternatively,one ouldmakethetwo ontra tsmat hby makingstronger thepre onditionrequiredbythe ustomer, thatis:

Customer

→ (bookFlight ∧ freeDrink ։ pay)

Morein general,wewantthefollowingtwopropertiesholdforanylogi for ontra ts. They say that the promise in a ontra t an be arbitrarily weak-ened(9),whilethepre ondition anbearbitrarilystrengthened(10).

(p ։ q) ∧ (q → q

′

_{) → (p ։ q}

′

₎

(9)

(p

′

→ p) ∧ (p ։ q) → (p

′

_։

_q)

(10) Note that the properties (8), (9) and (10) overthree of thefour possible asesoftransitivitypropertieswhi hmixstandardand ontra tualimpli ation. Observe,instead, that ombiningtwoimpli ations into a ontra tisnot a de-sirablepropertyofanylogi for ontra ts,forthesamereasonforwhi hwedo notwantstandardand ontra tualimpli ationsbeequivalent.

(p → q) ∧ (q → r) → (p ։ r)

NOTATAUTOLOGY

Anotherproperty that should hold is that, if apromise

q

is already true, thenitisalsotrueany ontra twhi hpromises

q

:

q → (p ։ q)

(11)

Of ourse, wedo not want the onverseto hold: it is notalwaysthe ase that a ontra timpliesitspromise.

In this se tion we give the basi ingredients of our logi for ontra ts PCL. In Se t.4.1 wepresent the syntax of PCL ; in Se t. 4.2 weprovideit with an Hilbert-style axiomatization. Finally, in Se t. 4.3 we study some interesting propertiesofPCLthatfollowfrom thegivenaxioms.

4.1 Syntax

ThesyntaxofPCLisasimpleextensionof IPC.Itin ludes thestandardlogi onne tives

¬, ∧, ∨, →

and the ontra tual impli ation onne tive

։

. We as-sume adenumerable set

{p, q, r, s, . . .}

of prime (atomi ) formulae. Arbitrary PCL formulaearedenoted withthe letters

p, q, r, s, . . .

(note that thefont dif-fers from that used for prime formulae). The pre eden e of IPC operators is thefollowing,fromhighestto lowest:

¬, ∧, ∨, →

. Westipulatethat

։

hasthe samepre eden eas

→

.

Denition4.1. TheformulaeofPCLareindu tivelydenedbythefollowing grammar.

p ::=

⊥

false

|

⊤

true

|

p

prime

|

¬p

negation

|

p ∨ p

disjun tion

|

p ∧ p

onjun tion

| p → p

impli ation

| p ։ p

ontra tualimpli ation

Welet

p ↔ q

besynta ti sugar for

(p → q) ∧ (q → p)

. Ifaformulais

։

-free, wesayitis anIPC formula. Weusethesymbol

=⇒

todenoteimpli ationin themeta-theory,soto avoid onfusionwith

→

.

4.2 Proof Theory: Hilbert-style Axiomatization

WenowdeneaHilbert-styleproofsystemforPCL. Theaxiomsin ludeallthe standardaxiomsforIPC(seee.g. [24℄). Likein IPC,wehaveasingleinferen e rule,i.e.ModusPonens. The hara terisingaxiomsforPCLare alled

Zero

,

Fix

and

PrePost

.

•

CoreIPC axioms.

p ∧ q → p

∧1

p ∧ q → q

∧2

p → q → p ∧ q

∧3

p → p ∨ q

∨1

q → p ∨ q

∨2

(p → r) → (q → r) → (p ∨ q) → r

∨3

p → q → p

→ 1

(p → q → r) → (p → q) → p → r

→ 2

⊥ → p

⊥

⊤

⊤

¬p → p → q

¬1

(p → q) → (p → ¬q) → ¬p

¬2

•

Contra tualimpli ationaxioms.

⊤ ։ ⊤

Zero

(p ։ p) → p

Fix

(p

′

_{→ p) → (p ։ q) → (q → q}

′

_{) → (p}

′

_։

_q

′

₎

_PrePost

•

Modusponens ( ut).

p p → q

q

Cut

Wewrite

⊢ p

when

p

isderivablefromtheaxiomsandinferen erulesabove. The ontra tualimpli ationaxiomsarea tuallyspe ial asesofthedesired propertiesof ontra tsseeninSe t. 3. Forinstan e,theaxiom

Zero

isaspe ial aseof(7). Theaxiom

Fix

isexa tlytheproperty(3). Theaxiom

PrePost

plays theroleofboththeproperties(10)and(9).

4.3 Fundamental Consequen es

Wepresentbelowsomesigni ant onsequen esoftheaxiomsinDef.4.2. Note that these onsequen es overallthepropertiesmarkedinSe t.3asdesirable. To shorten our notation, when speaking about non-provability, we write

6⊢ p

when the formula

p

is not a theorem of PCL (i.e.

p

is not true for all the instantiationsofthemetavariables). Forinstan e,wewrite

6⊢ p → p ∧ q

tomean that

¬∀p, q. ⊢ p → p ∧ q

.

Lemma4.3. Contra tualimpli ation isstri tly stronger thanimpli ation.

⊢ (p ։ q) → (p → q)

(12)

6⊢ (p → q) → (p ։ q)

(13)

Proof. For(12), assumethat

p ։ q

and

p

hold. Hen e,

q → p

trivially holds. Byusing

PrePost

on

q → p

,

p ։ q

,and

q → q

,weget

q ։ q

. Wethen on lude

q

by

Fix

. Weanti ipatein(13)anegativeresultthat anbeme hani allyveried usingthede isionpro edureofLemma6.14.

Below, we establish some further onne tions between

։

and

→

, whi h generalizethetransitivityof

։

.

following intera tionsbetween

։

and

→

.

⊢ (p ։ q) → (q ։ r) → (p ։ r)

(14)

⊢ (p → q) → (q ։ r) → (p ։ r)

(15)

⊢ (p ։ q) → (q → r) → (p ։ r)

(16)

6⊢ (p → q) → (q → r) → (p ։ r)

(17)

Proof. Properties (15,16) are dire t onsequen es of

PrePost

, and the trivial

r → r

and

p → p

.

For(14),weapply Lemma 4.3(12)to

p ։ q

,so obtaining

p → q

. Then we anapply(15)to on lude.

We anti ipate in (17) a negative result that an be me hani ally veried usingthede isionpro edureofLemma6.14.

The distributivity laws of

։

are quite pe uliar. As for standard impli a-tioninIPC,

∨

-distributivityholdsinonlyonedire tion(18,19). Instead,while

∧

-distributivity holdsin bothdire tions in IPC for standardimpli ation, on-tra tual impli ation only satises one dire tion (20,21). However, a related propertyholds(22).

Lemma4.5. Distributivity laws.

⊢ (p ։ q) ∨ (p ։ r) → (p ։ (q ∨ r))

(18)

6⊢ (p ։ (q ∨ r)) → (p ։ q) ∨ (p ։ r)

(19)

⊢ (p ։ (q ∧ r)) → (p ։ q) ∧ (p ։ r)

(20)

6⊢ (p ։ q) ∧ (p ։ r) → (p ։ (q ∧ r))

(21)

⊢ (p ։ q) ∧ (q ։ r) → (p ։ (q ∧ r))

(22)

Proof. For(18),assume

(p ։ q) ∨ (p ։ r)

. If

p ։ q

holds,weapply

PrePost

to weaken

q

to

q ∨ r

. The

p ։ r

aseissimilar.

For (20), assume

p ։ (q ∧ r)

. By

PrePost

, it is then easy to obtainboth

p ։ q

and

p ։ r

.

We anti ipate in (19,21) some negative results that an be me hani ally veriedusingthede isionpro edureofLemma 6.14.

For(22),assumethehypotheses. WeapplyLemma4.3to

q ։ r

andobtain

q → r

,hen e

q → (q ∧ r)

. By

PrePost

on

p ։ q

, weobtainthethesis.

Lemma4.6. Substitutionof equivalentformulae.

⊢ (p ↔ p

′

_{) → (q ↔ q}

′

_{) → (p ։ q) → (p}

′

_։

_q

′

₎

Proof. Apply

PrePost

to

p

′

_{→ p}

,

p ։ q

,and

q → q

′

.

Thefollowinglemma statesasu ient onditionandane essary ondition for

p ։ q

to hold. These onditionsare expressed in IPC, i.e. theymakeno useof

։

. WewillreturnontheseinDef. 8.6,8.8andrelatedresults,wherewe will provethat, when

p, q

are IPC formulae, these onditionsare a tually the weakest su ient onditionandthe strongestne essary onditionthat anbe expressedwithin IPC(Lemma8.10).

andne essary ondition.

⊢ q → (p ։ q)

(23)

⊢ (p ։ q) → ((q → p) → q)

(24)

Proof. For(23),assume

q

. We on ludeby

PrePost

on

p → ⊤

(trivial),

⊤ ։ ⊤

(by

Zero

),

⊤ → q

(by

q

).

For (24), assume

p ։ q

and

q → p

. By

PrePost

, we have

q ։ q

, so we on ludeby

Fix

.

Thefollowing lemmajustiesour hoi eof IPC, ratherthan lassi allogi CPC,asthebasisforourlogi : indeed, hoosingCPCwouldmakeour ontra -tualimpli ationmu hlessinteresting.

Lemma 4.8. Denote with

⊢C

p

the provability of

p

inthe systemof Def. 4.2 augmentedwith the axiomof ex ludedmiddle (

p ∨ ¬p

). Then,we have:

⊢

C

(p ։ q) ↔ q

Proof. Dire t onsequen eofLemma4.7,sin e

((q → p) → q) → q

isatautology ofCPC(a tually,itisthewell-knownPeir e'slaw).

Thefollowingtwolemmataareabouthandshakingof

n

ontra tingparties. Lemma 4.9speaksabout ir ular handshakingwherethe

i

-thpartyrelies on the promise made by the

i − 1

-th party, asin (2). Lemma 4.10 is astronger versionofthis,be auseitallowsea hpartytorelyonthepromisesmadebyall theotherparties,asin(4) .

Lemma4.9. (Handshaking) Forall

n ≥ 0

andfor all

p0, . . . , pn

:

⊢ (p0

։

p1) → · · · → (pn−1

։

pn) → (pn

։

p0) → (p0

∧ . . . ∧ pn)

Proof. Assume allthe hypotheses. Byrepeatedappli ation of Lemma 4.4, we have

pi

։

pi

forall

i ∈ 0..n

. Wethen on ludeby

Fix

.

Lemma4.10. (Greedy handshaking)Forall

n ≥ 0

,forall

p0, . . . , pn

,and for all

i, j ∈ 0..n

:

⊢

^

i



 ^

j6=i

pj



։

pi



→

^

i

pi

(25)

Proof. Byindu tion on

n

. Thebase ase

n = 0

is simple:

(⊤ ։ p0) → p0

is provedbyapplying

PrePost

to

⊤ ։ p0

,hen eobtaining

p0

։

p0

and on luding by

Fix

.

Inthe indu tive ase, assume that (25) holds for

n − 1

. We then proveit for

n

. Todo that, we assumethat the hypothesis



V

j6=i

pj



։

pi

is true for

ea h

i = 0..n

, and then wepro eed to provethe thesis

V

i

pi

. First, weprove thefollowingauxiliaryresult:

pn

→

^

j6=n

To prove(26), assume

pn

. Then, wehave



V

j6=i

pj



↔



V

j6=i,j6=n

pj



, so by Lemma 4.6weget



V

j6=i,j6=n

pj



։

pi

for

i = 0..n − 1

. We anapply the

indu tivehypothesis (25),andhave

V

j6=n

pj

.

Ba ktotheindu tive ase,notethatsin e

i

anbe

n

,wehave



V

j6=n

pj



։

pn

. Wethen on ludeby(26,24). 5 Examples

Example5.1. Thetoyex hanges enariofromSe t. 2ismodelledas:

⊢ (airplane ։ bike) ∧ (bike ։ airplane) → (airplane ∧ bike)

Indeed,thisisa onsequen eofouraxioms,andaspe ial aseofLemma4.9. Example5.2. Wenowexploitourlogi tomodelatypi alpreliminary ontra t forareal estatesaleinItaly.

Assumeabuyerwhoisinterestedinbuyinganewhousefromagivenseller. Before stipulatingthea tual pur hase ontra t, thebuyerand theseller meet to stipulateapreliminarysale ontra t,that xesthetermsand onditionsof thepur hase. Typi ally,this ontra twillindi atethepri eandthedatewhen thedeedofsalewilltakepla e,anditwilloutlinetheobligationsforthebuyer and the seller. When the preliminary ontra tis signed by both parties, the buyer will typi ally pay a part of the sale pri e. By the italian laws, if the sellerde idesnottosellthehouseafterhavingsignedthepreliminary ontra t and olle tedthedeposit,shemustpaythebuyerba ktwi ethesumre eived. Similarly, ifthebuyer hangeshis mindand de idesnot to buy thehouse, he losesthewholedepositedamount.

Wemodel thepreliminary sale ontra t astwoPCL formulae, onefor the buyerandtheotherfortheseller. Thebuyerwillsignthepreliminary ontra t (

signB

),providedthatthesellerwilla tuallysellherhouse(

sellS

),orsherefunds twi ethesumre eived(

refundS

). Also, thebuyerpromisesthatifhesignsthe preliminary ontra t,thaneither hewillpaythestipulated pri e(

payB

),orhe willnotpayandlosethedeposit(

refundB

)

Buyer : ((sellS ∨ refundS) ։ signB) ∧ (signB ։ (payB ∨ (¬payB ∧ refundB)))

Theseller promisesthat shewillsignthepreliminary ontra t(

signS

), pro-vided that either the buyer promises to pay the stipulated amount, or he promises to lose the deposit. Also, the seller promises that is she signs the preliminary ontra t, then she will either sell her house, or will not sell and refundtwi ethesumre eived.

Seller : ((payB ∨ refundB) ։ signS) ∧ (signS ։ (sellS ∨ (¬sellS ∧ refundS)))

Arst onsequen eisthat thetwo ontra tsleadtoanagreementbetween thebuyerandtheseller,that isbothpartieswillsignthepreliminary ontra t:

ofsale,thanthat partywillrefundtheother:

Buyer ∧ Seller ∧ ¬payB → refundB

(28)

Buyer ∧ Seller ∧ ¬sellS → refundS

(29)

Toprovetheabove,wepro eedasfollows. First,weapply transitivity(14) to

Buyer

and

Seller

:

(sellS ∨ refundS) ։ (payB ∨ (¬payB ∧ refundB))

(payB ∨ refundB) ։ (sellS ∨ (¬sellS ∧ refundS))

Then,weuse

PrePost

:

(sellS ∨ (¬sellS ∧ refundS)) ։ (payB ∨ (¬payB ∧ refundB))

(payB ∨ (¬payB ∧ refundB)) ։ (sellS ∨ (¬sellS ∧ refundS))

So,byLemma 4.9,wehavethat

Buyer ∧ Seller

implies

(sellS ∨ (¬sellS ∧ refundS)) ∧ (payB ∨ (¬payB ∧ refundB))

By(12)theaboveand

Buyer ∧ Seller

imply

signB

∧ signS

. Thisproves(27). Also,theaboveand

¬payB

learlyimply

refundB

. Thesameholdsfor

sellS

and

refundS

. Hen e,weestablish(28,29).

Example5.3. Wenowdes ribeapossibleonlinesalebetweentwoparties. In orderto buy anitem, rstthebuyerhasto onta tthebankandreservefrom hisa ountaspe i amountofmoneyforthetransa tion. Whenthishappens, thatamountisnolongeravailableforanythingelse. Wemodelthisreservation withtheformula

lock

. Then, thebuyerhasto makeanoertotheseller: this is modelled with

offer

. The seller, when provided with an oer, evaluates it. Ifshe thinkstheoerisgood,and themoneyhasbeenreserved,thenshe will send the item (

send

). Otherwise, she an els the transa tion (

abort

). When thetransa tionisaborted,thebank an elsthemoneyreservation,so thatthe buyer anusetheamountforothertransa tions(

unlock

).

Wenowformalizethe s enario. Thebuyer agrees to

lock

∧ offer

, provided that either the itemis sent, orthe moneyreservation is an elled. Theseller agreestoevaluatetheoer. Thebankagreesto an elthereservationwhenthe transa tionisaborted.

Buyer : (send ∨ unlock) ։ (lock ∧ offer)

Seller : offer ։ ((lock → send) ∨ abort)

Bank : (lock ∧ abort) ։ unlock

Under these assumptions, we an see that either the item is sent, or the transa tionisabortedandthereservation an elled.

⊢ (Buyer ∧ Seller ∧ Bank) → (send ∨ (abort ∧ unlock))

Toprovethis, rst weapply

PrePost

to

Seller

and obtain

(lock ∧ offer) ։

(lock ∧ offer ∧ ((lock → send) ∨ abort))

. By

PrePost

, we weaken it, obtaining

(send ∨ unblock) ։ (send ∨ (lock ∧ abort))

. By

Bank

and4.3, wehave

(lock ∧

abort) → unlock

, as well as

(lock ∧ abort) → (abort ∧ unlock)

. Therefore, by

PrePost

wehave

(send ∨ unlock) ։ (send ∨ (abort ∧ unlock))

. We on ludeby

PrePost

and

Fix

.

Example5.4. (Diningretailers)Aroundaroundtable,agroupof

n

utlery retailersisabouttohavedinner. Inthe enterofthetable,thereisalargedish offood. Despitethefoodbeingdeli ious,theretailers annotstarteatingright now. Todo that, and follow theproperetiquette, ea h retailer needsto have a omplete utlery set, onsisting of

n

pie es, ea h of a dierent kind. Ea h oneof the

n

retailersownsadistin t set of

n

pie e of utlery, allof thesame kind. Theretailersstartdis ussingabouttradingtheir utlery,sothatthey an nallyeat.Sin eeveryonewantstogetafairdeal,theywanttoformalizetheir ommittments.

Weformalizethes enarioasfollows. Numbertheretailers

r1, . . . , rn

together with the kinds of pie es of utlery, so that

ri

initially owns

n

pie es of kind number

i

. Then,write

gi,j

for

ri

gives apie e(ofkind

i

)to

rj

. Sin eretailers anusetheirown utlery,weassume

gi,i

tobetrue. Retailer

ri

anstarteating whenever

ei

=

V

j

g

j,i

.

Suppose that

r1

ommits to a simple ex hange with

r2

: they ommit to

g2,1

։ g1,2

and

g1,2

։ g2,1

, and theex hangetakespla esin e

g2,1

∧ g1,2

an be derived. While this seems a fair deal, it a tually exposes

r1

to a risk: if

r3, . . . , rn

perform asimilar ex hange with

r2

, then we have

g2,i

∧ g

i,2

for all

i

. Inparti ular,

gi,2

holds forall

i

, so

r2

anstarteating. Thisis howevernot ne essarilythe asefor

r1

,sin e

r3

hasnot ommittedtoanyex hangewith

r1

. A wise retailer would then never agree to a simple ex hange

g2,1

։ g1,2

. Instead,theretailer

r1

ould ommittoasafer ontra t

1 :

g1,1

∧ g2,1

∧ · · · ∧ gn,1

։ g1,1

∧ g1,2

∧ · · · ∧ g1,n

Theideais simple:

r1

requires ea h pie e of utlery, that is,

r1

requiresto beabletostarteating(

e1

). Whenthishappens,

r1

agreestoprovideea hother retailerwithapie eofhis utlery. Now,assumee hretailer

ri

ommitstothe analogous ontra t:

ci

= ei

։

^

j

g

i,j

We annowverifythat

V

i

ci

→

V

i

ei

, thatis, theabove ontra tsa tually allow everyoneto eat. Assume

ci

for all

i

, and dene

pi

=

V

j

g

i,j

. Clearly,

ci

= ei

։

pi

. Notethat

^

j6=i

pj

=

^

j6=i

^

k

gj,k

→

^

j

gj,i

= ei

(30)

sin ewe an hoose

k = i

and

g

i,i

istrue. Therefore,by

PrePost

,

ci

= ei

։

pi

→

 ^

j6=i

pj



։

pi

ByLemma4.10,sin e

V

i

ci

,wehave

V

i

pi

. By(30)wethen on lude

V

i

ei

. 1

tra tualimpli ation. Asmallsetofthesewasthenpi kedasouraxiomatization:

Zero

,

Fix

and

PrePost

. However,wehavenotyet he kedthatthisisindeed om-plete with respe t to the other requirements. That is, we have to he kthat alltherequirementsaretheoremsofPCL. Wenowqui klyre allthelistofall these requirementsandprovideasupportforea hone.

Thehandshakingproperties(1,2)havebeenestablishedinLemma4.9. Prop-erty (3) is the axiom

Fix

. The greedy handshaking (4) was established in Lemma 4.10. Property(6) wasprovedin Lemma 4.3. Property(7) is adire t onsequen eof

Zero

. Property (8) is provedin Lemma 4.4. Properties (9,10) are dire t onsequen es of

PrePost

. Property(11) is a onsequen e of axioms

Zero

and

PrePost

.

6 Proof Theory: Sequent Cal ulus

Inthisse tionweprovideanalternativeformalizationofPCL,throughasequent al ulusàlaGentzen. Oursequentshavetheform

Γ ⊢ p

,where

Γ

isaniteset offormulae. Below,wewrite

Γ, p

for

Γ ∪ {p}

.

MostoftherulesfortheIPCfragmenthavebeentakenfrom[27℄,whi h fea-turesarulesetforIPCwithoutstru turalrules. Thisfa tturnsouttobequite usefulwhenreasoningabouttherulesystem. Indeed,asin[27℄,weareableto establish ut-eliminationbyapplying areasonablysimplestru turalindu tion; werefertoSe t. 7forthedetailedproof. IntheIPCfragmentofourrulesystem below,only rules

¬R

and

weakR

divergefrom [27℄. This hange wasrequired to establishthesubformulaproperty(Lemma6.13). Anotherminor dieren e from [27℄ arises from our

Γ

's being sets rather thanmultisets; thisis however immaterial,be auseoftheabsen eofstru tural rules,andtheadmissibilityof ontra tionin[27℄.

Denition6.1. TheGentzen-stylerulesystemforPCL omprisesthefollowing rules.

Γ, p ⊢ p

id

Γ, p ∧ q, p ⊢ r

Γ, p ∧ q ⊢ r

∧ L1

Γ, p ∧ q, q ⊢ r

Γ, p ∧ q ⊢ r

∧ L2

Γ ⊢ p Γ ⊢ q

Γ ⊢ p ∧ q

∧ R

Γ, p ∨ q, p ⊢ r Γ, p ∨ q, q ⊢ r

Γ, p ∨ q ⊢ r

∨ L

Γ ⊢ p

Γ ⊢ p ∨ q

∨ R1

Γ ⊢ q

Γ ⊢ p ∨ q

∨ R2

Γ, p → q ⊢ p Γ, p → q, q ⊢ r

Γ, p → q ⊢ r

→ L

Γ, p ⊢ q

Γ ⊢ p → q

→ R

Γ, ¬p ⊢ p

Γ, ¬p ⊢ r

¬L

Γ, p ⊢ ⊥

Γ ⊢ ¬p

¬R

Γ, ⊥ ⊢ p

⊥L

Γ ⊢ ⊤

⊤R

Γ ⊢ ⊥

Γ ⊢ p

weakR

Γ ⊢ p Γ, p ⊢ q

Γ ⊢ q

cut

Contra tualimpli ationrules

Γ ⊢ q

Γ ⊢ p ։ q

Zero

Γ, p ։ q, r ⊢ p Γ, p ։ q, q ⊢ r

Γ, p ։ q ⊢ r

Fix

Γ, p ։ q, a ⊢ p Γ, p ։ q, q ⊢ b

Γ, p ։ q ⊢ a ։ b

PrePost

Note that IPC rules have left and right rules for ea h IPC onne tive. Roughly, ea h onne tive has right rules for introdu tion, and left rules for elimination. Contra tualimpli ationinsteadhasadierentavor.Rule

Zero

is ee tivelyanintrodu tionrule,andhasasimilarfun tiontotheHilbertaxiom Zero. Similarly, rule

Fix

is an elimination rule; its fun tion is related to the Hilbert axiomFix. Indeed,theserules ouldbenamed

։

R

and

։

L

, respe -tively. Theleft/rightruledualismhoweverisbrokenbyrule

PrePost

. Of ourse, itsfun tion isthatoftheHilbert axiom

PrePost

. Thisrulebehavesbothasan introdu tionandanelimination,soisbotharightandleftrule,in asense.

Inthe rest of this se tion westudy the sequent rule system above. First, we prove it equivalent to our Hilbert axioms (Th. 6.4). Then we prove the redundan y of the

weakR

rule, i.e. that

weakR

is admissible in the proof sys-tem omposed of allthe other rules. More importantly, wealso provethe

cut

ruleredundant,i.e. weprove ut-eliminationforoursequentrulesystem. Asa onsequen eof ut-elimination,weareableto establishthe onsisten y ofthe logi (Th. 6.11), thesubformulaproperty(Lemma 6.13),and thede idability

of

⊢

(Lemma 6.14). Wealso provethat the rules

Zero, PrePost, Fix

are not re-dundant, asonemightexpe t (Lemma 6.15). Finally we prove that PCLis a onservativeextensionofIPC(Lemma6.16).

6.1 Equivalen e of the Hilbert and Gentzen Systems

In this se tion, we establish the equivalen e between the twodierent logi al systemsweintrodu ed. Wedenote with

⊢

H

p

thefa t that

p

isprovablefrom the Hilbert-style axiomsof Def. 4.2. Similarly, by

⊢

G

p

wedenote that

∅ ⊢ p

is a derivablesequentfrom the Gentzen-style rules of Def. 6.1. We will then prove

⊢

H=⊢G

.

Lemma6.2.

⊢

H

p =⇒ ⊢G

p

Proof. Itissu ienttoshowthat

⊢

G

holdsforalltheHilbert-styleaxioms,and that itis losed under modusponens. The latteris trivially doneby

cut

and

→ R

. Fortheformer,we he kthe

։

-relatedaxioms,only,sin etheothersare standard.

• Zero

⊢ ⊤

⊤R

⊢ ⊤ ։ ⊤

Zero

• PrePost

∆, p

′

_{⊢ p}

′

id

_{∆, p}

′

_{, p ⊢ p}

id

∆, p

′

_{⊢ p}

→ L

∆, q ⊢ q

′

id

_{∆, q, q}

′

_{⊢ q}

′

id

∆, q ⊢ q

′

→ L

∆ = p

′

_{→ p, p ։ q, q → q}

′

_{⊢ p}

′

_։

_q

′

PrePost

p

′

_{→ p, p ։ q ⊢ (q → q}

′

_{) → (p}

′

_։

_q

′

₎

→ R

p

′

_{→ p ⊢ (p ։ q) → (q → q}

′

_{) → (p}

′

_։

_q

′

₎

→ R

⊢ (p

′

_{→ p) → (p ։ q) → (q → q}

′

_{) → (p}

′

_։

_q

′

₎

→ R

• Fix

p ։ p, p ⊢ p

id

p ։ p, p ⊢ p

id

p ։ p ⊢ p

Fix

⊢ (p ։ p) → p

→ R

Lemma6.3.

⊢G

p =⇒ ⊢H

p

Proof. Itissu ienttoprovethefollowingstatementforea hrule:

Γ0

⊢G

p0

· · · Γn

⊢G

pn

Γ ⊢G

p

=⇒ ⊢H

V

i

[V Γi

→ pi] →

V Γ → p

Then,thelemmafollowsbyindu tiononthederivationof

⊢G

p

. Most ases arestandard,sowe he konlythe

։

-relatedrules.

•

Rule

Zero

:

(V Γ → q) → V Γ → (p ։ q)

.

Assumethe hypotheses. Bymodus ponens,weget

q

, hen e

⊤ → q

. We have

⊤ ։ ⊤

byZero. Theformula

p → ⊤

triviallyholds. Wethenapply PrePosttorea h

p ։ q

:

•

Rule

PrePost

:

[(V Γ ∧ (p ։ q) ∧ a) → p]∧[(V Γ ∧ (p ։ q) ∧ b) → q] → (V Γ∧

(p ։ q)) → (a ։ b)

.

Assume all the hypotheses. We easily get

a → p, p ։ q, q → b

. By

PrePost

,weget

a ։ b

.

•

Rule

Fix

:

[(V Γ ∧ (p ։ q) ∧ r) → p] ∧ [(V Γ ∧ (p ։ q) ∧ q) → r] → (V Γ ∧

(p ։ q)) → r

.

Assume all the hypotheses. We get

r → p, q → r

, hen e

q → p

. Using

q → p

(dedu ed),

p ։ q

(hypothesis),

q → q

(trivial), weapply

PrePost

andget

q ։ q

. By

Fix

,

q

,hen e

r

.

Theorem6.4.

⊢

G

=⊢H

Proof. Immediatefrom lemmas6.2and6.3.

6.2 Properties of the Gentzen System

A rst basi resultof our system is that the left-weakening of a sequent, i.e. augmentingthe

Γ

,isstronglyadmissible.Thatis,wheneverwehaveaderivation for asequent, we anprodu e aderivation for the augmented sequent having thesameheight.

Lemma6.5. If

D

Γ ⊢ p

then

D

′

Γ, Γ

′

_{⊢ p}

where

D

′

has the sameheight of

D

.

Proof. Itissu ienttoaugmentea hsequentin

D

with

Γ

′

. Itisstraightforward to he kthatnoruleisinvalidatedbythis.

Convention. The abovelemma isveryfrequentlyused in ourproofs. To avoid ontinuously referring to it, we adopt the following notation: when we have

D

Γ ⊢ p

,wesimplywrite

D+

Γ, Γ

′

_{⊢ p}

fortheaugmentedderivation.

ThenextresultisdualtoLemma 6.5. Itstatesthattheright-weakeningof a sequent, i.e. repla ing a

⊥

on the right of the turnstile

⊢

with some other formula, anbeperformedwithoutusingthe

weakR

rule. Inotherwords,rule

weakR

isredundantinoursystem. Toprovethis,werstintrodu eanauxiliary lemma.

Lemma6.6. If

D

Γ ⊢ ⊥

where

D

is a

weakR

-freederivation, thenwe also have

Γ ⊢ p

witha

weakR

-free derivation,for any

p

.

Proof. Byindu tionontheheightofthederivation

D

. Thelaststepof

D

must beoneof

id, cut, Fix

oraleftrule. Ifaleftruleora

cut

hasbeenused,thethesis iseithertrivial(

¬L, ⊥L

)orimmediatelyfollowsbytheindu tionhypothesis. If

id

hasbeenused,then

⊥ ∈ Γ

,and

⊥L

su es. If

Fix

hasbeenused,werewrite thederivationin thefollowingway:

D0

Γ, a ։ b, ⊥ ⊢ a

D1

Γ, a ։ b, b ⊢ ⊥

Γ, a ։ b ⊢ ⊥

Fix

=⇒

Γ, a ։ b, p, a ⊢ a

id

D1

′′

₊

Γ, a ։ b, p, b ⊢ a

Γ, a ։ b, p ⊢ a

Fix

D1

′

Γ, a ։ b, b ⊢ p

Γ, a ։ b ⊢ p

Fix

where

D1

′

and

D1

′′

areobtainedfromtheindu tionhypothesison

D1

,and theformulae

p, a

respe tively.

Note that the transformation above does not introdu e new

cut

s in the derivation. So,on ethe uthasbeeneliminated,thesamepro edure an elim-inate

weakR

,too.

Lemma6.7. The

weakR

ruleisredundant. Proof. Itissu ienttoiterate Lemma6.6.

Anotherfundamental result enjoyed by ourGentzen-style rules, is the re-dundan yofthe

cut

rule. This isa lassi ut-elimination result,orHaupsatz, whi histhebasisformanyoftheresultsin thisse tion.

Theorem6.8. (Cut-elimination)The

cut

ruleisredundant. Proof. SeeSe t. 7forthedetailedproof.

Itispossibletoremoveboththerules

cut

and

weakR

fromoursystemwithout ae tingthegenerated

⊢

relation.

Theorem6.9. The ruleset

{cut, weakR}

isredundant.

Proof. Thisisnotanimmediate orollaryofthepreviousresults,sin eremoving a

cut

from aderivation ouldfor e us toin lude

weakR

in thenewderivation, and, vi eversa,removinga

weakR

ouldfor eus tointrodu ea

cut

. However, byinspe ting theproofforLemma 6.7, we anseethat the

weakR

-elimination pro eduredoesnotintrodu enew

cut

s. So,givenanarbitraryderivation

D

for asequent,byTh. 6.8wealsohavea ut-freederivation

D

′

forthesamesequent. Then,we anapplythepro edureofLemma6.7to on lude.

Inourlogi ,asforIPC, everynegation-freetheory

Γ

is onsistent. Lemma6.10. Let

Γ

befreefrom

¬, ⊥

. Then

Γ 6⊢ ⊥

.

Proof. By ontradi tion,assume

D

Γ ⊢ ⊥

tobea ut-freederivation. Wepro eed by indu tion onthederivation

D

, andthen by aseanalysis. The laststep of

D

an not be

id, ¬L, ⊥L

, otherwise

Γ

is not free from

¬, ⊥

. If the last step is another left rule, we have

Γ

′

_{⊢ ⊥}

as a premise for some

Γ

′

free from

¬, ⊥

so the indu tive hypothesis su es. The same applies to

Fix

. No right rule an introdu e

⊥

, so the last step is not a right rule. The same applies to

Theorem6.11. (Consisten y)The logi is onsistent,i.e.

∅ 6⊢ ⊥

. Proof. Dire t onsequen eofLemma6.10.

Cut-freederivationsenjoythesubformula property,statingthatallthe for-mulae o urring su h a derivationfor a sequentappear assubformulae in the sequentaswell. Equivalently,itstatesthata ut-freederivationofasequent an onlyinvolvesubformulaeof thatsequent. Asasingleex eption,thederivation mightmention

⊥

whilethesequentdoesnot,be auseofthe

weakR

rule. Denition6.12. Thesubformulae

sub(p)

ofaformula

p

areindu tivelydened asfollows

sub(p) = {p}

sub(⊥) = {⊥}

sub(⊤) = {⊤}

sub(¬p) = {¬p} ∪ sub(p)

sub(p ∨ q) = {p ∨ q} ∪ sub(p) ∪ sub(q)

sub(p ∧ q) = {p ∧ q} ∪ sub(p) ∪ sub(q)

sub(p → q) = {p → q} ∪ sub(p) ∪ sub(q)

sub(p ։ q) = {p ։ q} ∪ sub(p) ∪ sub(q)

Thesubformulaeofasetofformulae

Γ

is

sub(Γ) =

S

p∈Γ

sub(p)

.

Lemma 6.13. (Subformula Property)If

D

Γ ⊢ p

and

D

is ut-free, then the formulae o urringin

D

belong to

sub(Γ, p, ⊥)

.

Proof. Byasimpleindu tionon

D

. Thepropertyispreservedbyeveryrule. Note that a

{cut, weakR}

-free derivation would instead have a more tight

sub(Γ, p)

bound.

We an nowestablishde idabilityforPCL. Lemma6.14. (De idability)

Γ ⊢ p

isde idable.

Proof. We have

Γ ⊢ p

i it anbe derived without

cut

s. We an de ide the latter by sear hing for a shortest derivation bottom-up, exploring the whole proof spa enon-deterministi ally. Bythe subformulaproperty, ut-free proofs anonly ontainsequentshavingformulaein

sub(Γ, p, ⊥)

. Thisisanitesetof sequents: let

k

beits ardinality. Thedepthofthesear hintheproofspa e an belimitedto

k

: ifthereis atallerderivation, ithasasequento urringtwi e in somepath,sotheproof anbemadeshorter. Thisensuresthetermination ofthealgorithm.

Wehaveimplementedtheabovenaïvede isionpro edureforPCL, develop-ingaprototypetool,whi hweusedforexperimentingwithourlogi . Sin ethe proofspa eishuge,thetoolwasveryhelpfulinestablishingthenegativeresults forourlogi ,i.e.

6⊢ p

from somegiven

p

. Wegivemoreinformationaboutitin Se t. A.2.

Lemma6.15. Noneof the

Zero

,

PrePost

,

Fix

Gentzen rulesisredundant. Proof. First, we arefully examine the proof of the ut-elimination theorem, and he k that the sameproof a tually establish ut-elimination eventin the rule system without any of the rules

Zero

,

PrePost

,

Fix

. This is be ause the ut-eliminationpro edureneverintrodu esanewappli ationof,say,a

Fix

rule unless

Fix

was already present in the original derivation. Similarly, we an restate thesubformulapropertyinthese restri tedrulesystems,aswellas de- idability. Wethereforehavede isionpro edures forboththefull rulesystem andea hrestri tionofit,sowe an he kthatindeedsomeformulaisprovable in thefullsystem,butnotin therestri tion. As itmightbeexpe ted, itturns outthattoprovetheHilbertaxioms

Zero

,

PrePost

,

Fix

in theGentzensystem, therelatedruleisne essary. Thiswas he kedbyasimplemodi ationofour tool,des ribedinSe t. A.2.

Asani eresultofthesubformulaproperty,wegetthatPCLisa onservative extensionofIPC.

Lemma6.16. PCLisa onservativeextensionofIPC,thatis

⊢IP C

p ⇐⇒ ⊢ p

for allIPC formulae

p

.

Proof. The

⇒

partis Lemma 8.4. Forthe

⇐

part, if

⊢ p

, by Lemma 6.2 we have

⊢G

p

. By ut-eliminationandthesubformulaproperty,wehave

D

⊢ p

where

D

makeno use of rules Zero, Fix, and PrePost. Sin e all the other rules are in ludedintheGentzen systemofIPC, we anstate

⊢

IP C

p

.

7 Cut-elimination

In this se tion we prove ut elimination for the Gentzen system of Def. 6.1. In order to do this, we borrow a fairly simple stru tural indu tion te hnique from [27℄.

2

The whole te hnique an be des ribed as a re ursive algorithm, transformingageneri derivationintoa ut-freeone. Thealgorithmismadeof twore ursiveroutines: a oreroutine( ut-redu e)andadriver( ut-elim). The oreroutinedealswith thespe ial aseof aderivation ending witha

cut

betweentwo ut-free subderivations. Wenamederivations ofthis spe ialform redu ible derivations. Whenprovidedwitharedu iblederivation, ut-redu e produ es a ut-freederivation forthe samesequent. Exploiting ut-redu e, the driver ut-elim handles thegeneral ase. Thea tual pro edure isshown in Alg. 1.

2

Here,stru tural meansthatitpro eedsindu tivelyonthestru tureofaderivationin theGentzensystem.

ut-elim

D0

Γ0

⊢ p0

D1

Γ1

⊢ p1

Γ ⊢ p

cut

!

= ut-redu e

D

′

0

Γ0

⊢ p0

D

′

1

Γ1

⊢ p1

Γ ⊢ p

cut

!

ut-elim

· · ·

Di

Γi

⊢ pi

· · ·

Γ ⊢ p

r

!

=

· · ·

D

′

i

Γi

⊢ pi

· · ·

Γ ⊢ p

r

(

r 6= cut

) where

D

′

i

Γi

⊢ pi

= ut-elim



Di

Γi

⊢ pi



The ut-elim drivertakesasinput aderivation

D

. First,it applies itself re ursivelyonthederivationsofthepremises

Di

so onvertingthemtothe ut-free ones

D

′

i

. Then, if the last rule

r

used in

D

is not a

cut

, we an apply the samerule to

D

′

i

to onstru t a ut-free derivation. Otherwise,

r

is a

cut

, and weare in thespe ial asehandled by ut-redu e, so wejust invoke it. The ut-elimdriveralways terminatessin eea h re ursive allismade ona subderivation.

In the rest of this se tion, we dene the ore routine ut-redu e. This routinemakesuseof asophisti atedre ursions heme. Wheninvokedas

ut-redu e

D0

Γ ⊢ p

D1

Γ, p ⊢ q

Γ ⊢ q

cut

!

with ut-free

D0, D1

theroutinemakesseveralre ursive alls,allofthemforredu iblederivations. Assumeare ursive allismadeona uthaving

p

′

asthe utformula,and

D

′

0

, D

′

1

asthesubderivations. Then,oneofthefollowing onditionsholds: Denition7.1. Constraintsonthere ursive allsto ut-redu e:

3 1.

p

′

isapropersubformulaof

p

,or 2.

p

′

_{= p}

and

h(D

′

0

) < h(D0)

,or 3.

p

′

_{= p}

,

h(D

′

0

) ≤ h(D0)

, and

h(D

′

1

) < h(D1)

.

We anstatethe onditionsaboveasfollows: thetriple

(p

′

_{, h(D}

′

0

), h(D

′

1

))

is lexi ographi ally smallerthan

(p, h(D0), h(D1))

. Itis easyto see that this or-deringfortriplesisawell-foundedorderingrelation,andthereforethere ursion musteventuallyterminate.

We now pro eed to dene the ut-redu e routine. This is done by ex-amining thelast rules used in

D0

and

D1

, and overingallthepossible ases. Tosimplifythepresentation,weadopta ompa tnotation,writing

=⇒

forour redu tion, as seenin Alg. 2. Therest of this se tion will pre isely dene the

=⇒

relation. 3

Welet onditions2and3tooverlap,sin eweuse

≤

insteadof

=

.Thisisdonetofollow oura tualredu tionpro eduremore losely,aswewillsee.

ut-redu e

D0

Γ ⊢ p

D1

Γ, p ⊢ q

Γ ⊢ q

cut

!

=

D

¯

where

D0

Γ ⊢ p

D1

Γ, p ⊢ q

Γ ⊢ q

cut =⇒ D

'

and

D

¯

isobtainedbyre ursivelyapplying ut-redu etoallthe

cut

sin

D

′

.

Whenwewrite

D =⇒ D

′

,

D

isaredu iblederivation,and

D

′

istheresultof theredu tion. Whenweuse

cut

sin

D

′

,theyareto beinterpretedasre ursive alls to the ut-redu e routine. Of ourse, we shall take are these uts agreewiththewell-foundedorderingdis ussedabove. Wedo umentthisinthe derivation

D

′

,bywriting

cutp

whenwearein ase1oftheenumerationabove,

cut0

whenwearein ase2,or

cut1

whenwearein ase3.

7.1 Summary of Cases

To lassifyallpossible ases,werstintrodu esometerminology. Ea hGentzen ruleisrelatedtosomelogi al onne tive. Aruleforageneri onne tive

⊙

has as its prin ipal formulae the formulae o urring in that rule that involve

⊙

. Rules

id, weakR

and

cut

have no prin ipal formulae. Both left and right rules in theIPC fragmenthaveexa tlyoneprin ipal formula. Rules

Zero

and

Fix

have one prin ipal formula as well. When a prin ipal formula o urs in the left (resp. right)hand side ofthe turnstile

⊢

we allit aleft (resp. right) prin ipalformula. Rule

PrePost

hastwoprin ipalformulae,namedleftprin ipal andrightprin ipal formulae.

Inorderto redu e:

D0

Γ ⊢

a

D1

Γ,

a

⊢ b

Γ ⊢ b

cut

wepro eedby aseanalysisonthelastruleusedin

D0, D1

. Thederivation

D0

anendwitha

Zero

rule,a

PrePost

rule,a

Fix

rule,oranIPCrule. Similarly for

D1

. These

4

2

asesarefurthersplit,a ordingtowhether

•

the utformulaistheleftprin ipalformulaof

D0

andtherightprin ipal formulaof

D1

(the essential ase),

•

isnot therightprin ipalformulaof

D0

(the left ommutation ase),or

•

isnot theleftprin ipalformulaof

D1

(the right ommutation ase).

This lassi ationis rather standardin ut-eliminationresults, and isused in [27℄ as well. Note that the two ommutation ases an overlapwhen the ut formulais notright/left prin ipal in both

D0, D1

, respe tively. InTable1,we overallthepossible ases,andgroupthemwheneverthehandlingissimilar.

WenowprovideareadingkeyforTable1. Therstrowdes ribesthe ase where

D0

endswith

Zero

. Inthis ase,the utformulaistherightprin ipal for-mulaof

D0

,andsothereisnoleft ommutation ase,denotedby

∄

(l) . Therst

D

0

\

D

1

Zero PrePost Fix IPC Zero

∄

(l)

∄

(e) */Zero(r) Zero/PrePost(e) */PrePost(r) Zero/Fix(e) */Fix(r)

∄

(e) standard(r) PrePost

∄

(l)

∄

(e) */Zero(r) PrePost/PrePost(e) */PrePost(r) PrePost/Fix(e) */Fix(r)

∄

(e) standard(r) Fix

∄

(e) [Fix/*(l)℄ */Zero(r) Fix/*(l) [*/PrePost(r)℄ Fix/*(l) [*/Fix(r)℄ Fix/*(l) [standard(r)℄ IPC

∄

(e) [standard(l)℄ */Zero(r)

∄

(e) standard(l) [*/PrePost(r)℄

∄

(e) standard(l) [*/Fix(r)℄ standard(e,l,r)

(e)essential,(l)left ommutation,(r) right ommutation,[subsumed℄

Table1: Summaryof asesfor ut-elimination

ellisforthe asewhere

D1

endswith

Zero

aswell: thisisaright ommutation ase whi h is handled in the sameway as

PrePost/Zero

,

Fix/Zero

, et . so we willhaveasingle ase

∗/Zero

aseforthewhole olumn. The

Zero/PrePost

ase anbeanessential aseoraright ommutationdepending onwhetherthe ut formulaistheleftprin ipalformulaof

PrePost

,sowesplitintwosub ases. The right ommutation ase

∗/PrePost

isalsoreusedinotherpointsinthesame ol-umn. Thesameappliesto

Zero/Fix

. The

Zero/IP C

ase annotbeanessential ase,sin e

։

nevero urs inanIPCrule;sothis isaright ommutation.

These ondrowdes ribesthe asewhere

D0

endswith

PrePost

,andissimilar totherstrow.

The third row des ribes the ase where

D0

ends with

Fix

. Sin e

Fix

has no right prin ipal formula, there is no essential ase in this row, denoted by

∄

(e). The ase

Fix/Zero

is both a left and right ommutation ase, whi h we arbitrarily hose to handle asaright ommutation ase. The remaining ases might be right ommutations, but are surely left ommutations

Fix/∗

, so we handlethem inthatway.

Thefourthrowdes ribesthe asewhere

D0

endswithanIPCrule. The ase

IP C/Zero

might bealeft ommutation(dependingonthea tualIPCrule),but is surely a right ommutation aswell, so we handle it in that way. The ase

IP C/PrePost

an not be an essential ase, sin e

։

o urs in no IPC rule; it might bearight ommutation, butis surelyaleft ommutation(noIPC rules involves

։

),sowehandleitinthatway. The ase

IP C/Fix

issimilar. The ase

IP C/IP C

anbeeitheressential,aleft ommutation,oraright ommutation. Weinvitethereaderto he kthatTable1indeedenumeratesallthepossible ases,whi h anthereforebegroupedasfollows:

•

essential:

Zero/PrePost

(e),

Zero/Fix

(e),

PrePost/PrePost

(e),

PrePost/Fix

(e),standard(e)

•

left ommutations:

Fix/∗

(l),standard(l)

•

right ommutations:

∗/Zero

(r),

∗/PrePost

(r),

∗/Fix

(r),standard(r)

Most asesofthestandardgrouparewell-known asesforIPC,andare overed in[27℄,Appendix1. Thisin ludes,forinstan e,theessential ase

∧R/ ∧ L1

,the left ommutation

∧L1/∗

, and theright ommutation

∗/ ∧ R

. Handling these ases herewould essentially amountto opying the whole Appendix 1of [27℄

no a tual ontribution, we will refer to [27℄ when these ases arise, and omit them. For ompleteness,wedo umentinSe t. A.1howto rephrase[27℄inour notation. Finally,re allthatinDef. 6.1wedivergefrom[27℄inafewIPCrules, namely

¬R

and

weakR

. Of ourse, these rules are involved in standard ases whi h are not overedin [27℄, so we shallprovide aredu tionfor these ases. The ase

¬R/∗

annotbealeft ommutation,butit anbeessential(

¬R/¬L

); the ase

∗/¬R

is instead aright ommutation. The ase

∗/weakR

is a right ommutation,while

weakR/∗

isaleft ommutation.

Wenowpro eedbyhandlingallthe asesmentionedabove. Wesometimes write

Γ(p)

insteadof

Γ

tostressthat

p ∈ Γ

.

7.2 The Essential Cases

In these asesthe utformulais (right/left)prin ipal in both thepremises of the ut.

•

Case

Zero/PrePost

D0

Γ ⊢ q

Γ ⊢

p ։ q

Zero

D1

Γ, p ։ q, a ⊢ p

D2

Γ, p ։ q, q ⊢ b

Γ,

p ։ q

⊢ a ։ b

PrePost

Γ ⊢ a ։ b

cut =⇒

D0

Γ ⊢

q

Γ, q ⊢ q

id

Γ, q ⊢

p ։ q

Zero

D2

Γ, q,

p ։ q

⊢ b

Γ,

q

⊢ b

cut1

Γ ⊢ b

cutp

Γ ⊢ a ։ b

Zero

•

Case

Zero/Fix

D0

Γ ⊢ q

Γ ⊢

p ։ q

Zero

D1

Γ, p ։ q, a ⊢ p

D2

Γ, p ։ q, q ⊢ a

Γ,

p ։ q

⊢ a

Fix

Γ ⊢ a

cut =⇒

D0

Γ ⊢

q

Γ, q ⊢ q

id

Γ, q ⊢

p ։ q

Zero

D2

Γ, q,

p ։ q

⊢ a

Γ,

q

⊢ a

cut1

Γ ⊢ a

cutp

•

Case

PrePost/PrePost

. We anassume

(p ։ q) ∈ Γ

.

D0

Γ, a ⊢ p

D1

Γ, q ⊢ b

Γ ⊢

a ։ b

PrePost

D2

Γ, a ։ b, x ⊢ a

D3

Γ, a ։ b, b ⊢ y

Γ,

a ։ b

⊢ x ։ y

PrePost

Γ(p ։ q) ⊢ x ։ y

cut =⇒

ˆ

D0

Γ, x ⊢ p

ˆ

D1

Γ, q ⊢ y

Γ(p ։ q) ⊢ r

PrePost

ˆ

D0

=

D0+

Γ, x, a ⊢ p

D1+

Γ, x, q ⊢ b

Γ, x ⊢

a ։ b

PrePost

D2

Γ, x,

a ։ b

⊢ a

Γ, x ⊢

a

cut1

D0+

Γ, x,

a

⊢ p

Γ, x ⊢ p

cutp

ˆ

D1

=

D1

Γ, q ⊢

b

D0+

Γ, q, b, a ⊢ p

D1+

Γ, q, b, q ⊢ b

Γ, q, b ⊢

a ։ b

PrePost

D3+

Γ, q, b,

a ։ b

⊢ y

Γ, q,

b

⊢ y

cut1

Γ, q ⊢ y

cutp

•

Case

PrePost/Fix

. We anassume

(p ։ q) ∈ Γ

.

D0

Γ, a ⊢ p

D1

Γ, q ⊢ b

Γ ⊢

a ։ b

PrePost

D2

Γ, a ։ b, r ⊢ a

D3

Γ, a ։ b, b ⊢ r

Γ,

a ։ b

⊢ r

Fix

Γ(p ։ q) ⊢ r

cut =⇒

ˆ

D0

Γ, r ⊢ p

ˆ

D1

Γ, q ⊢ r

Γ ⊢ r

Fix

ˆ

D0

=

D0+

Γ, r, a ⊢ p

D1+

Γ, r, q ⊢ b

Γ, r ⊢

a ։ b

PrePost

D2

Γ, r,

a ։ b

⊢ a

Γ, r ⊢

a

cut1

D0+

Γ, r,

a

⊢ p

Γ, r ⊢ p

cutp

ˆ

D1

=

D1

Γ, q ⊢

b

D0+

Γ, q, b, a ⊢ p

D1+

Γ, q, b, q ⊢ b

Γ, q, b ⊢

a ։ b

PrePost

D3+

Γ, q, b,

a ։ b

⊢ r

Γ, q,

b

⊢ r

cut1

Γ, q ⊢ r

cutp

•

standard. Asanti ipated, wereferto [27℄here,but forthe ase

¬R/¬L

, shownbelow.

•

Case

¬R/¬L

D0

Γ, p ⊢ ⊥

Γ ⊢

¬p

¬R

D1

Γ, ¬p ⊢ p

Γ,

¬p

⊢ q

¬L

Γ ⊢ q

cut =⇒

D0

Γ, p ⊢ ⊥

Γ ⊢

¬p

¬R

D1

Γ,

¬p

⊢ p

Γ ⊢

p

cut1

D0

Γ,

p

⊢ ⊥

Γ ⊢ ⊥

cutp

Γ ⊢ q

weakR

7.3 The Left Commutation Cases

Inthese asesthe utformulaisnotarightprin ipalformulaintheleftpremise ofthe ut.

•

Case

Fix/∗

.We an assume

(p ։ q) ∈ Γ

.

D0

Γ, a ⊢ p

D1

Γ, q ⊢ a

Γ ⊢

a

Fix

D2

Γ,

a

⊢ b

∗

Γ(p ։ q) ⊢ b

cut =⇒

Γ, b, p ⊢ p

id

D1+

Γ, b, q ⊢

a

D0+

Γ, b, q,

a

⊢ p

Γ, b, q ⊢ p

cut0

Γ, b ⊢ p

Fix

D1

Γ, q ⊢

a

D2+

Γ, q,

a

⊢ b

Γ, q ⊢ b

cut0

Γ ⊢ b

Fix

•

standard.Asanti ipated,wereferto[27℄here,butforthe ase

weakR/∗

, shownbelow.

•

Case

weakR/∗

D0

Γ ⊢ ⊥

Γ ⊢

p

weakR

D1

Γ,

p

⊢ q

∗

Γ ⊢ q

cut =⇒

D0

Γ ⊢ ⊥

Γ ⊢ q

weakR

7.4 The Right Commutation Cases

Inthese asesthe utformulaisnotaleftprin ipalformulaintherightpremise ofthe ut.

•

Case

∗/Zero

D0

Γ ⊢

a

∗

D1

Γ, a ⊢ q

Γ,

a

⊢ p ։ q

Zero

Γ ⊢ p ։ q

cut =⇒

D0

Γ ⊢

a

D1

Γ,

a

⊢ q

Γ ⊢ q

cut1

Γ ⊢ p ։ q

Zero

•

Case

∗/PrePost

. We anassume

(p ։ q) ∈ Γ

.

D0

Γ ⊢

a

∗

D1

Γ, a, x ⊢ p

D2

Γ, a, q ⊢ y

Γ,

a

⊢ x ։ y

PrePost

Γ(p ։ q) ⊢ x ։ y

cut =⇒

D0+

Γ, x ⊢

a

D1

Γ, x,

a

⊢ p

Γ, x ⊢ p

cut1

D0+

Γ, q ⊢

a

D2

Γ, q,

a

⊢ y

Γ, q ⊢ y

cut1

Γ ⊢ x ։ y

PrePost

•

Case

∗/Fix

. We anassume

(p ։ q) ∈ Γ

.

D0

Γ ⊢

a

∗

D1

Γ, a, r ⊢ p

D2

Γ, a, q ⊢ r

Γ,

a

⊢ r

Fix

Γ(p ։ q) ⊢ r

cut =⇒

D0+

Γ, r ⊢

a

D1

Γ, r,

a

⊢ p

Γ, r ⊢ p

cut1

D0+

Γ, q ⊢

a

D2

Γ, q,

a

⊢ r

Γ, q ⊢ r

cut1

Γ ⊢ r

Fix

•

standard.Asanti ipated,wereferto[27℄here,butforthe ases

∗/weakR

and

∗/¬R

,shownbelow.

•

Case

∗/weakR

D0

Γ ⊢

p

∗

D1

Γ, p ⊢ ⊥

Γ,

p

⊢ q

weakR

Γ ⊢ q

cut =⇒

D0

Γ ⊢

p

D1

Γ,

p

⊢ ⊥

Γ ⊢ ⊥

cut1

Γ ⊢ q

weakR

•

Case

∗/¬R

D0

Γ ⊢

p

D1

Γ, p, q ⊢ ⊥

Γ,

p

⊢ ¬q

¬R

Γ ⊢ ¬q

cut =⇒

D0+

Γ, q ⊢

p

D1

Γ, q,

p

⊢ ⊥

Γ, q ⊢ ⊥

cut1

Γ ⊢ ¬q

¬R

8 Relations with Other Logi s

Inthisse tionweexploretherelationshipsbetweenPCLand otherlogi s. We areinterestedin possiblemappings,toseeifthereis somewaytoen odePCL insomeotherpre-existinglogi . Forinstan e,sin ePCLisadire textensionof IPC,onemightwonderwhetherthenewlyintrodu ed onne tivefor ontra tual impli ation

։

anbeexpressed usingIPC onne tives. Weanswernegatively to this question in Se t. 8.1. In Se t. 8.2 we explore some mappings to the modallogi S4,byextendingawell-knownmappingfromIPC toS4.

In this se tion, when we need to prove tautologies of IPC or S4, we will sometimesresortto anautomati theoremprover. Tothis purpose,weusethe Logi sWorkBen h(LWB)[22℄. TheinterestedreaderwillndinSe t. A.3how toobtainthea tualproofsgenerated byLWB.