Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-16T15:02:08.672Z Has data issue: false hasContentIssue false
  • English
  • Français

On orbits, of prompt and low computably enumerable sets

Published online by Cambridge University Press:  12 March 2014

Kevin Wald
Kevin Wald*
Affiliation:
Department of Mathematics, University of Connecticut, Storrs, Connecticut 06269-3009, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper concerns automorphisms of the computably enumerable sets. We prove two results relating semilow sets and prompt degrees via automorphisms, one of which is complementary to a recent result of Downey and Harrington. We also show that the property of effective simplicity is not invariant under automorphism, and that in fact every promptly simple set is automorphic to an effectively simple set. A major technique used in these proofs is a modification of the Harrington-Soare version of the method of Harrington-Soare and Cholak for constructing Δ30 automorphisms; this modification takes advantage of a recent result of Soare on the extension of “restricted” automorphisms to full automorphisms.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 67 , Issue 2 , June 2002 , pp. 649 - 678
Copyright
Copyright © Association for Symbolic Logic 2002

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]Cholak, P. A., Automorphisms of the lattice of recursively enumerable sets, Memoirs of the American Mathematical Society, vol. 113 (1995).CrossRefGoogle Scholar
[2]Cholak, P. A., The dense simple sets are orbit complete. Proceedings of the Oberwolfach conference on compulability theory in 1996, Journal of Pure and Applied Logic, vol. 94 (1998). pp. 37–44.CrossRefGoogle Scholar
[3]Downey, R. and Stob, M., Automorphisms of the lattice of recursively enumerable sets: Orbits, Advances in Mathematics, vol. 92 (1992), pp. 237–265.CrossRefGoogle Scholar
[4]Harrington, L. and Soare, R. I., Post's program and incomplete recursively enumerable sets, Proceedings of the National Academy of Sciences, USA, vol. 88 (1991), pp. 10242–10246.CrossRefGoogle ScholarPubMed
[5]Harrington, L. and Soare, R. I., The Δ30 automorphism method and noninvariant classes of degrees, Journal of the American Mathematical Society, vol. 9 (1996), pp. 617–666.CrossRefGoogle Scholar
[6]Maass, W., Recursively enumerable generic sets, this Journal, vol. 47 (1982), pp. 809–823.Google Scholar
[7]Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[8]Robinson, R. W., The inclusion lattice and degrees of unsolvability of the recursively enumerable sets, Ph. d. dissertation, Cornell University, 1966.Google Scholar
[9]Soare, R. I., Templates, extensions, and automorphisms, to appear.Google Scholar
[10]Soare, R. I., Automorphisms of the recursively enumerable sets, Part I: Maximal sets, Annals of Mathematics, vol. 100 (1974), pp. 80–120.CrossRefGoogle Scholar
[11]Soare, R. I., Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets, Annals of Mathematical Logic, vol. 22 (1982), pp. 69–107.CrossRefGoogle Scholar
[12]Soare, R. I., Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Springer-Verlag, Heidelberg, 1987.CrossRefGoogle Scholar
[13]Wald, K. M., Automorphisms and noninvariant properties of the computably enumerable sets, Ph. d. dissertation, University of Chicago, 1999.Google Scholar