Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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
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?)


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: http://dx.doi.org/10.1090/S0002-9939-1977-0446931-5
PII: S 0002-9939(1977)0446931-5
Keywords: Recursively enumerable sets, recursive sets, automorphisms of r.e. sets
Article copyright: © Copyright 1977 American Mathematical Society