Determining automorphisms of the recursively enumerable sets

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 }$.