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 -sentencesDOI
10.1305/ndjfl/1040136917
My notes
Similar books and articles
On the strength of Ramsey's theorem for pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
Random reals, the rainbow Ramsey theorem, and arithmetic conservation.Chris J. Conidis & Theodore A. Slaman - 2013 - Journal of Symbolic Logic 78 (1):195-206.
On the Ramsey property for sets of reals.Ilias G. Kastanas - 1983 - Journal of Symbolic Logic 48 (4):1035-1045.
Martin's axioms, measurability and equiconsistency results.Jaime I. Ihoda & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (1):78-94.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
A new proof that analytic sets are Ramsey.Erik Ellentuck - 1974 - Journal of Symbolic Logic 39 (1):163-165.
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
55 (#216,292)
6 months
3 (#225,816)
2010-08-24
Downloads
55 (#216,292)
6 months
3 (#225,816)
Historical graph of downloads
Citations of this work
On the strength of Ramsey's theorem for pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
The polarized Ramsey’s theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
Ramsey's Theorem and Cone Avoidance.Damir D. Dzhafarov & Carl G. Jockusch - 2009 - Journal of Symbolic Logic 74 (2):557-578.
References found in this work
Classes of Recursively Enumerable Sets and Degrees of Unsolvability.Donald A. Martin - 1966 - Mathematical Logic Quarterly 12 (1):295-310.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
The baire category theorem in weak subsystems of second-order arithmetic.Douglas K. Brown & Stephen G. Simpson - 1993 - Journal of Symbolic Logic 58 (2):557-578.
A criterion for completeness of degrees of unsolvability.Richard Friedberg - 1957 - Journal of Symbolic Logic 22 (2):159-160.
Effective Versions of Ramsey's Theorem: Avoiding the Cone Above $\mathbf{0}$'.Tamara Lakins Hummel - 1994 - Journal of Symbolic Logic 59 (4):1301-1325.