Some results on cut-elimination, provable well-orderings, induction and reflection

Annals of Pure and Applied Logic 95 (1-3):93-184 (1998)

Abstract
We gather the following miscellaneous results in proof theory from the attic.1. 1. A provably well-founded elementary ordering admits an elementary order preserving map.2. 2. A simple proof of an elementary bound for cut elimination in propositional calculus and its applications to separation problem in relativized bounded arithmetic below S21.3. 3. Equivalents for Bar Induction, e.g., reflection schema for ω logic.4. 4. Direct computations in an equational calculus PRE and a decidability problem for provable inequations in PRE.5. 5. Intuitionistic fixed point theories which are conservative extensions of HA.6. 6. Proof theoretic strengths of classical fixed points theories.7. 7. An equivalence between transfinite induction rule and iterated reflection schema over IΣn.8. 8. Derivation lengths of finite rewrite rules reducing under lexicographic path orders and multiply recursive functions.Each section can be read separately in principle
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(98)00020-7
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,683
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

The Incompleteness Theorems.Craig Smorynski - 1977 - In Jon Barwise (ed.), Handbook of Mathematical Logic. North-Holland. pp. 821 -- 865.
Reflection Principles and Their Use for Establishing the Complexity of Axiomatic Systems.G. Kreisel & A. Lévy - 1968 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 14 (7-12):97-142.
Reflection Principles and Their Use for Establishing the Complexity of Axiomatic Systems.Georg Kreisel & Azriel Lévy - 1968 - Zeitschrift für Mathematische Logic Und Grundlagen der Mathematik 14 (1):97--142.

View all 21 references / Add more references

Citations of this work BETA

Derivatives of Normal Functions and $$\Omega $$ Ω -Models.Toshiyasu Arai - 2018 - Archive for Mathematical Logic 57 (5-6):649-664.
Dynamic Ordinal Analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Intuitionistic Fixed Point Theories Over Set Theories.Toshiyasu Arai - 2015 - Archive for Mathematical Logic 54 (5-6):531-553.
Quick Cut-Elimination for Strictly Positive Cuts.Toshiyasu Arai - 2011 - Annals of Pure and Applied Logic 162 (10):807-815.

View all 8 citations / Add more citations

Similar books and articles

Epsilon Substitution for Transfinite Induction.Henry Towsner - 2004 - Archive for Mathematical Logic 44 (4):397-412.
Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
The Role of Parameters in Bar Rule and Bar Induction.Michael Rathjen - 1991 - Journal of Symbolic Logic 56 (2):715-730.
Intuitionistically Provable Recursive Well-Orderings.Harvey M. Friedman & Andre Scedrov - 1986 - Annals of Pure and Applied Logic 30 (2):165-171.
The Metamathematics of Scattered Linear Orderings.P. Clote - 1989 - Archive for Mathematical Logic 29 (1):9-20.
The Elimination Argument.Andrew M. Bailey - 2014 - Philosophical Studies 168 (2):475-482.
Arithmetical Interpretations of Dynamic Logic.Petr Hájek - 1983 - Journal of Symbolic Logic 48 (3):704-713.

Analytics

Added to PP index
2014-01-16

Total views
17 ( #474,810 of 2,242,825 )

Recent downloads (6 months)
1 ( #1,043,126 of 2,242,825 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature