Computable Numberings of Families of Infinite Sets

Аннотация

We state the following results: the family of all infinite computably enumerable sets has no computable numbering; the family of all infinite \( {\varPi}_1^1 \) sets has no \( {\varPi}_1^1 \) -computable numbering; the family of all infinite \( {\varSigma}_2^1 \) sets has no \( {\varSigma}_2^1 \) -computable numbering. For k > 2, the existence of a \( {\varSigma}_k^1 \) -computable numbering for the family of all infinite \( {\varSigma}_k^1 \) sets leads to the inconsistency of ZF.