A decidable fragment of the elementary theory of the lattice of recursively enumerable sets

Lerman, M.; Soare, R. I.

doi:10.1090/S0002-9947-1980-0549153-7

A decidable fragment of the elementary theory of the lattice of recursively enumerable sets
HTML articles powered by AMS MathViewer

by M. Lerman and R. I. Soare PDF

Trans. Amer. Math. Soc. 257 (1980), 1-37 Request permission

Abstract:

A natural class of sentences about the lattice of recursively enumerable sets modulo finite sets is shown to be decidable. This class properly contains the class of sentences previously shown to be decidable by Lachlan. New structure results about the lattice of recursively enumerable sets are proved which play an important role in the decision procedure.

References

Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309–316. MR 109125, DOI 10.2307/2964290
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
A. H. Lachlan, The elementary theory of recursively enumerable sets, Duke Math. J. 35 (1968), 123–146. MR 227008
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, On some games which are relevant to the theory of recursively enumerable sets, Ann. of Math. (2) 91 (1970), 291–310. MR 284333, DOI 10.2307/1970579
Manuel Lerman, On elementary theories of some lattices of $\alpha$-recursively enumerable sets, Ann. Math. Logic 14 (1978), no. 3, 227–272. MR 510232, DOI 10.1016/0003-4843(78)90020-7
Manuel Lerman, Richard A. Shore, and Robert I. Soare, $r$-maximal major subsets, Israel J. Math. 31 (1978), no. 1, 1–18. MR 506379, DOI 10.1007/BF02761377
Manuel Lerman and Robert I. Soare, $d$-simple sets, small sets, and degree classes, Pacific J. Math. 87 (1980), no. 1, 135–155. MR 590872
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
James C. Owings Jr., Recursion, metarecursion, and inclusion, J. Symbolic Logic 32 (1967), 173–179. MR 216951, DOI 10.2307/2271654
Robert W. Robinson, Two theorems on hyperhypersimple sets, Trans. Amer. Math. Soc. 128 (1967), 531–538. MR 215714, DOI 10.1090/S0002-9947-1967-0215714-1
J. R. Shoenfield, Degrees of classes of RE sets, J. Symbolic Logic 41 (1976), no. 3, 695–696. MR 485293, DOI 10.2307/2272046
Richard A. Shore, Determining automorphisms of the recursively enumerable sets, Proc. Amer. Math. Soc. 65 (1977), no. 2, 318–325. MR 446931, DOI 10.1090/S0002-9939-1977-0446931-5
Richard A. Shore, Nowhere simple sets and the lattice of recursively enumerable sets, J. Symbolic Logic 43 (1978), no. 2, 322–330. MR 491089, DOI 10.2307/2272830
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