A Ramsey-Type K\"onig's lemma and its variants
Laurent Bienvenu, Ludovic Patey, Paul Shafer · arXiv (Cornell University) · 2014
We use the framework of reverse mathematics to address the question of, given a mathematical problem, whether or not it is easier to find an infinite partial solution than it is to find a complete solution. Following Flood, we say that a Ramsey-type variant of a problem is the problem with the same instances but whose solutions are the infinite partial solutions to the original problem. We study Ramsey-type variants of problems related to Konig's lemma, such as restrictions of Konig's lemma, Boolean satisfiability problems, and graph coloring problems. We find that sometimes the Ramsey-type variant of a problem is strictly easier than the original problem (as Flood showed with weak Konig's lemma) and that sometimes the Ramsey-type variant of a problem is equivalent to the original problem. We show that the Ramsey-type variant of weak Konig's lemma is robust in the sense of Montalban: it is equivalent to several perturbations of itself. We also clarify the relationship between Ramsey-type weak Konig's lemma and algorithmic randomness by showing that Ramsey-type weak weak Konig's lemma is equivalent to the problem of finding diagonally non-recursive functions and that these problems are strictly easier than Ramsey-type weak Konig's lemma. This answers a question of Flood.