Computable reductions and reverse mathematics

DOI10.1007/978-3-319-40189-8_19MaRDI QIDQ3188256zbMATH OpenOpenAlexFDO

Authors Reed Solomon

Publication date 17 August 2016

Published in Pursuit of the Universal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-40189-8_19

Mathematics Subject Classification ID

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

Recommendations

• Strong reductions between combinatorial principles
• The weakness of being cohesive, thin or free in reverse mathematics
• Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• On notions of computability-theoretic reduction between Π21 principles
• Combinatorial principles weaker than Ramsey's Theorem for pairs

Cites work

• A _2⁰ set with no infinite low subset in either it or its complement
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• On notions of computability-theoretic reduction between Π21 principles
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• On the strength of Ramsey's theorem for pairs
• On uniform relationships between combinatorial problems
• Ramsey's theorem for singletons and strong computable reducibility
• Strong reductions between combinatorial principles
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• The uniform content of partial and linear orders
• The weakness of being cohesive, thin or free in reverse mathematics

Cited in

(15)

• Wadge reducibility and infinite computations
• The uniform content of partial and linear orders
• Reverse mathematics of matroids
• Strong reductions between combinatorial principles
• Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• scientific article; zbMATH DE number 619555 (Why is no real title available?)
• Weihrauch Complexity in Computable Analysis
• Relationships between computability-theoretic properties of problems
• Reverse Mathematics
• Compositions of multivalued functions
• The Complexity of Satisfaction Problems in Reverse Mathematics
• Notions of robust information coding
• Induction, bounding, weak combinatorial principles, and the homogeneous model theorem
• Separating principles below Ramsey's theorem for pairs
• Logical Approaches to Computational Barriers

This page was built for publication: Computable reductions and reverse mathematics

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