On the logical strengths of partial solutions to mathematical problems. (13th April 2017)

• Record Type: Journal Article
• Authors: Bienvenu, Laurent; Patey, Ludovic; Shafer, Paul
• Is Part Of: Transactions of the London Mathematical Society. Volume 4:Number 1(2017)
• Page Start: 30
• Page End: 71
• Publication Date: 2017-04-13
• Subjects: 03B30 -- 03F35 -- 05C15 -- 05D10 -- 03D32 (primary); Mathematics -- Periodicals; 510.5
• DOI: 10.1112/tlm3.12001
• Languages: English
• ISSNs: 2052-4986

Abstract

Abstract: 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.