On the logical strengths of partial solutions to mathematical problems
Laurent Bienvenu, Ludovic Patey, Paul Shafer · Transactions of the London Mathematical Society · 2017
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 ['Reverse mathematics and a Ramsey-type König's lemma', J. Symb.Log.77 (2012) 1272-1280], 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 König's lemma, such as restrictions of König'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 König'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 König's lemma is robust in the sense of Montalbán ['Open questions in reverse mathematics', Bull.Symb.Log. 17 (2011) 431-454]: it is equivalent to several perturbations.We also clarify the relationship between Ramsey-type weak König's lemma and algorithmic randomness by showing that Ramsey-type weak weak König's lemma is equivalent to the problem of finding diagonally non-recursive functions and that these problems are strictly easier than Ramsey-type weak König's lemma.This answers a question of Flood.