On the Strength of Ramsey's Theorem

Notre Dame Journal of Formal Logic 36 (4):570-582 (1995)

Abstract
We show that, for every partition F of the pairs of natural numbers and for every set C, if C is not recursive in F then there is an infinite set H, such that H is homogeneous for F and C is not recursive in H. We conclude that the formal statement of Ramsey's Theorem for Pairs is not strong enough to prove , the comprehension scheme for arithmetical formulas, within the base theory , the comprehension scheme for recursive formulas. We also show that Ramsey's Theorem for Pairs is strong enough to prove some sentences in first order arithmetic which are not provable within . In particular, Ramsey's Theorem for Pairs is not conservative over for -sentences
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1305/ndjfl/1040136917
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 43,049
Through your library

References found in this work BETA

Ramsey's Theorem and Recursion Theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
A Criterion for Completeness of Degrees of Unsolvability.Richard Friedberg - 1957 - Journal of Symbolic Logic 22 (2):159-160.

Add more references

Citations of this work BETA

The Polarized Ramsey’s Theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
RT2 2 Does Not Imply WKL0.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.
Forcing in Proof Theory.Jeremy Avigad - 2004 - Bulletin of Symbolic Logic 10 (3):305-333.

View all 28 citations / Add more citations

Similar books and articles

On the Ramsey Property for Sets of Reals.Ilias G. Kastanas - 1983 - Journal of Symbolic Logic 48 (4):1035-1045.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
Ramsey's Representation Theorem.Richard Bradley - 2004 - Dialectica 58 (4):483–497.
A New Proof That Analytic Sets Are Ramsey.Erik Ellentuck - 1974 - Journal of Symbolic Logic 39 (1):163-165.
Nonstandard Combinatorics.Joram Hirshfeld - 1988 - Studia Logica 47 (3):221 - 232.
A Recursion Theoretic Analysis of the Clopen Ramsey Theorem.Peter Clote - 1984 - Journal of Symbolic Logic 49 (2):376-400.
The Consistency Strength of an Infinitary Ramsey Property.George Kafkoulis - 1994 - Journal of Symbolic Logic 59 (4):1158-1195.
A Simple Proof and Some Difficult Examples for Hindman's Theorem.Henry Towsner - 2012 - Notre Dame Journal of Formal Logic 53 (1):53-65.
Belief Revision, Non-Monotonic Reasoning, and the Ramsey Test.Charles B. Cross - 1990 - In Kyburg Henry E., Loui Ronald P. & Carlson Greg N. (eds.), Knowledge Representation and Defeasible Reasoning. Kluwer Academic Publishers. pp. 223--244.

Analytics

Added to PP index
2010-08-24

Total views
43 ( #191,313 of 2,260,175 )

Recent downloads (6 months)
3 ( #493,552 of 2,260,175 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature