8
$\begingroup$

In Melliès’ survey Categorical Semantics of Linear Logic, a cut elimination procedure for intuitionistic linear logic is given which includes the following case:

3.9.3 Promotion vs. contraction

The proof $$ \displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{\displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B}}{\Upsilon_1 , !A , \Upsilon_2 \vdash B} \text{ Contraction} }{ \Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B } \text{ Cut} $$ is transformed into the proof $$ \displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{ \displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion} \qquad \displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B} }{ \Upsilon_1 , !A , !\Gamma , \Upsilon_2 \vdash B } \text{ Cut} }{ \displaystyle\frac{\Upsilon_1 , !\Gamma , !\Gamma , \Upsilon_2 \vdash B}{\Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B} \rlap{\;\text{ Series of Contractions and Exchanges}} } \text{ Cut} $$

Why is this a valid inductive step? Neither the size of the cut formula nor the sizes of the derivations are decreasing. (In the transformed proof, the right branch of the lower cut is potentially larger after inductively eliminating the upper cut.) So it's not clear why this procedure should terminate.

Improve this question
$\endgroup$
9
  • $\begingroup$ Just had a quick look and this is a long time since I haven't read such formalism but I got the impression that the goal here is to remove the cut after a Promotion vs Contraction. In this case, the transformation works as every contraction is now under the cut so the cuts goes up in the derivation tree and are inductively eliminated. $\endgroup$
    – holf
    Commented Jan 20, 2017 at 10:53
  • $\begingroup$ The problem is that in the transformed proof, the right branch of the lower cut is potentially larger after inductively eliminating the upper cut. (Will add this in clarification.) $\endgroup$
    – Sebastien Zany
    Commented Jan 20, 2017 at 11:11
  • 3
    $\begingroup$ Yes, but the number of contractions have been reduced by one. As far as I can tell (again, I did not go too much into details), no other transformations increase the number of contractions. So if you look at the value (#contraction, whatever_you_need_for_the_rest), then this value always decreases in the lexicographical order, so it will terminates at some point. $\endgroup$
    – holf
    Commented Jan 20, 2017 at 12:05
  • 2
    $\begingroup$ Besides what holf and Neel said, doesn't a variation of the usual (degree,rank) argument work? I mean, what's the difference between this step and the usual elimination of a cut on a contraction in LJ? (I mean Gentzen's intuitionistic sequent calculus) $\endgroup$
    – Damiano Mazza
    Commented Jan 20, 2017 at 18:42
  • 1
    $\begingroup$ But how do you eliminate the cut B? The only thing it seems you can do in the Promotion-Cut case is to swap the positions of the two cuts A and B. But then, you end up in the exact same situation. If you eliminate B (which is now above), you may increase the number of contractions above A. $\endgroup$
    – Jérôme Fortier
    Commented Jun 19, 2017 at 14:13

1 Answer 1

Reset to default
4
$\begingroup$

I extend what I wrote as a comment. As there is a great number of cases in the proof, I only give an idea of why this transformation terminates. The short answer is:

In the case promotion vs contraction, after the transformation, the number of contractions in the part of the proof containing cuts has decreased by one.

To go a bit more into details, I would say that you were mistaken because you thought that either the number of cuts or the size of the proof should decrease in order to ensure termination. However, termination can be proven by looking at other parameters of the proof.

If you want to prove termination, you only have to show that each rule will be applied a finite number of time. You can prove that the transformation rule promotion vs contraction will be applied at most m times, where m is the number of contractions in your initial proof. To prove this, you just have to observe that no rule introduces a new contraction in proof tree. And this one decreases the number of contraction by one. You can do this trick for any other rules "promotion vs sthg" to prove that this one will be applied only a finite number of time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.