Ramsey-type graph coloring and diagonal non-computability

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


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.



    Upload a copy of this work     Papers currently archived: 92,261

External links

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

Through your library

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 D. Dzhafarov & Carl G. Jockusch - 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.


Added to PP

29 (#553,855)

6 months
8 (#370,225)

Historical graph of downloads
How can I increase my downloads?

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

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 10 references / Add more references