Regular enumerations. (English) Zbl 1053.03024

The paper studies what the authors call, following I. N. Soskov [Arch. Math. Logic 39, 417–437 (2000; Zbl 0960.03037)], regular enumerations which are a kind of generic enumeration of families of sets. This paper deals with the transfinite case, which turns out to be a nontrivial extension of the finite case treated by Soskov (loc. cit.).
The results of this paper provide a unified treatment of several results. There are results on jump inversion, where the jump comes from enumeration reducibility. There are results characterizing the sets \(A\) such that
\[ (\forall X)[(\forall\gamma\leq \zeta)\,(B_\gamma\text{ is c.e. in }X^{(\gamma)}\text{ uniformly in }\gamma)\Rightarrow A\text{ is c.e. in }X^{(\alpha)}], \]
where \(\alpha\) is an arbitrary computable ordinal. There is a general result saying when the set
\[ {\mathcal S}_{\alpha,\beta}= \{X^{(\alpha)}:(\forall\gamma\leq \beta)\,(B_\gamma\text{ is c.e. in }X^\gamma\text{ uniformly in }\gamma)\} \]
has an element of least degree. This yields as corollaries some well-known results of C. J. Ash, C. G. Jockusch jun. and J. F. Knight [Trans. Am. Math. Soc. 319, 573–599 (1990; Zbl 0705.03022)] and of R. Downey and J. F. Knight [Proc. Am. Math. Soc. 114, 545–552 (1992; Zbl 0748.03027)], as well as some recent results of R. J. Coles, R. G. Downey and T. A. Slaman [J. Lond. Math. Soc., II. Ser. 62, 641–649 (2000; Zbl 1023.03036)] on existence and nonexistence of least jumps to which a given set is enumeration reducible, which have applications in computable algebra. The methods of the paper are interesting and demonstrate that enumeration reducibility plays a central role in a number of results in computable algebra. (To the reviewer’s knowledge the first such observation along these lines were in L. Richter’s thesis [Degrees of unsolvability of models, Ph.D. Thesis, University of Illinois at Urbana-Champaign (1977)]).


03D25 Recursively (computably) enumerable sets and degrees
03D45 Theory of numerations, effectively presented structures
Full Text: DOI


[1] Bulletin of the London Mathematical Society
[2] DOI: 10.1002/malq.19740201311 · Zbl 0304.02016 · doi:10.1002/malq.19740201311
[3] DOI: 10.1090/S0002-9947-1990-0955487-0 · doi:10.1090/S0002-9947-1990-0955487-0
[4] DOI: 10.1016/0168-0072(92)90026-V · Zbl 0769.03025 · doi:10.1016/0168-0072(92)90026-V
[5] DOI: 10.1007/s001530050156 · Zbl 0960.03037 · doi:10.1007/s001530050156
[6] DOI: 10.1002/malq.19710170139 · Zbl 0229.02037 · doi:10.1002/malq.19710170139
[7] Partial degrees and the density problem. Part 2: The enumeration degrees of the {\(\Sigma\)}2 sets are dense 49 pp 503– (1984) · Zbl 0574.03027
[8] Jumps of quasi-minimal enumeration degrees 50 pp 839– (1985)
[9] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[10] Proceedings of the American Mathematical Society 114 pp 545– (1992)
[11] 1-Genericity in the enumeration degrees 53 pp 878– (1988) · Zbl 0663.03030
[12] Recursion Theory Week, Oberwolfach 1989 1432 pp 57– (1990)
[13] Higher Recursion Theory (1990) · Zbl 0716.03043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.