Ramsey-type graph coloring and diagonal non-computability

DOI10.1007/S00153-015-0448-5zbMATH Open1342.03015arXiv1412.0917OpenAlexW1717332283MaRDI QIDQ892143FDOQ892143

Authors: Ludovic Patey 

Publication date: 18 November 2015

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

Abstract: A function is diagonally non-computable (d.n.c.) if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function (DNR_h) implies the Ramsey-type K"onig's lemma (RWKL). In this paper, we prove that for every computable order h, there exists an~$omega$-model of DNR_h which is not a not model of the Ramsey-type graph coloring principle for two colors (RCOLOR2) and therefore not a model of RWKL. The proof combines bushy tree forcing and a technique introduced by Lerman, Solomon and Towsner to transform a computable non-reducibility into a separation over omega-models.

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

Recommendations

• On the strength of Ramsey's theorem for pairs
• Effective versions of Ramsey's Theorem: Avoiding the cone above 0′
• Comparing the strength of diagonally nonrecursive functions in the absence of \(\Sigma_2^0\) induction
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• scientific article; zbMATH DE number 2236643

zbMATH Keywords

graph coloringforcingbushy treereverse mathematicsDNRRCOLORRWKLKönig's lemma

Mathematics Subject Classification ID

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

Cites Work

• Algorithmic randomness and complexity.
• Title not available (Why is that?)
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• Separating principles below Ramsey's theorem for pairs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lowness for Kurtz randomness
• Title not available (Why is that?)
• Diagonally non-computable functions and fireworks
• Comparing DNR and WWKL
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Infinite subsets of random sets of integers
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• Diagonally non-computable functions and bi-immunity
• Reverse mathematics and a Ramsey-type König's lemma
• Forcing with bushy trees
• Comparing the strength of diagonally nonrecursive functions in the absence of \(\Sigma_2^0\) induction
• A fixed-point-free minimal degree
• Separating principles below \(\mathsf{WKL}_0\)

Cited In (10)

• On the logical strengths of partial solutions to mathematical problems
• Forcing with bushy trees
• Comparing the strength of diagonally nonrecursive functions in the absence of \(\Sigma_2^0\) induction
• Dominating the Erdős-Moser theorem in reverse mathematics
• Degrees bounding principles and universal instances in reverse mathematics
• Coloring trees in reverse mathematics
• Iterative forcing and hyperimmunity in reverse mathematics
• The strength of the tree theorem for pairs in reverse mathematics
• Open questions about Ramsey-type statements in reverse mathematics
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q892143)