Switch to: References

Citations of:

The Strength of the Rainbow Ramsey Theorem

Barbara F. Csima & Joseph R. Mileti

Journal of Symbolic Logic 74 (4):1310 - 1324 (2009)

Add citations

You must login to add citations.

Open questions about Ramsey-type statements in reverse mathematics.Ludovic Patey - 2016 - Bulletin of Symbolic Logic 22 (2):151-169.details Ramsey’s theorem states that for any coloring of then-element subsets of ℕ with finitely many colors, there is an infinite setHsuch that alln-element subsets ofHhave the same color. The strength of consequences of Ramsey’s theorem has been extensively studied in reverse mathematics and under various reducibilities, namely, computable reducibility and uniform reducibility. Our understanding of the combinatorics of Ramsey’s theorem and its consequences has been greatly improved over the past decades. In this paper, we state some questions which naturally arose (...) Download Export citation Bookmark 4 citations
(1 other version)Nonstandard models in recursion theory and reverse mathematics.C. T. Chong, Wei Li & Yue Yang - 2014 - Bulletin of Symbolic Logic 20 (2):170-200.details We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models, and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey’s Theorem for Pairs. Download Export citation Bookmark 3 citations
Cohesive sets and rainbows.Wei Wang - 2014 - Annals of Pure and Applied Logic 165 (2):389-408.details 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 Export citation Bookmark 5 citations
The weakness of the pigeonhole principle under hyperarithmetical reductions.Benoit Monin & Ludovic Patey - 2020 - Journal of Mathematical Logic 21 (3):2150013.details The infinite pigeonhole principle for 2-partitions asserts the existence, for every set A, of an infinite subset of A or of its complement. In this paper, we study the infinite pigeonhole pr... Download Export citation Bookmark 1 citation
(1 other version)Annals of Pure and Applied Logic. [REVIEW]Itay Neeman - 2003 - Bulletin of Symbolic Logic 9 (3):414-416.details Download Export citation Bookmark
On notions of computability-theoretic reduction between Π21 principles.Denis R. Hirschfeldt & Carl G. Jockusch - 2016 - Journal of Mathematical Logic 16 (1):1650002.details Several notions of computability-theoretic reducibility between [Formula: see text] principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: see (...) Download Export citation Bookmark 9 citations
Algorithmic randomness, reverse mathematics, and the dominated convergence theorem.Jeremy Avigad, Edward T. Dean & Jason Rute - 2012 - Annals of Pure and Applied Logic 163 (12):1854-1864.details We analyze the pointwise convergence of a sequence of computable elements of L1 in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA0, each is equivalent to the assertion that every Gδ subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Königʼs lemma relativized to the Turing jump of any set. It is also equivalent to the (...) Download Export citation Bookmark 6 citations
Degrees bounding principles and universal instances in reverse mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.details Download Export citation Bookmark 3 citations

1