Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Determining automorphisms of the recursively enumerable sets


Author: Richard A. Shore
Journal: Proc. Amer. Math. Soc. 65 (1977), 318-325
MSC: Primary 02F25
DOI: https://doi.org/10.1090/S0002-9939-1977-0446931-5
MathSciNet review: 0446931
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We answer two questions of A. Nerode and give information about how the structure of $ {\mathcal{E}^\ast}$, the lattice of r.e. sets modulo finite sets, is determined by various subclasses.

Theorem. If $ {\mathcal{C}^\ast}$ is any nontrivial recursively invariant subclass of $ {\mathcal{E}^\ast}$, then any automorphism of $ {\mathcal{E}^\ast}$ is determined uniquely by its action on $ {\mathcal{C}^\ast}$.

Theorem. If $ {\mathcal{C}^\ast}$ is the class of recursive sets modulo finite sets or $ {\mathcal{M}^\ast} \subseteq {\mathcal{C}^\ast} \subseteq {\mathcal{S}^\ast}$ ( $ {\mathcal{M}^\ast}$ = maximal sets, $ {\mathcal{S}^\ast}$ = simple sets) then there is an automorphism of (the lattice generated by) $ {\mathcal{C}^\ast}$ which does not extend to one of $ {\mathcal{E}^\ast}$.


References [Enhancements On Off] (What's this?)

  • [A] H. Lachlan [1968], On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130, 1-37. MR 0227009 (37:2594)
  • 1. -[1968a], Degrees of recursively enumerable sets which have no maximal superset, J. Symbolic Logic 33, 431-443. MR 0236016 (38:4314)
  • [D] A. Martin [1966], Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12, 295-310. MR 0224469 (37:68)
  • [J] Myhill [1956], The lattice of recursively enumerable sets, J. Symbolic Logic 21, 220.
  • [R] W. Robinson [1968], A dichotomy of the recursively enumerable sets, Z. Math. Logik Grundlagen Math. 14, 339-356. MR 0237334 (38:5623)
  • [H] Rogers, Jr. [1967], Theory of recursive functions and effective computability, McGraw-Hill, New York. MR 0224462 (37:61)
  • [G] E. Sacks [1966], Degrees of unsolvability, 2nd. ed., Princeton Univ. Press, Princeton, N.J. MR 0186554 (32:4013)
  • [J] R. Shoenfield [1976], Degrees of classes of r.e. sets, J. Symbolic Logic 41, 695-696. MR 0485293 (58:5140)
  • [R] A. Shore [1977], Nowhere simple sets, J. Symbolic Logic (to appear).
  • [R] I. Soare [1974], Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets, Ann. of Math. (2) 100, 80-120. MR 0360235 (50:12685)
  • 2. -[1974a], Automorphisms of the lattice of recursively enumerable sets, Bull. Amer. Math. Soc. 80, 53-58. MR 0373858 (51:10058)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 02F25

Retrieve articles in all journals with MSC: 02F25


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1977-0446931-5
Keywords: Recursively enumerable sets, recursive sets, automorphisms of r.e. sets
Article copyright: © Copyright 1977 American Mathematical Society

American Mathematical Society