On the lattice of recursively enumerable sets

On the lattice of recursively enumerable sets
HTML articles powered by AMS MathViewer

Trans. Amer. Math. Soc. 130 (1968), 1-37

DOI: https://doi.org/10.1090/S0002-9947-1968-0227009-1

PDF | Request permission

References

Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0124208
Ju. L. Eršov, Decidability of the elementary theory of relatively complemented lattices and of the theory of filters, Algebra i Logika Sem. 3 (1964), no. 3, 17–38 (Russian). MR 0180490
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
Richard M. Friedberg, $4$-quantifier completeness: A Banach-Mazur functional not uniformly partial recursive, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astr. Phys. 6 (1958), 1–5. MR 0096588
Donald A. Martin, A theorem on hyperhypersimple sets, J. Symbolic Logic 28 (1963), 273–278. MR 177887, DOI 10.2307/2271305
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

26

Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
Abraham Robinson, Introduction to model theory and to the metamathematics of algebra, North-Holland Publishing Co., Amsterdam, 1963. MR 0153570
C. E. M. Yates, Recursively enumerable sets and retracing functions, Z. Math. Logik Grundlagen Math. 8 (1962), 331–345. MR 146072, DOI 10.1002/malq.19620080313
C. E. M. Yates, On the degrees of index sets, Trans. Amer. Math. Soc. 121 (1966), 309–328. MR 184855, DOI 10.1090/S0002-9947-1966-0184855-9