Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T00:24:00.005Z Has data issue: false hasContentIssue false
  • English
  • Français

A NOTE ON INITIAL SEGMENTS OF THE ENUMERATION DEGREES

Published online by Cambridge University Press:  25 June 2014

THEODORE A. SLAMAN  and
ANDREA SORBI
THEODORE A. SLAMAN
Affiliation:
DEPARTMENT OF MATHEMATICS THE UNIVERSITY OF CALIFORNIA, BERKELEY 719 EVANS HALL #3840 BERKELEY, CA 94720-3840 USAE-mail: [email protected]
ANDREA SORBI
Affiliation:
DIPARTIMENTO DI INGEGNERIA DELL’INFORMAZIONE E SCIENZE MATEMATICHE UNIVERSITÀ DEGLI STUDI DI SIENA VIA ROMA 56 I-53100 SIENA, ITALYE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that no nontrivial principal ideal of the enumeration degrees is linearly ordered: in fact, below every nonzero enumeration degree one can embed every countable partial order. The result can be relativized above any total degree: if a,b are enumeration degrees, with a total, and a < b, then in the degree interval (a,b), one can embed every countable partial order.

Keywords

03D30Enumeration reducibilityenumeration degree
Type
Articles
Information
The Journal of Symbolic Logic , Volume 79 , Issue 2 , June 2014 , pp. 633 - 643
Copyright
Copyright © The Association for Symbolic Logic 2014 

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

Calhoun, W. C. and Slaman, T. A., The${\rm{\Pi }}_2^0$e-degrees are not dense, this journal, 61 (1996), pp. 1364–1379.Google Scholar
Cooper, S. B., Partial degrees and the density problem, this JOURNAL, 47 (1982), pp. 854–859.Google Scholar
Cooper, S. B., Enumeration reducibility, nondeterministic computations and relative computability of partial functions, Recursion theory week, Oberwolfach 1989 (K. Ambos-Spies, G. Müller, and G. E. Sacks, editors), Lecture Notes in Mathematics, vol. 1432, Springer Verlag, Heidelberg, 1990, pp. 57–110.Google Scholar
Cooper, S. B., Computability theory, Chapman & Hall/CRC Mathematics, Boca Raton, London, New York, Washington, DC, 2003.Google Scholar
Gutteridge, L., Some results on enumeration reducibility, Ph.d. thesis, Simon Fraser University, 1971.Google Scholar
Kent, T. F., Lewis, A. E. M., and Sorbi, A., Empty intervals in the enumeration degrees. Annals of Pure and Applied Logic, 163 (2012), no. 5, pp. 567–574.Google Scholar
Lagemann, J., Embedding theorems in the reducibility ordering of the partial degrees, Ph.d. thesis, M. I. T., 1971.Google Scholar
Marsibilio, D. and Sorbi, A., Bounded enumeration reducibility and its degree structure. Archive for Mathematical Logic, 51 (2012), no. 1–2, pp. 163–186.Google Scholar
McEvoy, K. and Cooper, S. B., On minimal pairs of enumeration degrees, this JOURNAL, 50 (1985), pp. 983–1001.Google Scholar
Odifreddi, P., Classical recursion theory (Volume II), Studies in Logic and the Foundations of Mathematics, vol. 143,North-Holland, Amsterdam, 1999.Google Scholar
Omanadze, R. S. and Sorbi, A., Strong enumeration reducibilities. Archive for Mathematical Logic, 45 (2006), no. 7, 869–912.Google Scholar
Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
Sacks, G. E., Degrees of unsolvability, second ed., Annals of Mathematical Studies, Princeton University Press, Princeton, NJ, 1966.Google Scholar
Shoenfield, J. R., On degrees of unsolvability. Annals of Mathematics, 69 (1959), pp. 644–653.Google Scholar
Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Omega Series, Springer Verlag, Heidelberg, 1987.Google Scholar
Soskova, M. I. and Soskov, I. N., Embedding countable partial orderings in the enumeration degrees and the ω-enumeration degrees. Journal of Logic and Computation, 4 (2012), pp. 927–952.Google Scholar