Effectively infinite classes of numberings and computable families of reals

We prove various sufficient conditions for the effective infinity of classes of computable numberings. Then we apply them to show that for every computable family of left-c.e. reals without the greatest element the class of its Friedberg computable numberings is effectively infinite. In particular, this result covers the families of all left-c.e. and all Martin-Löf random left-c.e. reals whose Friedberg computable numberings have been constructed by Broadhead and Kjos-Hanssen in their paper (In Mathematical Theory and Computational Practice, CiE 2009 (2009) 49–58 Springer). In addition, for every infinite computable family of left-c.e. reals we prove that the classes of all its computable, positive and minimal numberings are effectively infinite.

Перевод пока недоступен