On notions of computability-theoretic reduction between Π21 principles

DOI10.1142/S0219061316500021zbMath1373.03068MaRDI QIDQ3186057

Denis R. Hirschfeldt, Carl G. jun. Jockusch

Publication date: 8 August 2016

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

zbMATH Keywords

Ramsey's theoremWeihrauch reducibilitystrong reducibilityKönig's lemmacomputable reducibilityuniform reducibility

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) 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)

Related Items (25)

An inside/outside Ramsey theorem and recursion theory ⋮ Reduction games, provability and compactness ⋮ Computable Reductions and Reverse Mathematics ⋮ Generalized Effective Reducibility ⋮ RAMSEY-LIKE THEOREMS AND MODULI OF COMPUTATION ⋮ Iterative Forcing and Hyperimmunity in Reverse Mathematics ⋮ The uniform content of partial and linear orders ⋮ Dominating the Erdős-Moser theorem in reverse mathematics ⋮ A topological view on algebraic computation models ⋮ Algebraic properties of the first-order part of a problem ⋮ Ramsey’s theorem for singletons and strong computable reducibility ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective ⋮ Induction, Bounding, Weak Combinatorial Principles, and the Homogeneous Model Theorem ⋮ Some Questions in Computable Mathematics ⋮ Borel-Piecewise Continuous Reducibility for Uniformization Problems ⋮ The weakness of being cohesive, thin or free in reverse mathematics ⋮ Using Ramsey's theorem once ⋮ On uniform relationships between combinatorial problems ⋮ \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models ⋮ Effectiveness for the dual Ramsey theorem ⋮ A note on the diamond operator ⋮ COH, SRT 2 2 , and multiple functionals ⋮ Weihrauch Complexity in Computable Analysis ⋮ Lawvere-Tierney topologies for computability theorists

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The weakness of being cohesive, thin or free in reverse mathematics
• Classical recursion theory. The theory of functions and sets of natural numbers
• On the uniform computational content of computability theory
• On uniform relationships between combinatorial problems
• Ramsey’s theorem for singletons and strong computable reducibility
• Algorithmic Randomness and Complexity
• Slicing the Truth
• Partition Theorems and Computability Theory
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• Corrigendum to: “On the strength of Ramsey's Theorem for pairs”
• ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM
• Notions of robust information coding
• OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS
• Induction, Bounding, Weak Combinatorial Principles, and the Homogeneous Model Theorem

This page was built for publication: On notions of computability-theoretic reduction between Π21 principles