Cone avoiding closed sets

DOI10.1090/S0002-9947-2014-06049-2MaRDI QIDQ5496642zbMATH OpenFDO

Authors Lu Liu

Publication date 2 February 2015

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.03777

zbMATH Keywords

Martin-Löf randomnessRamsey's theoremrandomness extractionweak weak König's lemma

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Models of arithmetic and set theory (03C62) Algorithmic randomness and dimension (03D32) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: We prove that for an arbitrary subtree $T$ of $2^{<omega}$ with each element extendable to a path, a given countable class $mathcalM$ closed under disjoint union, and any set $A$, if none of the members of $mathcalM$ strongly $k$-enumerate $T$ for any $k$, then there exists an infinite set contained in either $A$ or $$ such that for every $CinmathcalM$, $CoplusG$ also does not strongly $k$-enumerate $T$. We give applications of this result, which include: (1) $mathsfR{T}_2^2$ doesn't imply $mathsfWWK{L}_0$; (2) (Ambos-Spies et al.2004) $mathsfDNR$ is strictly weaker than $mathsfWWK{L}_0$; (3) (Kjos-Hanssen 2009) for any Martin-L"{o}f random set $A$ either $A$ or $$ contains an infinite subset that does not compute any Martin-L"{o}f random set; etc. We also discuss further generalizations of this result.

Recommendations

• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• Comparing DNR and WWKL
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
• Infinite subsets of random sets of integers
• Extracting randomness within a subset is hard

Cites work

• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• A fixed-point-free minimal degree
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• A strong law of computationally weak subsets
• Algorithmic randomness and complexity.
• Comparing DNR and WWKL
• Computability and Randomness
• Corrigendum to: ``On the strength of Ramsey's theorem for pairs
• Diagonally non-recursive functions and effective Hausdorff dimension
• Enumerations of the Kolmogorov function
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• scientific article; zbMATH DE number 1670880 (Why is no real title available?)
• scientific article; zbMATH DE number 3930883 (Why is no real title available?)
• scientific article; zbMATH DE number 3536056 (Why is no real title available?)
• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• Infinite subsets of random sets of integers
• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• Ramsey's theorem and cone avoidance
• Ramsey's theorem and recursion theory
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs

Cited in

(19)

• Infinite subsets of random sets of integers
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• Thin set versions of Hindman's theorem
• Pigeons do not jump high
• Coloring trees in reverse mathematics
• The reverse mathematics of non-decreasing subsequences
• Extracting randomness within a subset is hard
• Some Questions in Computable Mathematics
• Partial orders and immunity in reverse mathematics
• On the uniform computational content of Ramsey's theorem
• On the logical strengths of partial solutions to mathematical problems
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
• An inside/outside Ramsey theorem and recursion theory
• Relationships between computability-theoretic properties of problems
• THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS
• Computing sets from all infinite subsets
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Open questions about Ramsey-type statements in reverse mathematics
• (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE

This page was built for publication: Cone avoiding closed sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496642)