Computable numberings of families of infinite sets (Q2300737)

A Friedberg numbering of a set is an effective enumeration of the set's members without repetition. In [Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys. 6, 1--5 (1958; Zbl 0084.24902)] \textit{R. M. Friedberg} gave such an enumeration of the c.e. sets. This paper shows by diagonal argument that there is no such enumeration for the infinite c.e. sets. Extending these arguments to the analytical hierarchy, there is neither a \(\pi^1_1\)-computable numbering for all infinite \(\pi^1_1\) sets, nor a \(\varepsilon^1_2\)-computable numbering for all infinite \(\varepsilon^1_2\) sets. Moreover, that for \(k>2\) there is no \(\varepsilon^1_k\)-computable numbering of the infinite \(\varepsilon^1_k\) sets is a consequence of Gödel's axiom of constructibility, whence existence of such an ordering is unprovable in ZF. Whether or not its nonexistence is provable in ZF is an open question.