Ramsey's Theorem and Cone Avoidance

Journal of Symbolic Logic 74 (2):557-578 (2009)
  Copy   BIBTEX

Abstract

It was shown by Cholak, Jockusch, and Slaman that every computable 2-coloring of pairs admits an infinite low₂ homogeneous set H. We answer a question of the same authors by showing that H may be chosen to satisfy in addition $C\,\not \leqslant _T \,H$, where C is a given noncomputable set. This is shown by analyzing a new and simplified proof of Seetapun's cone avoidance theorem for Ramsey's theorem. We then extend the result to show that every computable 2-coloring of pairs admits a pair of low₂ infinite homogeneous sets whose degrees form a minimal pair.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,088

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

Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
On the Ramsey property for sets of reals.Ilias G. Kastanas - 1983 - Journal of Symbolic Logic 48 (4):1035-1045.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
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.
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-09-12

Downloads
52 (#280,502)

6 months
4 (#404,301)

Historical graph of downloads
How can I increase my downloads?

References found in this work

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
A cohesive set which is not high.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.

Add more references