\({\Pi}_1^0\)-encodability and omniscient reductions. (English) Zbl 07060305

Monin, Benoit; Patey, Ludovic

Notre Dame J. Formal Logic 60, No. 1, 1-12 (2019).

Summary: A set of integers \(A\) is computably encodable if every infinite set of integers has an infinite subset computing \(A\). By a result of Solovay, the computably encodable sets are exactly the hyperarithmetic ones. In this article, we extend this notion of computable encodability to subsets of the Baire space, and we characterize the \({\Pi}_1^0\)-encodable compact sets as those which admit a nonempty \({\Sigma}^1_1\)-subset. Thanks to this equivalence, we prove that weak König’s lemma is not strongly computably reducible to Ramsey’s theorem. This answers a question of Hirschfeldt and Jockusch.

MSC:

03D30	Other degrees and reducibilities in computability and recursion theory
03D65	Higher-type and set recursion theory

Keywords:

reverse mathematics; computable encodability; Ramsey’s theory; computable reduction; higher recursion theory