A recursion theoretic analysis of the clopen Ramsey theorem

Journal of Symbolic Logic 49 (2):376-400 (1984)
  Copy   BIBTEX

Abstract

Solovay has shown that if F: [ω] ω → 2 is a clopen partition with recursive code, then there is an infinite homogeneous hyperarithmetic set for the partition (a basis result). Simpson has shown that for every 0 α , where α is a recursive ordinal, there is a clopen partition F: [ω] ω → 2 such that every infinite homogeneous set is Turing above 0 α (an anti-basis result). Here we refine these results, by associating the "order type" of a clopen set with the Turing complexity of the infinite homogeneous sets. We also consider the Nash-Williams barrier theorem and its relation to the clopen Ramsey theorem

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,726

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

A generalization of the limit lemma and clopen games.Peter Clote - 1986 - Journal of Symbolic Logic 51 (2):273-291.
An ordinal partition avoiding pentagrams.Jean A. Larson - 2000 - Journal of Symbolic Logic 65 (3):969-978.
Inner models and large cardinals.Ronald Jensen - 1995 - Bulletin of Symbolic Logic 1 (4):393-407.
On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
A game‐theoretic proof of analytic Ramsey theorem.Kazuyuki Tanaka - 1992 - Mathematical Logic Quarterly 38 (1):301-304.
The spectrum of resplendency.John T. Baldwin - 1990 - Journal of Symbolic Logic 55 (2):626-636.
Some Ramsey theory in Boolean algebra for complexity classes.Gregory L. McColm - 1992 - Mathematical Logic Quarterly 38 (1):293-298.
Turing degrees and many-one degrees of maximal sets.Manuel Lerman - 1970 - Journal of Symbolic Logic 35 (1):29-40.

Analytics

Added to PP
2009-01-28

Downloads
21 (#748,435)

6 months
6 (#737,115)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Partial impredicativity in reverse mathematics.Henry Towsner - 2013 - Journal of Symbolic Logic 78 (2):459-488.

Add more citations

References found in this work

Recursive well-founded orderings.Keh-Hsun Chen - 1978 - Annals of Mathematical Logic 13 (2):117-147.
Recursice well-founded orderings.D. -H. Chen - 1978 - Annals of Mathematical Logic 13 (2):117.

Add more references