Cohesive sets and rainbows

Annals of Pure and Applied Logic 165 (2):389-408 (2014)

Abstract

We study the strength of RRT32, Rainbow Ramsey Theorem for colorings of triples, and prove that RCA0 + RRT32 implies neither WKL0 nor RRT42 source. To this end, we establish some recursion theoretic properties of cohesive sets and rainbows for colorings of pairs. We show that every sequence admits a cohesive set of non-PA Turing degree; and that every ∅′-recursive sequence admits a low3 cohesive set

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,879

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2013-12-12

Downloads
15 (#704,592)

6 months
1 (#386,016)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Degrees Bounding Principles and Universal Instances in Reverse Mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.
The Definability Strength of Combinatorial Principles.Wei Wang - 2016 - Journal of Symbolic Logic 81 (4):1531-1554.

Add more citations

Similar books and articles

Generalized Cohesiveness.Tamara Hummel & Carl G. Jockusch - 1999 - Journal of Symbolic Logic 64 (2):489-516.
Correction to “a Cohesive Set Which is Not High”.Carl Jockusch & Frank Stephan - 1997 - Mathematical Logic Quarterly 43 (4):569-569.
A Cohesive Set Which is Not High.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.
Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry.John P. Burgess - 1988 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
Cohesive Toposes and Cantor's 'Lauter Einsen'.F. W. Lawvere - 1994 - Philosophia Mathematica 2 (1):5-15.
Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
On Subcreative Sets and S-Reducibility.John T. Gill Iii & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669 - 677.
The Ordertype of Β-R.E. Sets.Klaus Sutner - 1990 - Journal of Symbolic Logic 55 (2):573-576.