Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-23T05:49:37.141Z Has data issue: false hasContentIssue false
  • English
  • Français

Elementary differences between the (2p)-C. E. and the (2p +1)-c. e. enumeration degrees

Published online by Cambridge University Press:  12 March 2014

I. S. Kalimullin
I. S. Kalimullin*
Affiliation:
N.G. Chebotarev Research Institute of Mechanics and, Mathematics Kazan State University, Universitetskaya St. 17, Kazan. 420008, Russia. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

It is proved that the (2p)-c. e. e-degrees are not elementarily equivalent to the (2p + 1)-c. e. e-degrees for each nonzero p ∈ ω. It follows that m-c. e. e-degrees are not elementarily equivalent to the n-c e. e-degrees if 1 <m < n.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 1 , March 2007 , pp. 277 - 284
Copyright
Copyright © Association for Symbolic Logic 2007

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]Cooper, S. B., Enumeration reducibility, nondeterministic computations and relative computability of partial functions, Recursion Theory Week, Oberwolfach 1989 (Ambos-Spies, K., Müller, G., and Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1432, Springer, 1990, pp. 57–110.Google Scholar
[2]Kalimullin, I. S., Elementary theories of semilattices of n-recursive enumerable degrees with respect to enumerability, Russian Mathematics, vol. 45 (2001), no. 4, pp. 22–25.Google Scholar
[3]Kalimullin, I. S., Splitting properties of n-c. e. enumeration degrees, this Journal, vol. 67 (2002), pp. 537–546.Google Scholar
[4]Kalimullin, I. S., Definability of the jump operator in the enumeration degrees, Journal of Mathematical Logic, vol. 3 (2003), no. 2, pp. 257–267.CrossRefGoogle Scholar
[5]Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical Society, vol. 16 (1966), pp. 537–569.Google Scholar
[6]Rogers, H. Jr, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.Google Scholar
[7]Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Omega Series, Springer, 1987.Google Scholar