Ordinal notations and well-orderings in bounded arithmetic

Annals of Pure and Applied Logic 120 (1-3):197-223 (2003)
  Copy   BIBTEX

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 PLS

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,168

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Dynamic ordinal analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Normal forms for elementary patterns.Timothy J. Carlson & Gunnar Wilken - 2012 - Journal of Symbolic Logic 77 (1):174-194.
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.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.

Analytics

Added to PP
2014-01-16

Downloads
18 (#614,279)

6 months
1 (#448,551)

Historical graph of downloads
How can I increase my 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.

Add more citations

References found in this work

Proof Theory.K. Schütte - 1977 - Springer Verlag.
Systems of predicative analysis.Solomon Feferman - 1964 - Journal of Symbolic Logic 29 (1):1-30.

Add more references