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
MathSciNet review: 0446931
Full-text PDF

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

Keywords: Recursively enumerable sets, recursive sets, automorphisms of r.e. sets
Article copyright: © Copyright 1977 American Mathematical Society

American Mathematical Society