Cohesive sets and rainbows

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

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

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2013.06.002

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,100

External links

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

Through your library

My notes

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.
The cohesive principle and the Bolzano‐Weierstraß principle.Alexander P. Kreuzer - 2011 - Mathematical Logic Quarterly 57 (3):292-298.
Review: Robert I. Soare, Recursion Theory and Dedekind Cuts; Robert I. Soare, Cohesive Sets and Recursively Enumerable Dedekind Cuts. [REVIEW]Brian H. Mayoh - 1971 - Journal of Symbolic Logic 36 (1):148-148.
On rainbows and the sacraments: From the semiology of the'Logique de Port-Royal'to Pascal's theory of figures.T. Shiokawa - 1997 - Revue Internationale de Philosophie 51 (199):77-99.
About the coexistence of “classical sets” with “non-classical” ones: A survey.Roland Hinnion - 2003 - Logic and Logical Philosophy 11:79-90.
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.

Analytics

Added to PP
2013-12-12

Downloads
17 (#871,044)

6 months
1 (#1,475,085)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

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

References found in this work

Subsystems of Second Order Arithmetic.Stephen G. Simpson - 1999 - Studia Logica 77 (1):129-129.
On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.

View all 12 references / Add more references