Determining automorphisms of the recursively enumerable sets
Author:
Richard A. Shore
Journal:
Proc. Amer. Math. Soc. 65 (1977), 318325
MSC:
Primary 02F25
MathSciNet review:
0446931
Fulltext 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
(37 #2594), http://dx.doi.org/10.1090/S00029947196802270091
 1.
A.
H. Lachlan, Degrees of recursively enumerable sets which have no
maximal supersets., J. Symbolic Logic 33 (1968),
431–443. MR 0236016
(38 #4314)
 [D]
Donald
A. Martin, Classes of recursively enumerable sets and degrees of
unsolvability, Z. Math. Logik Grundlagen Math. 12
(1966), 295–310. MR 0224469
(37 #68)
 [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 (38 #5623)
 [H]
Hartley
Rogers Jr., Theory of recursive functions and effective
computability, McGrawHill Book Co., New YorkToronto, Ont.London,
1967. MR
0224462 (37 #61)
 [G]
Gerald
E. Sacks, Degrees of unsolvability, Princeton University
Press, Princeton, N.J., 1963. MR 0186554
(32 #4013)
 [J]
J.
R. Shoenfield, Degrees of classes of RE sets, J. Symbolic
Logic 41 (1976), no. 3, 695–696. MR 0485293
(58 #5140)
 [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 (50 #12685)
 2.
Robert
I. Soare, Automorphisms of the lattice of
recursively enumerable sets, Bull. Amer. Math.
Soc. 80 (1974),
53–58. MR
0373858 (51 #10058), http://dx.doi.org/10.1090/S000299041974133501
 [A]
 H. Lachlan [1968], On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130, 137. MR 0227009 (37:2594)
 1.
 [1968a], Degrees of recursively enumerable sets which have no maximal superset, J. Symbolic Logic 33, 431443. MR 0236016 (38:4314)
 [D]
 A. Martin [1966], Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12, 295310. 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, 339356. MR 0237334 (38:5623)
 [H]
 Rogers, Jr. [1967], Theory of recursive functions and effective computability, McGrawHill, 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, 695696. 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, 80120. MR 0360235 (50:12685)
 2.
 [1974a], Automorphisms of the lattice of recursively enumerable sets, Bull. Amer. Math. Soc. 80, 5358. MR 0373858 (51:10058)
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC:
02F25
Retrieve articles in all journals
with MSC:
02F25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029939197704469315
PII:
S 00029939(1977)04469315
Keywords:
Recursively enumerable sets,
recursive sets,
automorphisms of r.e. sets
Article copyright:
© Copyright 1977
American Mathematical Society
