Fast cut-elimination by projection (Q4362908)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1086658
Language Label Description Also known as
default for all languages
No label defined
    English
    Fast cut-elimination by projection
    scientific article; zbMATH DE number 1086658

      Statements

      0 references
      0 references
      14 June 1998
      0 references
      fast cut elimination
      0 references
      Kalmar elementary bound
      0 references
      cut-projection
      0 references
      Skolemization
      0 references
      exponential bounds
      0 references
      Statman's sequence of sequents
      0 references
      Fast cut-elimination by projection (English)
      0 references
      Gentzen's procedure for cut-elimination is applicable to all proofs, and it is independent of the over-all forms of proofs and natures of end-sequents. However, the resulting proof can be very long. Indeed, sometimes its length cannot be bound by any (Kalmar) elementary function. The authors give a new procedure applicable to proofs in QMON, using methods like cut-projection and Skolemization in proofs, that gives cut-free proofs with exponential bounds on the length. To demonstrate the efficiency of the new procedure, they apply these two procedures to Statman's sequence of sequents [\textit{R. Statman}, Proc. Am. Math. Soc. 75, 104-107 (1979; Zbl 0411.03048)]. The definition of QMON is rather involved. Roughly, a proof is in QMON when all cut formulas are written in terms of \(\wedge\), \(\vee\), \(\forall\), \(\exists\), and the end-sequent has a specified form. By Skolemization, they mean to substitute Skolem functions in eigen-variables and to drop the quantifications. The authors give an example which illustrates cut-projection: In the cut formula, \(\exists xP(x)\) occurs as a subformula and \(\exists x\) is introduced from a unique formula \(P(t)\). In such a case, replace \(\exists xP(x)\) by \(P(t)\) throughout, and obtain a shorter proof with a new cut formula. For the entire collection see [Zbl 0868.00033].
      0 references

      Identifiers