𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Overspill Principles and Axiom Schemes for Bounded Formulas

✍ Scribed by Joaquín Borrego-Díaz; Alejandro Fernández-Margarit; Mario Pérez-Jiménez

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
376 KB
Volume
42
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

We study the theories IV,, LV, and overspill principles for 0, formulas. We show that IE, LV, j IV,, but we do not know if IV, j LVn. We introduce a new scheme, the growth scheme Crr, and we prove that LV, CrVn * IV,. Also, we analyse the utility of bounded collection axioms for the study of the above theories.

📜 SIMILAR VOLUMES

Improved bounds on the Weak Pigeonhole P
Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms
✍ Albert Atserias 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 158 KB

We show that the known bounded-depth proofs of the Weak Pigeonhole Principle PHP 2n n in size n O(log(n)) are not optimal in terms of size. More precisely, we give a size-depth trade-o upper bound: there are proofs of size n O(d(log(n)) 2=d ) and depth O(d). This solves an open problem of Maciel et