Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Recursively enumerable sets and degrees


Author: Robert I. Soare
Journal: Bull. Amer. Math. Soc. 84 (1978), 1149-1181
MSC (1970): Primary 02F25, 02F30; Secondary 02F47, 02G05, 02G10, 06A20, 02F50
DOI: https://doi.org/10.1090/S0002-9904-1978-14552-2
MathSciNet review: 508451
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [Al] D. A. Alton, Uniformities in recursively enumerable sets, Doctoral Dissertation, Cornell Univ., Ithaca, N. Y., 1970.
  • [A2] D. A. Alton, Recursively enumerable sets which are uniform for finite extensions, J. Symbolic Logic 36 (1971), 271-287. MR 292671
  • [BeSo] V. L. Bennison and R. I. Soare, Some lowness properties and computational complexity sequences, Theor. Comput Sci. (to appear). MR 479982
  • [Bi1] G. Birkhoff, On the combination of subalgebras, Proc. Cambridge Philos. Soc. 29 (1933), 441-464.
  • [Bi2] G. Birkhoff, Lattice theory, 3rd ed., Amer. Math. Soc. Colloq. Publ., vol. 25, Amer. Math. Soc., Providence, R I., 1967. MR 227053
  • [BIMq] M. Blum and I. Marques, On complexity properties of recursively enumerable sets, J. Symbolic Logic 38 (1973), 579-593. MR 332455
  • [Bol] W. W. Boone, Certain simple unsolvable problems of group theory, Indag. Math. 16 (1954), 231-237, 492-497; ibid. 17 (1955), 252-256, 571-577; ibid. 19 (1957), 22-27, 227-232. MR 66372
  • [Bo2] W. W. Boone, The word problem, Ann. of Math. (2) 70 (1959), 207-265. MR 179237
  • [Bo3] W. W. Boone, Word problems and recursively enumerable degrees of unsolvability, A sequel on finitely presented groups, Ann. of Math. (2) 84 (1966), 49-84. MR 201500
  • [CoJ] P. Cohen and C. G. Jockusch, Jr., A lattice property of Post's simple set, Illinois J. Math. 19 (1975), 450-453. MR 389557
  • Alonzo Church, An Unsolvable Problem of Elementary Number Theory, Amer. J. Math. 58 (1936), no. 2, 345–363. MR 1507159, https://doi.org/10.2307/2371045
  • [Cp1] S. B. Cooper, Sets recursively enumerable in high degrees, Notices Amer. Math. Soc. 19 (1972), A-20.
  • [Cp2] S. B. Cooper, Minimal upper bounds for sequences of recursively enumerable degrees, J. London Math. Soc. 5 (1972), 445-450. MR 357092
  • [Cp3] S. B. Cooper, Degrees of unsolvability complementary between recursively enumerable degrees I, Ann. Math. Logic 4 (1972), 31-73. MR 294126
  • [Cp4] S. B. Cooper, Jump equivalence of the Δ20 hyperhyperimmune sets, J. Symbolic Logic 37 (1972) 598-600. MR 360240
  • [Cp5] S. B. Cooper, An annotated bibliography for the structure of the degrees below 0' with special reference to that of the recursively enumerable degrees, Recursive Function Theory Newsletter 5 (1974), 1-15.
  • [Cp6] S. B. Cooper, Minimal pairs and high recursively enumerable degrees, J. Symbolic Logic 39 (1974), 655-660. MR 371626
  • [Cp7] S. B. Cooper, On a theorem of C. E. M. Yates (preprint), 1974.
  • [Da1] M. Davis, Computability and unsolvability, McGraw-Hill, New York, 1958. MR 124208
  • [Da2] M. Davis, (Ed.), The undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions, Raven Press, Hewlitt, N. Y., 1965. MR 189996
  • [Da3] M. Davis, Hilbert's tenth problem is unsolvable, Amer. Math. Monthly 80 (1973), 233-269. MR 317916
  • [De] A. N. Degtev, Hypersimple sets with retraceable complements, Algebra i Logika 10 (1971), 235-246. MR 288023
  • [Dk1] J. Dekker, Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. 4 (1953), 495-501. MR 58533
  • [Dk2] J. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791-796. MR 63995
  • [Dk3] J. Dekker, Productive sets, Trans. Amer. Math. Soc. 78 (1955), 129-149. MR 67049
  • [DkMy1] J. C. E. Dekker and J. Myhill, Some theorems on classes of recursively enumerable sets, Trans. Amer. Math. Soc. 89 (1958), 25-29. MR 97310
  • [DkMy2] J. C. E. Dekker and J. Myhill, Retraceable sets, Canad. J. Math. 10 (1958), 357-373. MR 99292
  • [E1] Y. L. Ershov, Decidability of the elementary theory of relatively complemented distributive lattices and of the theory of filters, Algebra i Logika 3 (1964), 17-38. (Russian) MR 180490
  • Yu. L. Ershov, Necessary conditions for the isomorphism of Rogers semilattices of finite partially ordered sets, Algebra Logika 42 (2003), no. 4, 413–421, 510 (Russian, with Russian summary); English transl., Algebra Logic 42 (2003), no. 4, 232–236. MR 2017512, https://doi.org/10.1023/A:1025005309632
  • [Fe] S. Feferman, Degrees of unsolvability associated with classes of formalized theories, J. Symbolic Logic 22 (1957) 161-175. MR 98675
  • [Fn] L. Feiner, Orderings and Boolean algebras not isomorphic to recursive ones, Doctoral Dissertation, M.I.T., Cambridge, Mass., 1967.
  • [Fr1] R. M. Friedberg, The fine structure of degrees of unsolvability of recursively enumerable sets, Seminars of Cornell Institute for Symbolic Logic, 1957, pp. 404-406.
  • [Fr2] R. M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability, Proc. Nat Acad. Sci. USA. 43 (1957), 236-238. MR 18 #867. MR 84474
  • [Fr3] R. M. Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159-160. MR 98025
  • [Fr4] R. M. Friedberg, Three theorems on recursive enumeration: I. Decomposition, II. Maximal set, III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309-316. MR 22 #13. MR 109125
  • [FrRg] R. M. Friedberg and H. Rogers, Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117-125. MR 112831
  • [GiMr] J. Gill and P. Morris, On subcreative sets and S-reducibility, J. Symbolic Logic 39 (1974), 669-677. MR 363840
  • Kurt Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, Monatsh. Math. Phys. 38 (1931), no. 1, 173–198 (German). MR 1549910, https://doi.org/10.1007/BF01700692
  • [Gö2] K. Gödel, On undecidable propositions of formal mathematical systems, Notes by S. C. Kleene and Barkley Rosser on lectures at the Institute for Advanced Study, Princeton, N. J., 1934. Reprinted in Davis, [Da2].
  • [Ha] W. Hanf, Model theoretic methods in the study of elementary logic, Sympos. Theory of Models (Berkeley), North-Holland, Amsterdam, 1965, pp. 132-145. MR 210570
  • [Hy1] L. Hay, The class of recursively enumerable subsets of a recursively enumerable set, Pacific J. Math. 46 (1973), 167-183. MR 392525
  • [Hy2] L. Hay, The halting problem relativized to complements, Proc. Amer. Math. Soc. 41 (1973), 583-587. MR 327495
  • [J1] C. G. Jockusch, Jr., The degrees of hyperhyperimmune sets, J. Symbolic Logic 34 (1969), 489-493. MR 252224
  • [J2] C. G. Jockusch, Jr., Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229-237. MR 245439
  • [J3] C. G. Jockusch, Jr., Degrees in which the recursive sets are uniformly recursive, Canad. J. Math. 24 (1972), 1092-1099. MR 321716
  • [J4] C. G. Jockusch, Jr., Review of Lerman [Le3], MR 45 #3200.
  • [J5] C. G. Jockusch, Jr., II10 classes and Boolean combinations of recursively enumerable sets, J. Symbolic Logic 39 (1974), 95-96. MR 344094
  • [JSo1] C. G. Jockusch, Jr. and R. I. Soare, A minimal pair of II10 classes, J. Symbolic Logic 36 (1971), 66-78. MR 282834
  • [JSo2] C. G. Jockusch, Jr. and R. I. Soare, Degrees of members ofII10 classes, Pacific J. Math. 40 (1972), 605-616. MR 309722
  • [JSo3] C. G. Jockusch, Jr., II10 classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33-56. MR 316227
  • [JSo4] C. G. Jockusch, Jr., Post's problem and his hypersimple set, J. Symbolic Logic 38 (1973), 446-452. MR 337544
  • [Ka] S. Kallibekov, Index sets of degrees of unsolvability, Algebra i Logika 10 (1971), 316-326. (Russian) MR 294129
  • [Ke] C. F. Kent, Constructive analogues of the group of permutations of the natural numbers, Trans. Amer. Math. Soc. 104 (1962), 347-362. MR 140406
  • [Kl1] S. C. Kleene, A theory of positive integers in formal logic, Amer. J. Math. 57 (1935), 153-173, 219-244.
  • S. C. Kleene, General recursive functions of natural numbers, Math. Ann. 112 (1936), no. 1, 727–742. MR 1513071, https://doi.org/10.1007/BF01565439
  • [K13] S. C. Kleene, Introduction to metamathematics, Van Nostrand, New York, 1952. MR 14 #525. MR 51790
  • [KlPo] S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379-407. MR 15 #772. MR 61078
  • [Ku] A. V. Kuznecov, On primitive recursive functions of large oscillation, Dokl. Akad. Nauk SSSR, 71 (1950), 233-236. (Russian) MR 34731
  • [La1] A. H. Lachlan, Some notions of reducibility and productiveness, Z. Math. Logik Grundlagen Math. 11 (1965), 17-44. MR 172795
  • [La2] A. H. Lachlan, On a problem of G. E. Sacks, Proc. Amer. Math. Soc. 16 (1965), 972-979. MR 182560
  • [La3] A. H. Lachlan, A note on universal sets, J. Symbolic Logic 31 (1966), 573-574. MR 211857
  • [La4] A. H. Lachlan, The impossibility of finding relative complements for recursively enumerable degrees, J. Symbolic Logic 31 (1966), 434-454. MR 34 #5673. MR 205847
  • [La5] A. H. Lachlan, Lower bounds for pairs of r.e. degrees, Proc. London Math. Soc. 16 (1966), 537-569. MR 34 #4126. MR 204282
  • [La6] A. H. Lachlan, The priority method. I, Z. Math. Logik Grundlagen Math. 13 (1967), 1-10. MR 210582
  • [La7] A. H. Lachlan, Complete recursively enumerable sets, Proc. Amer. Math. Soc. 19 (1968), 99-102. MR 221933
  • [La8] A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1-37. MR 37 #2594. MR 227009
  • [La9] A. H. Lachlan, The elementary theory of recursively enumerable sets, Duke Math. J. 35 (1968), 123-146. MR 37 #2593. MR 227008
  • [La10] A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457-472. MR 38 #5620. MR 237331
  • [La11] A. H. Lachlan, Degrees of recursively enumerable sets which have no maximal superset, J. Symbolic Logic 33 (1968), 431-443. MR 38 #4314. MR 236016
  • [La12] 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 44 # 1652. MR 284333
  • [La13] A. H. Lachlan, Embedding nondistributive lattices in the recursively enumerable degrees, Conf. Mathematical Logic, London 1970, Lecture Notes in Math., no. 255, Springer-Verlag, Berlin and New York, 1972, pp. 149-177. MR 376318
  • [La14] A. H. Lachlan, The priority method for the construction of recursively enumerable sets, Proc. Cambridge Summer School in Logic, 1971, Lecture Notes in Math., no. 337, Springer-Verlag, Berlin and New York, 1973. MR 335247
  • [La15] A. H. Lachlan, Recursively enumerable degrees, Handwritten notes from lectures in Warsaw, April, 1973.
  • [La16] A. H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1975), 307-365. MR 409150
  • [La17] A. H. Lachlan, Uniform enumeration operations, J. Symbolic Logic 40 (1975), 401-409. MR 379156
  • [La18] A. H. Lachlan, wtt-complete sets are not necessarily tt-complete, Proc. Amer. Math. Soc. 48 (1975), 429-434. MR 357087
  • A. H. Lachlan, Bounding minimal pairs, J. Symbolic Logic 44 (1979), no. 4, 626–642. MR 550390, https://doi.org/10.2307/2273300
  • [Ld1] R. E. Ladner, A completely mitotic nonrecursive r.e. degree, Trans. Amer. Math. Soc. 184 (1973), 479-507. MR 398805
  • [Ld2] R. E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973), 199-211. MR 342381
  • [LdSs] R. E. Ladner and L. P. Sasso, The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 4 (1975), 429-448. MR 379157
  • [Le1] M. Lerman, Recursive functions modulo co-r-maximal sets, Trans. Amer. Math. Soc. 148 (1970), 429-444. MR 265157
  • [Le2] M. Lerman, Turing degrees and many-one degrees of maximal sets, J. Symbolic Logic 35 (1970), 29-40. MR 278948
  • [Le3] M. Lerman, Some theorems on r-maximal sets and major subsets of recursively enumerable sets, J. Symbolic Logic 36 (1971), 193-215. MR 45 #3200. MR 294127
  • [Le4] M. Lerman, Congruence relations, filters, ideals, and definability in lattices of α-recursively enumerable sets, J. Symbolic Logic 41 (1976), 405-418. MR 414334
  • [Le5] M. Lerman, Admissible ordinals and priority arguments, Proc. Cambridge Summer School in Logic, 1971, Lecture Notes in Math., no. 337, Springer-Verlag, Berlin and New York, 1973. MR 52 #59. MR 379153
  • [Le6] M. Lerman, Lattices of α-recursivefy enumerable sets, Oslo Conf. Generalized Recursion Theory, June, 1976 (to appear). MR 414334
  • [Le7] M. Lerman, On elementary theories of some lattices of α-recursively enumerable sets (to appear).
  • [Le8] M. Lerman, Automorphism bases for the semilattice of recursively enumerable degrees, Notices Amer. Math. Soc. 24 (1977), A-251. Abstract #77T-E10
  • M. Lerman and R. I. Soare, A decidable fragment of the elementary theory of the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 257 (1980), no. 1, 1–37. MR 549153, https://doi.org/10.1090/S0002-9947-1980-0549153-7
  • Manuel Lerman and Robert I. Soare, 𝑑-simple sets, small sets, and degree classes, Pacific J. Math. 87 (1980), no. 1, 135–155. MR 590872
  • Manuel Lerman, Richard A. Shore, and Robert I. Soare, 𝑟-maximal major subsets, Israel J. Math. 31 (1978), no. 1, 1–18. MR 506379, https://doi.org/10.1007/BF02761377
  • [Ma1] D. A. Martin, A theorem on hyperhypersimple sets, J. Symbolic Logic 28 (1963), 273-278. MR 177887
  • [Ma2] D. A. Martin, Completeness, the recursion theorem, and effectively simple sets, Proc. Amer. Math. Soc. 17 (1966), 838-842. MR 216950
  • [Ma3] D. A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295-310. MR 37 #68. MR 224469
  • [Ma4] D. A. Martin, On a question of G. E. Sacks, J. Symbolic Logic 31 (1966), 66-69. MR 204283
  • [Ma5] D. A. Martin, The priority method of Sacks, mimeographed notes, 1966.
  • [MaMi] D. A. Martin and W. Miller, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159-166. MR 228341
  • [MaPr] D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205-209. MR 280374
  • [Mtl] Y. Matiyasevič, Diophantine representation of enumerable predicates, Izv. Akad Nauk. SSSR Ser. Math. 35 (1971), 3-30. (Russian) MR 274289
  • [Mt2] Y. Matiyasevič, Enumerable sets are diophantine, Dokl. Akad. Nauk SSSR 191 (1970), 279-282. (Russian)
  • [Mc] T. G. McLaughlin, On a class of complete simple sets, Canad. Math. Bull. 8 (1965), 33-37. MR 182561
  • [Md] Y. T. Medvedev, On nonisomorphic recursively enumerable sets, Dokl. Akad. Nauk SSSR 102 (1955), 211-214. (Russian) MR 80614
  • [MkNe] G. Metakides and A. Nerode, Recursively enumerable vector spaces, Ann. Math. Logic, 1978 (to appear). MR 446936
  • [Mr] C. F. Miller, On group-theoretic decision problems and their classification, Ann. of Math. Studies, no. 68, Princeton Univ. Press, Princeton, N. J., 1971. MR 310044
  • [MoSo] M. D. Morley and R. I. Soare, Boolean algebras, splitting theorems and Δ20 sets, Fund. Math. 90 (1975), 45-52. MR 398807
  • [Mu] A. A. Muchnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR 108 (1956), 194-197. (Russian). MR 81859
  • [My1] J. Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97-108. MR 71379
  • [My2] J. Myhill, The lattice of recursively enumerable sets, J. Symbolic Logic 21 (1956), 220 (abstract).
  • [No] P. S. Novikov, On the algorithmic unsolvability of the word problem in groups, Trudy Mat. Inst. Steklov no. 44 Izdat Akad. Nauk SSSR, Moscow, (1955). (Russian) MR 75197
  • [O1] J. C. Owings, Jr., Recursion, metarecursion and inclusion, J. Symbolic Logic 32 (1967), 173-178. MR 216951
  • [O2] J. C. Owings, Jr., Review of Lachlan [La8], [La9] and Robinson [Ro3], [Ro4], J. Symbolic Logic 35 (1970), 153-155.
  • [Po] E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284-316. MR 6 #29. MR 10514
  • [Ri1] H. G. Rice, Classes of recursively enumerable sets and their decision problems, Trans. Amer. Math. Soc. 74 (1953), 358-366. MR 53041
  • [Ri2] H. G. Rice, On completely recursively enumerable classes and their key arrays, J. Symbolic Logic 21 (1956), 304-308. MR 81243
  • [Ro1] R. W. Robinson, The inclusion lattice and degrees of unsolvability of the recursively enumerable sets, Doctoral Dissertation, Cornell Univ., Ithaca, N. Y., 1966.
  • [Ro2] R. W. Robinson, Recursively enumerable sets not contained in any maximal set, Notices Amer. Math. Soc. 13 (1966), 325. Abstract #632-4.
  • [Ro3] R. W. Robinson, Two theorems on hyperhypersimple sets, Trans. Amer. Math. Soc. 128 (1967), 531-538. MR 35 #6549. MR 215714
  • [Ro4] R. W. Robinson, Simplicity of recursively enumerable sets, J. Symbolic Logic 32 (1967), 162-172. MR 36 #1323. MR 218235
  • [Ro5] R. W. Robinson, A dichotomy of the recursively enumerable sets, Z. Math. Logik Grundlagen Math. 14 (1968), 339-356. MR 38 #5623. MR 237334
  • [Ro6] R. W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285-314. MR 274286
  • [Ro7] R. W. Robinson, Jump restricted interpolation in the r.e. degrees, Ann. of Math. (2) 93 (1971) 586-596. MR 313037
  • [Rg1] H. Rogers, Jr., Computing degrees of unsolvability, Math. Ann. 138 (1959), 125-140. MR 114752
  • [Rg2] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 224462
  • [Rg3] H. Rogers, Jr., Some problems of definability in recursive function theory, Sets, Models and Recursion Theory, John Crossley, ed., North-Holland, Amsterdam, 1967, pp. 183-201. MR 223237
  • [Rs] B. Rosser, Extensions of some theorems of Gödel and Church, J. Symbolic Logic 1 (1936), 87-91.
  • [Sa1] G. E. Sacks, A minimal degree less than 0', Bull. Amer. Math. Soc. 67 (1961), 416-419. MR 126380
  • [Sa2] G. E. Sacks, On the degrees less than 0', Ann of Math. (2) 77 (1963), 211-231. MR 146078
  • [Sa3] G. E. Sacks, Recursive enumerability and the jump operator, Trans. Amer. Math. Soc. 108 (1963), 223-239. MR 27 #5681. MR 155747
  • [Sa4] G. E. Sacks, A maximal set which is not complete, Michigan Math. J. 11 (1964), 193-205. MR 29 #3368. MR 166090
  • [Sa5] G. E. Sacks, The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964), 300-312. MR 29 #3367. MR 166089
  • [Sa6] G. E. Sacks, A simple set which is not effectively simple, Proc. Amer. Math. Soc. 15 (1964), 51-55. MR 156780
  • [Sa7] G. E. Sacks, Degrees of unsolvability, rev. ed., Ann. of Math. Studies, no. 55, Princeton Univ. Press, Princeton, N. J., 1966. MR 186554
  • [Sa8] G. E. Sacks, On a theorem of Lachlan and Martin, Proc. Amer. Math. Soc. 18 (1967), 140-141. MR 207558
  • [Sa9] G. E. Sacks, RE sets higher up, Logic, Foundations of Mathematics and Computability Theory, 173-194, D. Reidel, Dordrecht-Holland, 1977. MR 472498
  • [Ss] L. P. Sasso, Deficiency sets and bounded information reducibilities, Trans. Amer. Math. Soc. 200 (1974), 267-290. MR 469729
  • [Sf1] J. R. Shoenfield, Quasicreative sets, Proc. Amer. Math. Soc. 8 (1957), 964-967. MR 89808
  • [Sf2] J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644-653. MR 105355
  • [Sf3] J. R. Shoenfield, Undecidable and creative theories, Fund. Math. 49 (1961), 171-179. MR 130177
  • [Sf4] J. R. Shoenfield, Application of model theory to degrees of unsolvability, Sympos. Theory of Models, North-Holland, Amsterdam, 1965, pp. 359-363. MR 34 #53. MR 200154
  • [Sf5] J. R. Shoenfield, Degrees of unsolvability, North-Holland, Amsterdam, 1971. MR 49 #4768. MR 282830
  • [Sf6] J. R. Shoenfield, The decision problem for recursively enumerable degrees, Bull. Amer. Math. Soc. 81 (1975), 973-977. MR 387035
  • [Sf7] J. R. Shoenfield, Degrees of classes of r.e. sets, J. Symbolic Logic 41 (1976), 695-696. MR 485293
  • [Sh1] R. A. Shore, A decidable class of two quantifier sentences in the theory of the recursively enumerable degrees, vol. 24 Notices Amer. Math. Soc. (1977), A-436. Abstract #77T-E48.
  • [Sh2] R. A. Shore, Nowhere simple sets and the lattice of recursively enumerable sets, J. Symbolic Logic 43 (1978), 322-330. MR 491089
  • [Sh3] R. A. Shore, Determining automorphisms of the recursively enumerable sets, Proc. Amer. Math. Soc. 65 (1977), 318-325. MR 446931
  • [Sh4] R. A. Shore, α-recursion theory, Handbook of Mathematical Logic, J. Barwise, ed., North-Holland, Amsterdam, 1978. MR 485262
  • [Si] S. G. Simpson, Degrees of unsolvability: A survey of results, Handbook of Mathematical Logic, J. Barwise, ed., North-Holland, Amsterdam, 1978.
  • [Sm] R. M. Smullyan, Effectively simple sets, Proc. Amer. Math Soc. 15 (1964), 893-894. MR 180485
  • [So1] R. I. Soare, The Friedberg-Muchnik Theorem re-examined, Canad. J. Math. 24 (1972), 1070-1078. MR 344096
  • [So2] R. I. Soare, Automorphisms of the lattice of recursively enumerable sets, Bull. Amer. Math. Soc. 80 (1974), 53-58. MR 373858
  • [So3] R. I. Soare, Automorphisms of the lattice of recursively enumerable sets. Part I: Maximal sets, Ann. of Math. 100 (1974), 80-120. MR 50 #10058. MR 360235
  • [So4] R. I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), 513-530. MR 429521
  • Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921
  • [So6] R. I. Soare, Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets (to appear). MR 373858
  • [So7] R. I. Soare, Post's program and complete recursively enumerable sets (to appear).
  • [So8] R. I. Soare, Computational complexity, speedable and levelable sets, J. Symbolic Logic 42 (1977), 545-563. MR 485278
  • [Sp1] C. Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581-592. MR 18 #1118. MR 82457
  • [Sp2] C. Spector, Inductively defined sets of natural numbers, Warsaw Symposium on Infinitistic Methods, New York, 1961, pp. 98-102. MR 141593
  • [St] M. Stob, Doctoral Dissertation, Univ. of Chicago, Chicago, III., 1979.
  • [Te1] S. Tennenbaum, Degree of unsolvability and the rate of growth of functions, Notices Amer. Math. Soc. 8 (1961), 608.
  • [Te2] S. Tennenbaum, Degree of unsolvability and the rate of growth of functions, Proc. Sympos. Math. Theory of Automata, Microwave Res. Inst. Sympos. Ser. vol. 12, Polytechnic Press, Brooklyn, N. Y., 1962. MR 167406
  • [Th] S. K. Thomason, Sublattices of the recursively enumerable degrees, Z. Math. Logik Grundlagen Math. 17 (1971), 273-280. MR 45 #8523. MR 299475
  • [Ts] R. E. Tulloss, Some complexities of simplicity: concerning grades of simplicity of recursively enumerable sets, Doctoral Dissertation, Univ. of Calif., Berkeley, Calif., 1971.
  • [Tu] A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. 42 (1936), 230-265; ibid. 43 (1936), 544-546.
  • [U] V. A. Uspenskiĭ, Some notes on recursively enumerable sets, Z. Math. Logik Grundlagen Math. 3 (1957), 157-170; English transl., Amer. Math. Soc. Transl. (2) 23 (1963), 89-101. MR 91917
  • [Y1] C. E. M. Yates, Recursively enumerable sets and retracing functions, Z. Math. Logik Grundlagen Math. 8 (1962), 331-345. MR 146072
  • [Y2] C. E. M. Yates, Three theorems on the degree of recursively enumerable sets, Duke Math. J. 32 (1965), 461-468. MR 31 #4721. MR 180486
  • [Y3] C. E. M. Yates, A minimal pair of r.e. degrees, J. Symbolic Logic 31 (1966), 159-168. MR 34 #5677. MR 205851
  • [Y4] C. E. M. Yates, On the degrees of index sets, Trans. Amer. Math. Soc. 121 (1966), 309-328. MR 184855
  • [Y5] C. E. M. Yates, Recursively enumerable degrees and the degrees less than0', Sets, Models and Recursion Theory, North-Holland, Amsterdam, 1967, pp. 264-271. MR 219422
  • [Y6] C. E. M. Yates, On the degrees of index sets. II. Trans. Amer. Math. Soc. 135 (1969), 249-266. MR 241295
  • [Y7] C. E. M. Yates, Initial segments of the degrees of unsolvability, Part I, Mathematical Logic and the Foundations of Set Theory (Jerusalem), North-Holland, Amsterdam, 1970, pp. 63-83. MR 269505
  • [Y8] C. E. M. Yates, Initial segments and implications for the structure of degrees, Conference in Mathematical Logic-London 1970, Lecture Notes in Math., no. 255, Springer-Verlag, Berlin and New York, 1972, pp. 305-335. MR 357095
  • [Y9] C. E. M. Yates, Prioric games and minimal degrees below0', Fund. Math. 82 (1974), 217-237. MR 406784
  • [Y10] C. E. M. Yates, Banach-Mazur games, comeager sets, and degrees of unsolvability, Math. Proc. Cambridge Philos. Soc. (to appear). MR 406783

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1970): 02F25, 02F30, 02F47, 02G05, 02G10, 06A20, 02F50

Retrieve articles in all journals with MSC (1970): 02F25, 02F30, 02F47, 02G05, 02G10, 06A20, 02F50


Additional Information

DOI: https://doi.org/10.1090/S0002-9904-1978-14552-2

American Mathematical Society