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 |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
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.
Citations of this work BETA
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.
The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - Journal of Symbolic Logic 74 (4):1310 - 1324.
View all 30 citations / Add more citations
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 index
2010-08-24
Total views
47 ( #213,598 of 2,411,290 )
Recent downloads (6 months)
3 ( #244,435 of 2,411,290 )
2010-08-24
Total views
47 ( #213,598 of 2,411,290 )
Recent downloads (6 months)
3 ( #244,435 of 2,411,290 )
How can I increase my downloads?
Downloads