Strong Reductions between Relatives of the Stable Ramsey's Theorem

2017/11/17 by David J. Nichols, Nichols, David
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.1711.06532

openalex publication_date 2017/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A complete analysis is given of the computable reductions that hold between SRT²₂, SPT²₂, and SIPT²₂. In particular, while D²₂≤_{\rm sW}SIPT²₂≤_{\rm sW}SPT²₂≤_{\rm sW}SRT²₂, it is shown that SRT²₂\not≤_{\rm sc}SPT²₂\not≤_{\rm sc}SIPT²₂\not≤_{\rm sc}D²₂.

Related

• Strong reductions and combinatorial principles
• The strength of Ramsey's theorem for pairs and arbitrarily many colors
• Ramsey's theorem for singletons and strong computable reducibility
• Conservation of Ramsey's theorem for pairs and well-foundedness
• Stable Ramsey's theorem and measure