Effective choice functions and index sets

摘要

θe is the eth partial recursive function; I(e) = {n|θn = θe}. An effective choice function is a partial recursive functional h wth dom(h) ⊆ ℘(ω) such that h(A) ϵ A whenever h(A) is defined. Theorem: If h(A) is defined for all infinite A ⊆ω, then {h(I(e)) | e ϵ ω} is strongly effectively immune. This result may be generalized to functionals H such that, for all A ϵ dom(H), H(A) is a finite subset of A.