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

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)