\(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
type: Item
instance of: scholarly article
zbMATH Open document ID: 1245.03095
author: Jiayi Liu
publication date: 2012-06-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/1602.03784
full work available at URL: https://projecteuclid.org/euclid.jsl/1333566640
Mathematics Subject Classification ID: 03F35
Mathematics Subject Classification ID: 03B30
Mathematics Subject Classification ID: 03C62
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D80
zbMATH DE Number: 6047779
zbMATH Keywords: recursion theory
zbMATH Keywords: computability
zbMATH Keywords: reverse mathematics
zbMATH Keywords: Ramsey
zbMATH Keywords: weak König's lemma
zbMATH Keywords: RCA
zbMATH Keywords: WKL
zbMATH Keywords: Mathias forcing
zbMATH Keywords: PA degree
zbMATH Keywords: cone avoidance
MaRDI profile type: Publication
OpenAlex ID: W1560798351
arXiv ID: 1602.03784
cites work: Q4220572
cites work: On the strength of Ramsey's theorem
cites work: On the strength of Ramsey's theorem for pairs
DOI: 10.2178/JSL/1333566640
Recommended article: Q4522570
Recommended article: \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
Recommended article: Q4273183
Recommended article: \(\{e^{\pm i(n- 1/4)t} \}_{n\in \mathbb{N}}\) is not a basis of \(L^ 2[- \pi,\pi]\)
Recommended article: A characterization of \(P^ 2(\mu)\neq L^ 2(\mu)\)
Recommended article: \(D^*(\mathbb{R};\leq)\) does not imply \(D_ 1^*\)
Recommended article: Q4391555
Recommended article: On Karoubi's theorem: \(W(A)=W(A[t])\)
Recommended article: Weak rational ergodicity does not imply rational ergodicity
Recommended article: NO ZERO DIVISOR FOR WICK PRODUCT IN (S)*
title: \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
published in: The Journal of Symbolic Logic
review text: In this article, the author settles a long-standing question in reverse mathematics by showing that \(\text{RCA}_0\) plus \(\text{RT}^2_\infty\) (Ramsey's theorem for pairs for an arbitrary number of colors) does not prove \( \text{WKL}_0\) (weak König's lemma). He does this by constructing an \(\omega\)-model of \(\text{RCA}_0 + \text{RT}^2_2\) in which the set universe avoids all cones above PA degrees. The construction relies on the following central computability-theoretic result: If \(C\) is not of PA degree and \(A\) is any set then there is an infinite set \(G\) such that \(G \oplus C\) is not of PA degree and \(G\) is either a subset of \(A\) or disjoint from \(A\). The proof of this theorem uses a Mathias forcing argument based on techniques previously used by \textit{D. Seetapun} and \textit{T. A. Slaman} [``On the strength of Ramsey's theorem'', Notre Dame J. Formal Logic 36, No. 4, 570--582 (1995; Zbl 0843.03034)], \textit{P. A. Cholak}, \textit{C. G. Jockusch} and \textit{T. A. Slaman} [``On the strength of Ramsey's theorem for pairs'', J. Symb. Log. 66, No. 1, 1--55 (2001; Zbl 0977.03033)] and \textit{D. D. Dzhafarov} and \textit{C. G. Jockusch} [``Ramsey's theorem and cone avoidance'', J. Symb. Log. 74, No. 2, 557--578 (2009; Zbl 1166.03021)]. The article assumes familiarity with this previous work.
reviewed by: Jeffry L. Hirst
description: scientific article; zbMATH DE number 6047779