Strong reductions and combinatorial principles

2015/04/06 by Damir D. Dzhafarov, Dzhafarov, Damir D.
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1504.01405

openalex publication_date 2015/04/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper is a contribution to the growing investigation of strong reducibilities between Π¹₂ 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 SRT²₂ is not uniformly or strongly computably reducible to D²_

Related

• On uniform relationships between combinatorial problems
• Strong Reductions between Relatives of the Stable Ramsey's Theorem
• The reverse mathematics of Ramsey-type theorems
• Separating principles below Ramsey's Theorem for Pairs
• Partial orders and immunity in reverse mathematics