Mathematical Logic Quarterly 54 (6):629-640 (2008)

In this paper we show some non-elementary speed-ups in logic calculi: Both a predicative second-order logic and a logic for fixed points of positive formulas are shown to have non-elementary speed-ups over first-order logic. Also it is shown that eliminating second-order cut formulas in second-order logic has to increase sizes of proofs super-exponentially, and the same in eliminating second-order epsilon axioms. These are proved by relying on results due to P. Pudlák
Keywords epsilon calculi  second‐order logic  Speed‐up
Categories (categorize this paper)
DOI 10.1002/malq.200710067
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 61,089
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Elimination Theorems of Uniqueness Conditions.Nobuyoshi Motohashi - 1982 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 28 (33-38):511-524.
Elimination Theorems of Uniqueness Conditions.Nobuyoshi Motohashi - 1982 - Mathematical Logic Quarterly 28 (33‐38):511-524.

View all 7 references / Add more references

Citations of this work BETA

Intuitionistic Fixed Point Theories Over Set Theories.Toshiyasu Arai - 2015 - Archive for Mathematical Logic 54 (5-6):531-553.

Add more citations

Similar books and articles

Analytic Calculi for Product Logics.George Metcalfe, Nicola Olivetti & Dov Gabbay - 2004 - Archive for Mathematical Logic 43 (7):859-889.
Epsilon Calculi.Hartley Slater - 2001 - Internet Encyclopedia of Philosophy.
Epsilon Calculi.Barry Hartley - 2006 - Logic Journal of the IGPL 14 (4):535-590.
Metafizyka w logice.Jacek Wojtysiak - 1999 - Filozofia Nauki 1.
Analytic Combinatory Calculi and the Elimination of Transitivity.Pierluigi Minari - 2004 - Archive for Mathematical Logic 43 (2):159-191.
Display Calculi for Logics with Relative Accessibility Relations.Stéphane Demri & Rajeev Goré - 2000 - Journal of Logic, Language and Information 9 (2):213-236.
Some Results on Measure Independent Gödel Speed-Ups.Martin K. Solomon - 1978 - Journal of Symbolic Logic 43 (4):667-672.


Added to PP index

Total views
14 ( #697,547 of 2,440,210 )

Recent downloads (6 months)
1 ( #432,124 of 2,440,210 )

How can I increase my downloads?


My notes