Relationships between computability-theoretic properties of problems

DOI10.1017/JSL.2020.38MaRDI QIDQ5070462zbMATH OpenOpenAlexFDO

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

Publication date 12 April 2022

Published in 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)

Recommendations

• Computable reductions and reverse mathematics
• Iterative forcing and hyperimmunity in reverse mathematics
• The weakness of being cohesive, thin or free in reverse mathematics
• Ramsey-like theorems and moduli of computation
• The canonical Ramsey theorem and computability theory

Cites work

• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 2039009 (Why is no real title available?)
• scientific article; zbMATH DE number 2236628 (Why is no real title available?)
• Arithmetical Reducibilities I
• Computational randomness and lowness
• Cone avoiding closed sets
• Density of the cototal enumeration degrees
• Iterative forcing and hyperimmunity in reverse mathematics
• Lowness and nullsets
• On cototality and the skip operator in the enumeration degrees
• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• Partial orders and immunity in reverse mathematics
• Ramsey's theorem and cone avoidance
• Ramsey's theorem and recursion theory
• Reducibility and Completeness for Sets of Integers
• Retraceable Sets
• Semirecursive Sets and Positive Reducibility
• Separating principles below Ramsey's theorem for pairs
• Some logically weak Ramseyan theorems
• Subsystems of second order arithmetic
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• The thin set theorem for pairs implies DNR
• The weakness of being cohesive, thin or free in reverse mathematics
• Thin set theorems and cone avoidance
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(3)

• On relations between properties in transitive Turing machines
• Thin set theorems and cone avoidance
• Relationships between computability-theoretic properties of problems

This page was built for publication: Relationships between computability-theoretic properties of problems

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