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

Abstract | References | Similar Articles | Additional Information

Abstract: We answer two questions of A. Nerode and give information about how the structure of , the lattice of r.e. sets modulo finite sets, is determined by various subclasses.

Theorem. *If* *is any nontrivial recursively invariant subclass of* , *then any automorphism of* *is determined uniquely by its action on* .

Theorem. *If* *is the class of recursive sets modulo finite sets or* ( = *maximal sets*, = *simple sets*) *then there is an automorphism of* (*the lattice generated by*) *which does not extend to one of* .

**[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)**

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