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 theorycomputable reducibilityRamsey's theoremreverse mathematicsWeihrauch reducibility

Mathematics Subject Classification ID

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

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)

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

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)