We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Ramsey-type graph coloring and diagonal non-computability.
- Authors
Patey, Ludovic
- 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 ( h- DNR) implies Ramsey-type weak König's lemma ( RWKL). In this paper, we prove that for every computable order h, there exists an $${\omega}$$ -model of h- DNR which is not a not model of the Ramsey-type graph coloring principle for two colors ( RCOLOR) 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.
- Subjects
GRAPH coloring; COMPUTABILITY logic; MATHEMATICAL functions; ALGORITHMIC randomness; COMPUTABLE functions; EXISTENCE theorems; MATHEMATICAL bounds
- Publication
Archive for Mathematical Logic, 2015, Vol 54, Issue 7/8, p899
- ISSN
0933-5846
- Publication type
Article
- DOI
10.1007/s00153-015-0448-5