Effective choice functions and index sets (Q1820773)

This short and well-written paper gives a complete proof of the following result (generalizing - as the author mentions - some previous unpublished work of John Case): Let h be an effective choice function (i.e., h is partial recursive with dom(h)\(\subseteq {\mathcal P}(\omega)\) such that h(A)\(\in A\) whenever h(A) is defined) whose domain includes all infinite subsets of \(\omega\). Let \(Z=\{h(I(n))|\) \(n\in \omega \}\) with \(I(n)=\{m|\Phi_ m=\Phi_ n\}\). Then Z is strongly effectively immune, i.e., Z is infinite and there exists a recursive function f such that \(ran(\Phi_ x)\subseteq Z\to \max (ran(\Phi_ x))<f(x)\) for all \(x\in \omega.\) A further generalization of this result yields as a corollary the theorem on size measures of \textit{M. Blum} [Inf. Control 11, 257-265 (1967; Zbl 0165.021)].