Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T10:03:48.121Z Has data issue: false hasContentIssue false
  • English
  • Français

The -spectrum of a linear order

Published online by Cambridge University Press:  12 March 2014

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

Abstract

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable degree, but not 0. Since our argument requires the technique of permitting below a set, we include a detailed explantion of the mechanics and intuition behind this type of permitting.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 66 , Issue 2 , June 2001 , pp. 470 - 486
Copyright
Copyright © Association for Symbolic Logic 2001

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

[1]Ash, C. J., Jockusch, C. G., and Knight, J. F., Jumps of orderings, Transactions of the American Mathematical Society, vol. 319 (1990), pp. 573–599.CrossRefGoogle Scholar
[2]Dekker, J. C. E., A theorem on hypersimple sets, Proceedings of the American Mathematical Society, vol. 5 (1954), pp. 791–796.CrossRefGoogle Scholar
[3]Downey, R., On presentations of algebraic structures, Complexity, logic, and recursion theory (Sorbi, A., editor), Dekker, New York, 1997, pp. 157–205.Google Scholar
[4]Downey, R., Recursion theory and linear orderings, Handbook of computable algebra, (to appear).Google Scholar
[5]Downey, R. and Jockusch, C. G., Every low boolean algebra is isomorphic to a recursive one, Proceedings of the American Mathematical Society, vol. 122 (1994), pp. 871–880.CrossRefGoogle Scholar
[6]Downey, R. and Knight, J. F., Orderings with α-th jump degree 0(α), Proceedings of the American Mathematical Society, vol. 114 (1992), pp. 545–552.Google Scholar
[7]Feiner, L. J., Orderings and boolean algebras not isomorphic to recursive ones, Ph.D. thesis, Massachusetts Institute of Technology, 1967.Google Scholar
[8]Jockusch, C. G. and Soare, R. I., Degrees of orderings not isomorphic to recursive linear orderings, Annals of Pure and Applied Logic, vol. 52 (1991), pp. 39–64.CrossRefGoogle Scholar
[9]Knight, J. F., Degrees coded into jumps of orderings, this Journal, vol. 51 (1986), pp. 1034–1042.Google Scholar
[10]Knight, J. F. and Stob, M., Computable boolean algebras, this Journal, (to appear).Google Scholar
[11]Posner, D., A survey of non-r. e. degrees ≤ 0′, Recursion theory: Its generalizations and applications (Drake, F. R. and Wainer, S. S., editors), Cambridge University Press, Cambridge, 1980, pp. 52–109.CrossRefGoogle Scholar
[12]Richter, L. J., Degrees of structures, this Journal, vol. 46 (1981), pp. 723–731.Google Scholar
[13]Rosenstein, J., Linear orderings, Academic Press, New York, 1982.Google Scholar
[14]Slaman, T., Relative to any nonrecursive set, Proceedings of the American Mathematical Society, vol. 126 (1998), pp. 2117–2122.CrossRefGoogle Scholar
[15]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, New York, 1987.CrossRefGoogle Scholar
[16]Thurber, J., Degrees of boolean algebras, Ph.D. thesis, University of Notre Dame, 1994.Google Scholar
[17]Wehner, S., Enumerations, countable structures, and turing degrees, Proceedings of the American Mathematical Society, vol. 126 (1998), pp. 2131–2139.CrossRefGoogle Scholar