RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS

DOI10.1017/jsl.2020.38OpenAlexW3092261656MaRDI QIDQ5070462

Dan Turetsky, Noam Greenberg, Ludovic Patey, Matthew Harrison-Trainor, Rodney G. Downey

Publication date: 12 April 2022

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

conecomputability theoryreverse mathematicshyperimmunity

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Thin set theorems and cone avoidance

Cites Work

• The weakness of being cohesive, thin or free in reverse mathematics
• The thin set theorem for pairs implies DNR
• Density of the cototal enumeration degrees
• On the strength of Ramsey's theorem
• Some logically weak Ramseyan theorems
• On the strength of Ramsey's theorem for pairs
• Computational randomness and lowness
• RT₂² does not imply WKL₀
• Partial Orders and Immunity in Reverse Mathematics
• Retraceable Sets
• Lowness and nullsets
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• Ramsey's theorem and cone avoidance
• Reducibility and Completeness for Sets of Integers
• Iterative forcing and hyperimmunity in reverse mathematics
• On cototality and the skip operator in the enumeration degrees
• Thin set theorems and cone avoidance
• SEPARATING PRINCIPLES BELOW RAMSEY'S THEOREM FOR PAIRS
• Cone avoiding closed sets
• Semirecursive Sets and Positive Reducibility
• Arithmetical Reducibilities I
• ∏ 0 1 Classes and Degrees of Theories
• Ramsey's theorem and recursion theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item