[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Open Access
2009 Ramsey's Theorem for Pairs and Provably Recursive Functions
Ulrich Kohlenbach , Alexander Kreuzer
Notre Dame J. Formal Logic 50(4): 427-444 (2009). DOI: 10.1215/00294527-2009-019

Abstract

This paper addresses the strength of Ramsey's theorem for pairs ( R T 2 2 ) over a weak base theory from the perspective of 'proof mining'. Let R T 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 Σ 1 0 -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 -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 R T 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 R T 2 2 that are primitive recursive in f.

Citation Download Citation

Ulrich Kohlenbach . Alexander Kreuzer . "Ramsey's Theorem for Pairs and Provably Recursive Functions." Notre Dame J. Formal Logic 50 (4) 427 - 444, 2009. https://doi.org/10.1215/00294527-2009-019

Information

Published: 2009
First available in Project Euclid: 11 February 2010

zbMATH: 1221.03059
MathSciNet: MR2598872
Digital Object Identifier: 10.1215/00294527-2009-019

Subjects:
Primary: 03F10 , 03F35 , 05D10

Keywords: proof mining , provably recursive functions , Ramsey's Theorem for pairs

Rights: Copyright © 2009 University of Notre Dame

Vol.50 • No. 4 • 2009
Back to Top