zbMATH — the first resource for mathematics

\({\Pi}_1^0\)-encodability and omniscient reductions. (English) Zbl 07060305
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.
03D30 Other degrees and reducibilities in computability and recursion theory
03D65 Higher-type and set recursion theory
Full Text: DOI Euclid