Ramsey's Theorem for Pairs and Provably Recursive Functions

Notre Dame Journal of Formal Logic 50 (4):427-444 (2009)
  Copy   BIBTEX

Abstract

This paper addresses the strength of Ramsey's theorem for pairs ($RT^2_2$) over a weak base theory from the perspective of 'proof mining'. Let $RT^{2-}_2$ denote Ramsey's theorem for pairs where the coloring is given by an explicit term involving only numeric variables. We add this principle to a weak base theory that includes weak König's Lemma and a substantial amount of $\Sigma^0_1$-induction (enough to prove the totality of all primitive recursive functions but not of all primitive recursive functionals). In the resulting theory we show the extractability of primitive recursive programs and uniform bounds from proofs of $\forall\exists$-theorems. There are two components of this work. The first component is a general proof-theoretic result, due to the second author, that establishes conservation results for restricted principles of choice and comprehension over primitive recursive arithmetic PRA as well as a method for the extraction of primitive recursive bounds from proofs based on such principles. The second component is the main novelty of the paper: it is shown that a proof of Ramsey's theorem due to Erdős and Rado can be formalized using these restricted principles. So from the perspective of proof unwinding the computational content of concrete proofs based on $RT^2_2$ the computational complexity will, in most practical cases, not go beyond primitive recursive complexity. This even is the case when the theorem to be proved has function parameters f and the proof uses instances of $RT^2_2$ that are primitive recursive in f

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,623

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

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
On Rudimentarity, Primitive Recursivity and Representability.Saeed Salehi - 2020 - Reports on Mathematical Logic 55:73–85.
Provably total functions of Basic Arithemtic.Saeed Salehi - 2003 - Mathematical Logic Quarterly 49 (3):316.
Completeness of the primitive recursive $$omega $$ ω -rule.Emanuele Frittaion - 2020 - Archive for Mathematical Logic 59 (5-6):715-731.
Primitive Recursion and the Chain Antichain Principle.Alexander P. Kreuzer - 2012 - Notre Dame Journal of Formal Logic 53 (2):245-265.
A Simple Proof of Parsons' Theorem.Fernando Ferreira - 2005 - Notre Dame Journal of Formal Logic 46 (1):83-91.

Analytics

Added to PP
2010-09-13

Downloads
41 (#385,398)

6 months
3 (#1,257,776)

Historical graph of downloads
How can I increase my downloads?