On the Strength of Ramsey's Theorem

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

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,181

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 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
2010-08-24

Downloads
53 (#219,508)

6 months
1 (#414,449)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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.
Ramsey's Theorem and Cone Avoidance.Damir Dzhafarov & Carl Jockusch Jr - 2009 - Journal of Symbolic Logic 74 (2):557 - 578.
Forcing in Proof Theory.Jeremy Avigad - 2004 - Bulletin of Symbolic Logic 10 (3):305-333.

View all 41 citations / Add more citations