Ramsey-type graph coloring and diagonal non-computability

DOI10.1007/s00153-015-0448-5zbMath1342.03015arXiv1412.0917OpenAlexW1717332283MaRDI QIDQ892143

Ludovic Patey

Publication date: 18 November 2015

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

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

zbMATH Keywords

forcinggraph coloringreverse mathematicsbushy treeDNRKönig's lemmaRCOLORRWKL

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

Related Items (7)

Iterative Forcing and Hyperimmunity in Reverse Mathematics ⋮ Dominating the Erdős-Moser theorem in reverse mathematics ⋮ Coloring trees in reverse mathematics ⋮ OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS ⋮ THE STRENGTH OF THE TREE THEOREM FOR PAIRS IN REVERSE MATHEMATICS ⋮ Degrees bounding principles and universal instances in reverse mathematics ⋮ On the logical strengths of partial solutions to mathematical problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diagonally non-computable functions and fireworks
• Infinite subsets of random sets of integers
• Degrees of members of \(\Pi_ 1^ 0\) classes
• COMPARING THE STRENGTH OF DIAGONALLY NONRECURSIVE FUNCTIONS IN THE ABSENCE OF INDUCTION
• Diagonally Non-Computable Functions and Bi-Immunity
• RT₂² does not imply WKL₀
• Separating principles below
• Algorithmic Randomness and Complexity
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• Lowness for Kurtz randomness
• A fixed-point-free minimal degree
• Reverse mathematics and a Ramsey-type König's Lemma
• Comparing DNR and WWKL
• FORCING WITH BUSHY TREES
• SEPARATING PRINCIPLES BELOW RAMSEY'S THEOREM FOR PAIRS

This page was built for publication: Ramsey-type graph coloring and diagonal non-computability