𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Monotone simulations of non-monotone proofs

✍ Scribed by Albert Atserias; Nicola Galesi; Pavel Pudlák

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
173 KB
Volume
65
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We show that an LK proof of size m of a monotone sequent (a sequent that contains only formulas in the basis 4; 3) can be turned into a proof containing only monotone formulas of size m Oðlog mÞ and with the number of proof lines polynomial in m: Also we show that some interesting special cases, namely the functional and the onto versions of Pigeonhole Principle and a version of the Matching Principle, have polynomial size monotone proofs. We prove that LK is polynomially bounded if and only if its monotone fragment is.

📜 SIMILAR VOLUMES

Light monotone Dialectica methods for pr
Light monotone Dialectica methods for proof mining
✍ Mircea-Dan Hernest 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB

## Abstract In view of an enhancement of our implementation on the computer, we explore the possibility of an algorithmic optimization of the various proof‐theoretic techniques employed by Kohlenbach for the synthesis of new (and better) effective uniform bounds out of established qualitative proof