RT₂² does not imply WKL₀

Journal of Symbolic Logic 77 (2):609-620 (2012)
  Copy   BIBTEX

Abstract

We prove that RCA₀ + RT $RT\begin{array}{*{20}{c}} 2 \\ 2 \\ \end{array} $ ̸͢ WKL₀ by showing that for any set C not of PA-degree and any set A, there exists an infinite subset G of A or ̅Α, such that G ⊕ C is also not of PA-degree

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1333566640

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,867

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

On the strength of Ramsey's theorem for pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
Slicing the truth: on the computable and reverse mathematics of combinatorial principles.Denis Roman Hirschfeldt - 2015 - [Hackensack,] NJ: World Scientific. Edited by C.-T. Chong.
On the strength of Ramsey's theorem for pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
Combinatorial principles weaker than Ramsey's Theorem for pairs.Denis R. Hirschfeldt & Richard A. Shore - 2007 - Journal of Symbolic Logic 72 (1):171-206.
Constructing sequences one step at a time.Henry Towsner - 2020 - Journal of Mathematical Logic 20 (3):2050017.
How Strong is Ramsey’s Theorem If Infinity Can Be Weak?Leszek Aleksander Kołodziejczyk, Katarzyna W. Kowalik & Keita Yokoyama - 2023 - Journal of Symbolic Logic 88 (2):620-639.
Generics for computable Mathias forcing.Peter A. Cholak, Damir D. Dzhafarov, Jeffry L. Hirst & Theodore A. Slaman - 2014 - Annals of Pure and Applied Logic 165 (9):1418-1428.
$\Pi ^{0}_{1}$ -Encodability and Omniscient Reductions.Benoit Monin & Ludovic Patey - 2019 - Notre Dame Journal of Formal Logic 60 (1):1-12.
On notions of computability-theoretic reduction between Π21 principles.Denis R. Hirschfeldt & Carl G. Jockusch - 2016 - Journal of Mathematical Logic 16 (1):1650002.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.

Analytics

Added to PP
2012-04-05

Downloads
170 (#114,813)

6 months
11 (#340,569)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Cohesive sets and rainbows.Wei Wang - 2014 - Annals of Pure and Applied Logic 165 (2):389-408.
Ramsey-type graph coloring and diagonal non-computability.Ludovic Patey - 2015 - Archive for Mathematical Logic 54 (7-8):899-914.
The Thin Set Theorem for Pairs Implies DNR.Brian Rice - 2015 - Notre Dame Journal of Formal Logic 56 (4):595-601.

View all 13 citations / Add more citations

References found in this work

No references found.

Add more references