Ramsey-type graph coloring and diagonal non-computability

Archive for Mathematical Logic 54 (7-8):899-914 (2015)


A function is diagonally non-computable 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 implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is not a not model of the Ramsey-type graph coloring principle for two colors 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 ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -models.

Download options


    Upload a copy of this work     Papers currently archived: 72,766

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

16 (#671,867)

6 months
1 (#386,499)

Historical graph of downloads
How can I increase my downloads?

References found in this work

RT₂² Does Not Imply WKL₀.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.
RT2 2 Does Not Imply WKL0.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.
Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.

View all 9 references / Add more references

Citations of this work

The Strength of the Tree Theorem for Pairs in Reverse Mathematics.Ludovic Patey - 2016 - Journal of Symbolic Logic 81 (4):1481-1499.

Add more citations

Similar books and articles

Reverse Mathematics and the Coloring Number of Graphs.Matthew Jura - 2016 - Notre Dame Journal of Formal Logic 57 (1):27-44.
Effective Coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Graph Coloring and Reverse Mathematics.James H. Schmerl - 2000 - Mathematical Logic Quarterly 46 (4):543-548.
Some Ramsey-Type Theorems for Countably Determined Sets.Josef Mlček & Pavol Zlatoš - 2002 - Archive for Mathematical Logic 41 (7):619-630.
On the Possibility, or Otherwise, of Hypercomputation.Philip D. Welch - 2004 - British Journal for the Philosophy of Science 55 (4):739-746.
Reverse Mathematics and Grundy Colorings of Graphs.James H. Schmerl - 2010 - Mathematical Logic Quarterly 56 (5):541-548.
Ramsey's Theorem and Cone Avoidance.Damir Dzhafarov & Carl Jockusch Jr - 2009 - Journal of Symbolic Logic 74 (2):557 - 578.
Domatic Partitions of Computable Graphs.Matthew Jura, Oscar Levin & Tyler Markkanen - 2014 - Archive for Mathematical Logic 53 (1-2):137-155.