Strong reductions between combinatorial principles

DOI10.1017/JSL.2016.1MaRDI QIDQ2976339zbMATH OpenOpenAlexFDO

Authors Damir D. Dzhafarov

Publication date 28 April 2017

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

Full work available at URL https://arxiv.org/abs/1504.01405, https://semanticscholar.org/paper/2ca6858ede30e7e7ff273d0981682dd6a8e621e5

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)

Abstract: This paper is a contribution to the growing investigation of strong reducibilities between $P{i}_2^1$ statements of second-order arithmetic, viewed as an extension of the traditional analysis of reverse mathematics. We answer several questions of Hirschfeldt and Jockusch (to appear) about uniform and strong computable reductions between various combinatorial principles related to Ramsey's theorem for pairs. Among other results, we establish that the principle $mathsf{SRT}_2^2$ is not uniformly or strongly computably reducible to $mathsf{D}_{<infty}^2$, that $mathsfCOH$ is not uniformly reducible to $mathsf{D}_{<infty}^2$, and that $mathsfCOH$ is not strongly reducible to $mathsf{D}_2^2$. The latter also extends a prior result of Dzhafarov (2015). We introduce a number of new techniques for controlling the combinatorial and computability-theoretic properties of the problems and solutions we construct in our arguments.

Recommendations

• Computable reductions and reverse mathematics
• On notions of computability-theoretic reduction between Π21 principles
• The weakness of being cohesive, thin or free in reverse mathematics
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs

Cites work

• Algorithmic randomness and complexity.
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• On the strength of Ramsey's theorem
• Open questions in reverse mathematics
• Probabilistic computability and choice
• Subsystems of second order arithmetic
• The metamathematics of Stable Ramsey’s Theorem for Pairs

Cited in

(29)

• On Weihrauch reducibility and intuitionistic reverse mathematics
• Combinatorics of reductions between equivalence relations
• Some results concerning the \(\mathsf{SRT}_2^2\) vs. \(\mathsf{COH}\) problem
• The definability strength of combinatorial principles
• Barendregt's problem \#26 and combinatory strong reduction
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• The uniform content of partial and linear orders
• An inside/outside Ramsey theorem and recursion theory
• Reduction games, provability and compactness
• Lawvere-Tierney topologies for computability theorists
• Weihrauch and constructive reducibility between existence statements
• Some Questions in Computable Mathematics
• Combinatorial principles equivalent to weak induction
• A solution to Curry and Hindley's problem on combinatory strong reduction
• Computable reductions and reverse mathematics
• Cohesive avoidance and strong reductions
• Strong combinatorial principles and level by level equivalence
• Effectiveness for the dual Ramsey theorem
• Ramsey's theorem for singletons and strong computable reducibility
• Ramsey's theorem and products in the Weihrauch degrees
• The weakness of being cohesive, thin or free in reverse mathematics
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Dominating the Erdős-Moser theorem in reverse mathematics
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• COH, SRT 2 2 , and multiple functionals
• On the uniform computational content of Ramsey's theorem
• Weihrauch Complexity in Computable Analysis
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• Open questions about Ramsey-type statements in reverse mathematics

This page was built for publication: Strong reductions between combinatorial principles

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