Ramsey-type graph coloring and diagonal non-computability

DOI10.1007/S00153-015-0448-5MaRDI QIDQ892143zbMATH OpenOpenAlexFDO

Authors 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

bushy treeDNRforcinggraph coloringKönig's lemmaRCOLORreverse mathematicsRWKL

Mathematics Subject Classification ID

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

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.

Review text

For each computable function \(h\), the author uses bushy tree forcing to construct an \(\omega\)-model of RCA\(_0\)+\(h\)-DNR that is not a model of RCOLOR\(_2\). The principle \(h\)-DNR asserts the existence of an \(h\)-bounded d.n.c. function. Given a graph \(G\) with vertices \(V\), a set \(H \subseteq V\) is \(k\)-homogeneous if for every finite \(V_0\subseteq V\) there is a \(k\)-coloring of the vertices of \(G\) restricted to \(V_0\) that is monochromatic on \(V_0 \cap H\). The principle RCOLOR\(_k\) asserts that every locally \(k\)-colorable graph has an infinite \(k\)-homogeneous set. For \(k\geq 3\), RCOLOR\(_k\) is equivalent to RWKL, as shown by \textit{L. Bienvenue}, \textit{L. Patey}, and \textit{P. Shafer} [``On the logical strengths of partial solutions to mathematical problems, Preprint, \url{arXiv:1411.5874}]. Clearly, RCOLOR\(_2\) is weaker than RCOLOR\(_3\), but it is not known if this relationship is strict. The results of the paper address a question of \textit{S. Flood} and \textit{H. Towsner} [``Separating principles below WKl\(_0\), Preprint, \url{arXiv:1410.4068}].

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 _2⁰ induction
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• scientific article; zbMATH DE number 2236643

Cites work

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

Cited in

(10)

• Dominating the Erdős-Moser theorem in reverse mathematics
• Coloring trees in reverse mathematics
• Comparing the strength of diagonally nonrecursive functions in the absence of _2⁰ induction
• The strength of the tree theorem for pairs in reverse mathematics
• Iterative forcing and hyperimmunity in reverse mathematics
• On the logical strengths of partial solutions to mathematical problems
• Degrees bounding principles and universal instances in reverse mathematics
• Open questions about Ramsey-type statements in reverse mathematics
• Forcing with bushy trees
• scientific article; zbMATH DE number 2236643 (Why is no real title available?)

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)