STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES

DOI10.1017/jsl.2016.1zbMath1368.03044arXiv1504.01405OpenAlexW2559546918MaRDI QIDQ2976339

Damir D. Dzhafarov

Publication date: 28 April 2017

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

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

zbMATH Keywords

computability theoryreverse mathematicsRamsey's theoremWeihrauch reducibilitycomputable reducibility

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (17)

An inside/outside Ramsey theorem and recursion theory ⋮ Reduction games, provability and compactness ⋮ Computable Reductions and Reverse Mathematics ⋮ The uniform content of partial and linear orders ⋮ Dominating the Erdős-Moser theorem in reverse mathematics ⋮ OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS ⋮ Ramsey’s theorem for singletons and strong computable reducibility ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ ON WEIHRAUCH REDUCIBILITY AND INTUITIONISTIC REVERSE MATHEMATICS ⋮ Some Questions in Computable Mathematics ⋮ The weakness of being cohesive, thin or free in reverse mathematics ⋮ \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models ⋮ Effectiveness for the dual Ramsey theorem ⋮ Weihrauch and constructive reducibility between existence statements ⋮ COH, SRT 2 2 , and multiple functionals ⋮ Weihrauch Complexity in Computable Analysis ⋮ Lawvere-Tierney topologies for computability theorists

Cites Work

• Unnamed Item
• On the strength of Ramsey's theorem
• Probabilistic computability and choice
• Algorithmic Randomness and Complexity
• Open Questions in Reverse Mathematics
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• On the role of the collection principle for Σ⁰₂-formulas in second-order reverse mathematics

This page was built for publication: STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES