Determining automorphisms of the recursively enumerable sets
HTML articles powered by AMS MathViewer
- by Richard A. Shore
- Proc. Amer. Math. Soc. 65 (1977), 318-325
- DOI: https://doi.org/10.1090/S0002-9939-1977-0446931-5
- PDF | Request permission
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
- A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, DOI 10.1090/S0002-9947-1968-0227009-1
- A. H. Lachlan, Degrees of recursively enumerable sets which have no maximal supersets, J. Symbolic Logic 33 (1968), 431–443. MR 236016, DOI 10.2307/2270328
- Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310. MR 224469, DOI 10.1002/malq.19660120125 Myhill [1956], The lattice of recursively enumerable sets, J. Symbolic Logic 21, 220.
- Robert W. Robinson, A dichotomy of the recursively enumerable sets, Z. Math. Logik Grundlagen Math. 14 (1968), 339–356. MR 237334, DOI 10.1002/malq.19680142105
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-London, 1967. MR 0224462
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- J. R. Shoenfield, Degrees of classes of RE sets, J. Symbolic Logic 41 (1976), no. 3, 695–696. MR 485293, DOI 10.2307/2272046 A. Shore [1977], Nowhere simple sets, J. Symbolic Logic (to appear).
- Robert I. Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. of Math. (2) 100 (1974), 80–120. MR 360235, DOI 10.2307/1970842
- Robert I. Soare, Automorphisms of the lattice of recursively enumerable sets, Bull. Amer. Math. Soc. 80 (1974), 53–58. MR 373858, DOI 10.1090/S0002-9904-1974-13350-1
Bibliographic Information
- © Copyright 1977 American Mathematical Society
- 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