The minimum degree of recursively representable choice functions (Q1072546)

By a recursive space of alternatives we mean a pair \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\), where \({\mathcal R}({\mathcal X})\) is the image of a compact, convex subset \({\mathcal X}\subseteq {\mathbb{R}}^ n_+\) in a recursive metric space \({\mathcal M}({\mathbb{R}}^ n)\) comprised of n-tuples of \({\mathcal R}\)-indices of recursive real numbers and where \({\mathbb{F}}_{{\mathcal R}}\) is the class of all recursive subsets of \({\mathcal R}({\mathcal X})\). A choice function on \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\) is a set- valued map defined on the class \({\mathbb{F}}_{{\mathcal R}}\), \(\phi:{\mathbb{F}}_{{\mathcal R}}\to {\mathcal P}({\mathcal R}({\mathcal X}))\) such that for any \(A\in {\mathbb{F}}_{{\mathcal R}}\), \(\phi(A)\subseteq A\). A choice function \(\phi\) on \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\) is recursively rational if there exists a binary relation \(\gtrsim:{\mathcal R}({\mathcal X})^ 2\to \{0,1\}\) such that for any \(\alpha,\beta \in {\mathcal R}({\mathcal X})\) if \(\alpha \gtrsim \beta\) then \(f(\alpha)\geq f(\beta)\) for f:\({\mathbb{N}}\to {\mathbb{N}}^ a\) potentially partial recursive function. Every recursively rational choice function \(\phi\) on \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\) is recursively representable in the sense that if \(\{{\mathbb{F}}_ j\}_{j\in {\mathbb{N}}}\subseteq {\mathbb{F}}_{{\mathcal R}}\) is an R. E. subfamily, then \(\{\phi ({\mathbb{F}}_ j)\}_{j\in {\mathbb{N}}}\subseteq {\mathbb{F}}_{{\mathcal R}}\) is an R. E. sub-family. In this paper we prove that the minimum degree of Turing complexity of a recursively representable choice function \(\phi\) on \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\) is \(\underset \tilde{} O''\), the degree of a complete \(\Sigma_ 2\) set in the Kleene-Mostowski hierarchy. A consequence of this result is that the complexity of such choice functions in this sense is bounded strictly above the degrees of the R. E. sets.