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 , 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]**A. H. Lachlan,*On the lattice of recursively enumerable sets*, Trans. Amer. Math. Soc.**130**(1968), 1–37. MR**0227009**, 10.1090/S0002-9947-1968-0227009-1**1.**A. H. Lachlan,*Degrees of recursively enumerable sets which have no maximal supersets.*, J. Symbolic Logic**33**(1968), 431–443. MR**0236016****[D]**Donald A. Martin,*Classes of recursively enumerable sets and degrees of unsolvability*, Z. Math. Logik Grundlagen Math.**12**(1966), 295–310. MR**0224469****[J]**Myhill [1956],*The lattice of recursively enumerable sets*, J. Symbolic Logic**21**, 220.**[R]**Robert W. Robinson,*A dichotomy of the recursively enumerable sets*, Z. Math. Logik Grundlagen Math.**14**(1968), 339–356. MR**0237334****[H]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[G]**Gerald E. Sacks,*Degrees of unsolvability*, Princeton University Press, Princeton, N.J., 1963. MR**0186554****[J]**J. R. Shoenfield,*Degrees of classes of RE sets*, J. Symbolic Logic**41**(1976), no. 3, 695–696. MR**0485293****[R]**A. Shore [1977],*Nowhere simple sets*, J. Symbolic Logic (to appear).**[R]**Robert I. Soare,*Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets*, Ann. of Math. (2)**100**(1974), 80–120. MR**0360235****2.**Robert I. Soare,*Automorphisms of the lattice of recursively enumerable sets*, Bull. Amer. Math. Soc.**80**(1974), 53–58. MR**0373858**, 10.1090/S0002-9904-1974-13350-1

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