Premium
Separating principles below WKL 0
Author(s) -
Flood Stephen,
Towsner Henry
Publication year - 2016
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201500001
Subject(s) - iterated function , mathematics , lemma (botany) , ideal (ethics) , construct (python library) , turing , forcing (mathematics) , algebra over a field , translation (biology) , turing machine , discrete mathematics , pure mathematics , calculus (dental) , algorithm , computer science , computation , epistemology , mathematical analysis , ecology , philosophy , biochemistry , chemistry , poaceae , messenger rna , gene , biology , programming language , medicine , dentistry
In this paper, we study the Ramsey‐type weak Kőnig's Lemma, written RWKL , using a technique introduced by Lerman, Solomon, and the second author. This technique uses iterated forcing to construct an ω‐model satisfying one principle T 1 but not another T 2 . The technique often allows one to translate a “one step” construction (building an instance of T 2 along with a collection of solutions to each computable instance of T 1 ) into an ω‐model separation (building a computable instance of T 2 together with a Turing ideal where T 1 holds but this instance has no solution). We illustrate this translation by separating d - DNR from DNR (reproving a result of Ambos‐Spies, Kjos‐Hanssen, Lempp, and Slaman), and then apply this technique to separate RWKL from DNR (which has been shown separately by Bienvenu, Patey, and Shafer).