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 Konigs lemma, such as restrictions of Konigs 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 Konigs 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 Konigs 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 Konigs lemma and algorithmic randomness by showing that Ramsey-type weak weak Konigs lemma is equivalent to the problem of finding diagonally non-recursive functions and that these problems are strictly easier than Ramsey-type weak Konigs lemma. This answers a question of Flood.
تحميل البحث