question from Phil Wadler re cut/linear logic

Jeremy DAWSON jeremy at discus.anu.edu.au
Thu Nov 20 10:44:40 EST 2003


> Consider the following proof

   A, A-o!B;|-;!B          ;B|-;!B otimes !B
   ------------------------------------------Cut
   A, A-o!B;|-;!B

But how is this an instance of the Cut rule which you define as

   G;G'|-D';D,A   A,L;G'|-D';P
   ---------------------------Cut
   G,L;G'|-D';D,P


Should this be 
                           ;B|-;!B otimes !B
                           ----------------- !L
   A, A-o!B;|-;!B          !B;|-;!B otimes !B
   ------------------------------------------Cut(a)
   A, A-o!B;|-;!B otimes !B
?

Assuming so, we could obtain 

                           ;B|-;!B otimes !B
                           ----------------- !L
         !B;|-;!B          !B;|-;!B otimes !B
         ------------------------------------Cut(b)
               !B;|-;!B otimes !B
             -----------------------------(...)
             A, A-o!B;|-;!B otimes !B

where (...) represents the derivation of 
    A, A-o!B;|-;!B
which was left unspecified, and assuming that this (...)
derivation could be transformed to a derivation of 
    A, A-o!B;|-;!B otimes !B
from 
    !B;|-;!B otimes !B

>From here we see that the cut(b) is completely superfluous
since its conclusion is the same as its right premise.
Thus we can obtain 

	       ;B|-;!B otimes !B
	       ----------------- !L
               !B;|-;!B otimes !B
             -----------------------------(...)
             A, A-o!B;|-;!B otimes !B

This has now eliminated the cut as long as the moves represented 
by (...) are legal. 

Having looked at Girard's paper we cannot see how to fill in the (...)
moves for deriving 
    A, A-o!B;|-;!B

Jeremy Dawson and  Rajeev Gore 



More information about the Types-list mailing list