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

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(02)00066-0

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,990

External links

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

Through your library

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.
Beckmann, A., Pollett, C. and Buss, SR, Ordinal notations.S. R. Buss - 2003 - Annals of Pure and Applied Logic 120:285.
Dynamic ordinal analysis.Arnold Beckmann - 2003 - Archive for Mathematical Logic 42 (4):303-334.
Elementary descent recursion and proof theory.Harvey Friedman & Michael Sheard - 1995 - Annals of Pure and Applied Logic 71 (1):1-45.
On the provability logic of bounded arithmetic.Rineke Verbrugge & Alessandro Berarducci - 1991 - Annals of Pure and Applied Logic 61 (1-2):75-93.
Ordinal arithmetic and $\Sigma_{1}$ -elementarity.Timothy J. Carlson - 1999 - Archive for Mathematical Logic 38 (7):449-460.
Σ 1 -elementarity and Skolem hull operators.Gunnar Wilken - 2007 - Annals of Pure and Applied Logic 145 (2):162-175.
Systems of iterated projective ordinal notations and combinatorial statements about binary labeled trees.L. Gordeev - 1989 - Archive for Mathematical Logic 29 (1):29-46.
An ordinal analysis of admissible set theory using recursion on ordinal notations.Jeremy Avigad - 2002 - Journal of Mathematical Logic 2 (1):91-112.

Analytics

Added to PP
2014-01-16

Downloads
29 (#538,959)

6 months
10 (#382,663)

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 - New York: Springer Verlag.
Systems of predicative analysis.Solomon Feferman - 1964 - Journal of Symbolic Logic 29 (1):1-30.

Add more references