Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-13T22:36:08.520Z Has data issue: false hasContentIssue false
  • English
  • Français

Array nonrecursiveness and relative recursive enumerability

Published online by Cambridge University Press:  12 March 2014

Mingzhong Cai
Mingzhong Cai*
Affiliation:
Department of Mathematics, Cornell University, Ithaca NY 14853, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we prove that a degree a is array nonrecursive (ANR) if and only if every degree b ≥ a is r.e. in and strictly above another degree (RRE). This result will answer some questions in [ASDWY]. We also deduce an interesting corollary that every n-REA degree has a strong minimal cover if and only if it is array recursive.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 77 , Issue 1 , March 2012 , pp. 21 - 32
Copyright
Copyright © Association for Symbolic Logic 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[ASDWY]Ambos-Spies, K., Ding, D., Wang, W., and Yu, L., Bounding non-GL2 and R.E.A., this Journal, vol. 74 (2009), no. 3, pp. 989–1000.Google Scholar
[CS]Cai, M. and Shore, R.A., Domination, forcing, array nonrecursiveness and relative recursive enumerablity, this Journal, vol. 77 (2012), no. 1, pp. 33–48.Google Scholar
[C]Conidis, C.J., Classifying model-theoretic properties, this Journal, vol. 73 (2008), no. 3, pp. 885–905.Google Scholar
[CHKS]Csima, B.F., Hirschfeldt, D.R., Knight, J., and Soare, R.I., Bounding prime models, this Journal, vol. 69 (2004), no. 4, pp. 1117–1142.Google Scholar
[DJS1]Downey, R., Jockusch, C., and Stob, M., 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.CrossRefGoogle Scholar
[DJS2]Downey, R., Array nonrecursive degrees and genericity, London Mathematical Society Lecture Notes Series, vol. 224, University Press, 1996, pp. 93–105.Google Scholar
[I]Ishmukhametov, S., Weak recursive degrees and a problem of Spector, Recursion Theory and Complexity(Arslanov, and Lempp, , editors), de Gruyter, 1999, pp. 81–89.CrossRefGoogle Scholar
[JP]Jockusch, C. and Posner, D., Double jumps of minimal degrees, this Journal, vol. 43 (1978), no. 4, pp. 715–724.Google Scholar
[JS]Jockusch, C. and Soare, R.I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[K]Kučera, A., Measure, -classes and complete extensions of PA, Recursion Theory Week (Oberwolfach, 1984) (Berlin), Lecture Notes in Math., vol. 1141, Springer, pp. 245–259.CrossRefGoogle Scholar
[L]Lewis, A.E.M., classes, strong minimal covers and hyperimmune-free degrees, Bulletin of the London Mathematical Society, vol. 39 (2007), no. 6, pp. 892–910.CrossRefGoogle Scholar
[S]Shore, R.A., The structure of the degrees of unsolvability, Recursion Theory, Proceedings of the Symposia in Pure Mathematics 42 (Nerode, A. and Shore, R.A., editors), American Mathematical Society, Providence, R.I., 1985, pp. 33–51.Google Scholar