Hostname: page-component-8448b6f56d-c4f8m Total loading time: 0 Render date: 2024-04-17T09:17:24.595Z Has data issue: false hasContentIssue false
  • English
  • Français

η-representation of sets and degrees

Published online by Cambridge University Press:  12 March 2014

Kenneth Harris
Kenneth Harris*
Affiliation:
Department of Computer Science, University of Chicago1100 E. 5TH Street, Chicago, IL 60637, USA, E-mail: kaharris@cs.uchicago.edu
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that a set has an η-representation in a linear order if and only if it is the range of a 0′-computable limitwise monotonic function. We also construct a Δ3 Turing degree for which no set in that degree has a strong η-representation, answering a question posed by Downey.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 4 , December 2008 , pp. 1097 - 1121
Copyright
Copyright © Association for Symbolic Logic 2008

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

[CDK98]Coles, R. J., Downey, R., and Khoussainov, B. M., On initial segments of computable linear orders, Order, vol. 14 (1998), pp. 107–24.CrossRefGoogle Scholar
[CHKS04]Csima, B., Hirschfeldt, D., Knight, J. F., and Soare, R. I., Bounding prime models, this Journal, vol. 69 (2004), no. 4, pp. 1117–1142.Google Scholar
[Dow98]Downey, Rod, Computability theory and linear orders, Handbook of recursive mathematics (Ershov, Y. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Studies in Logic and the Foundations of Mathematics, vol. 138, Elsevier, 1998.Google Scholar
[HMP07]Hirschfeldt, D., Miller, R., and Podzorov, S., Order-computable sets, The Notre Dame Journal of Formal Logic, vol. 48 (2007), no. 3, pp. 317–347.CrossRefGoogle Scholar
[Khi98]Khisamiev, N. G., Constructive abelian groups, Handbook of recursive mathematics (Ershov, Yu. L., Goncharov, S. S., Nerode, A., and Remmel, J. B., editors), Studies in Logic and the Foundations of Mathematics, vol. 138-139, Elsevier Science, 1998, pp. 1177–1231.Google Scholar
[KNS97]Khoussainov, B. M., Nies, A., and Shore, R. A., Computable models of theories with few models, Notre Dame Journal of Formal Logic, vol. 38 (1997),pp. 165–178.CrossRefGoogle Scholar
[Ler81]Lerman, Manuel, On recursive linear orders, Logic year 1979-80 (Lerman, M., Schmerl, J. H., and Soare, R. I., editors), Lecture Notes in Mathematics, vol. 859, 1981, pp. 132–142.CrossRefGoogle Scholar
[Soa87]Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematics, Springer-Verlag, 1987.CrossRefGoogle Scholar