Array nonrecursiveness and relative recursive enumerability. (English) Zbl 1269.03044

Author’s abstract: In this paper we prove that a degree \({\mathbf a}\) is array nonrecursive if and only if every degree \({\mathbf b\geq\mathbf a}\) is r.e. in and strictly above another degree. This result answers some questions in [K. Ambos-Spies et al., J. Symb. Log. 74, No. 3, 989–1000 (2009; Zbl 1201.03025)]. We also deduce an interesting corollary that every \(n\)-REA degree has a strong minimal cover if and only if it is array recursive.


03D25 Recursively (computably) enumerable sets and degrees
03D28 Other Turing degree structures


Zbl 1201.03025
Full Text: DOI Euclid


[1] K. Ambos-Spies, D. Ding, W. Wang, and L. Yu Bounding non-\(GL_2\) and R.E.A., Journal of Symbolic Logic, vol. 74(2009), no. 3, pp. 989-1000. · Zbl 1201.03025 · doi:10.2178/jsl/1245158095
[2] M. Cai and R.A. Shore Domination, forcing, array nonrecursiveness and relative recursive enumerablity , Journal of Symbolic Logic, vol. 77(2012), no. 1, pp. 33-48. · Zbl 1269.03045 · doi:10.2178/jsl/1327068690
[3] C.J. Conidis Classifying model-theoretic properties , Journal of Symbolic Logic, vol. 73(2008), no. 3, pp. 885-905. · Zbl 1160.03012 · doi:10.2178/jsl/1230396753
[4] B.F. Csima, D.R. Hirschfeldt, J. Knight, and R.I. Soare Bounding prime models , Journal of Symbolic Logic, vol. 69(2004), no. 4, pp. 1117-1142. · Zbl 1071.03021 · doi:10.2178/jsl/1102022214
[5] R. Downey, C. Jockusch, and M. Stob Array nonrecursive sets and multiple permitting arguments , Recursion Theory Week (Proceedings, Oberwolfach, 1989) , Lecture Notes in Mathematics, vol. 1432, Springer-Verlag,1990, pp. 141-173. · Zbl 0713.03020 · doi:10.1007/BFb0086116
[6] —- Array nonrecursive degrees and genericity , London Mathematical Society Lecture Notes Series , vol. 224, University Press,1996, pp. 93-105. · Zbl 0849.03029 · doi:10.1017/CBO9780511629167.005
[7] S. Ishmukhametov Weak recursive degrees and a problem of Spector , Recursion Theory and Complexity (Arslanov and Lempp, editors), de Gruyter,1999, pp. 81-89. · Zbl 0951.03036
[8] C. Jockusch and D. Posner Double jumps of minimal degrees , Journal of Symbolic Logic, vol. 43(1978), no. 4, pp. 715-724. · Zbl 0411.03034 · doi:10.2307/2273510
[9] C. Jockusch and R.I. Soare \(\Pi^0_1\) classes and degrees of theories, Transactions of the American Mathematical Society , vol. 173(1972), pp. 33-56. · Zbl 0262.02041 · doi:10.2307/1996261
[10] A. Kučera Measure, \(\Pi^0_1\) -classes and complete extensions of PA, Recursion Theory Week (Oberwolfach, 1984) (Berlin), Lecture Notes in Math., vol. 1141, Springer, pp. 245-259. · Zbl 0622.03031 · doi:10.1007/BFb0076224
[11] A.E.M. Lewis \(\Pi^0_1\) classes, strong minimal covers and hyperimmune-free degrees, Bulletin of the London Mathematical Society , vol. 39(2007), no. 6, pp. 892-910. · Zbl 1148.03032 · doi:10.1112/blms/bdm083
[12] R.A. Shore The structure of the degrees of unsolvability , Recursion Theory, Proceedings of the Symposia in Pure Mathematics 42 (A. Nerode and R.A. Shore, editors), American Mathematical Society, Providence, R.I.,1985, pp. 33-51. · Zbl 0573.03016 · doi:10.1090/pspum/042/791051
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.