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
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
0 references
0 references
0.8093147
0 references
0.8092074
0 references
0.8035543
0 references
0 references
0.7955103
0 references
0.79349756
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