Strong reductions between combinatorial principles

DOI10.1017/JSL.2016.1zbMATH Open1368.03044arXiv1504.01405OpenAlexW2559546918MaRDI QIDQ2976339FDOQ2976339

Authors: Damir D. Dzhafarov 

Publication date: 28 April 2017

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

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.

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

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

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)

Cites Work

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

Cited In (29)

• 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
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Dominating the Erdős-Moser theorem in reverse mathematics
• 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
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• 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
• Cohesive avoidance and strong reductions
• The weakness of being cohesive, thin or free in reverse mathematics
• 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
• On Weihrauch reducibility and intuitionistic 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)