Ordinal notations and well-orderings in bounded arithmetic
Annals of Pure and Applied Logic 120 (1-3):197-223 (2003)
Abstract
This paper investigates provability and non-provability of well-foundedness of ordinal notations in weak theories of bounded arithmetic. We define a notion of well-foundedness on bounded domains. We show that T21 and S22 can prove the well-foundedness on bounded domains of the ordinal notations below 0 and Γ0. As a corollary, the class of polynomial local search problems, PLS, can be augmented with cost functions that take ordinal values below 0 and Γ0 without increasing the class PLSDOI
10.1016/s0168-0072(02)00066-0
My notes
Similar books and articles
Ordinal notations and well-orderings in bounded arithmetic (vol 120, pg 197, 2003).Arnold Beckmann, Samuel R. Buss & Chris Pollett - 2003 - Annals of Pure and Applied Logic 123 (1-3):291-291.
Erratum to “Ordinal notations and well-orderings in bounded arithmetic” [Annals of Pure and Applied Logic 120 (2003) 197–223]. [REVIEW]Arnold Beckmann, Samuel R. Buss & Chris Pollett - 2003 - Annals of Pure and Applied Logic 123 (1-3):291.
An ordinal analysis of admissible set theory using recursion on ordinal notations.Jeremy Avigad - 2002 - Journal of Mathematical Logic 2 (1):91-112.
Normal forms for elementary patterns.Timothy J. Carlson & Gunnar Wilken - 2012 - Journal of Symbolic Logic 77 (1):174-194.
Ordinal arithmetic with simultaneously defined theta‐functions.Andreas Weiermann & Gunnar Wilken - 2011 - Mathematical Logic Quarterly 57 (2):116-132.
Ordinal arithmetic and $\Sigma_{1}$ -elementarity.Timothy J. Carlson - 1999 - Archive for Mathematical Logic 38 (7):449-460.
Assignment of Ordinals to Patterns of Resemblance.Gunnar Wilken - 2007 - Journal of Symbolic Logic 72 (2):704 - 720.
Beckmann, A., Pollett, C. and Buss, SR, Ordinal notations.S. R. Buss - 2003 - Annals of Pure and Applied Logic 120:285.
Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
An unexpected separation result in Linearly Bounded Arithmetic.Arnold Beckmann & Jan Johannsen - 2005 - Mathematical Logic Quarterly 51 (2):191-200.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
Systems of iterated projective ordinal notations and combinatorial statements about binary labeled trees.L. Gordeev - 1989 - Archive for Mathematical Logic 29 (1):29-46.
Analytics
Added to PP
2014-01-16
Downloads
18 (#614,279)
6 months
1 (#448,551)
2014-01-16
Downloads
18 (#614,279)
6 months
1 (#448,551)
Historical graph of downloads
Citations of this work
The strength of extensionality II—weak weak set theories without infinity.Kentaro Sato - 2011 - Annals of Pure and Applied Logic 162 (8):579-646.
References found in this work
Systems of predicative analysis, II: Representations of ordinals.Solomon Feferman - 1968 - Journal of Symbolic Logic 33 (2):193-220.
