×

zbMATH — the first resource for mathematics

Effectively infinite classes of enumerations. (English) Zbl 0849.03034
Summary: This research partially answers the question about the size of the class of positive elements of a Rogers semilattice. To this end, we introduce the notions of effective infinity for classes of computable enumerations. We consider the classes of (1) all enumerations without repetitions, (2) all positive undecidable enumerations, (3) all negative undecidable enumerations, and (4) all computable enumerations of a family of recursively enumerable sets. We use the finite injury priority method to prove five theorems which give sufficient conditions for these classes to be effectively infinite. These theorems permit to strengthen the results of Pour-El, Pour-El and Howard, Ershov and Khutoretskij about the existence of enumerations without repetitions and positive undecidable enumerations.
MSC:
03D45 Theory of numerations, effectively presented structures
03D20 Recursive functions and relations, subrecursive hierarchies
03D25 Recursively (computably) enumerable sets and degrees
PDF BibTeX XML Cite