Recursively enumerable sets and degrees
HTML articles powered by AMS MathViewer
- by Robert I. Soare PDF
- Bull. Amer. Math. Soc. 84 (1978), 1149-1181
References
-
[Al] D. A. Alton, Uniformities in recursively enumerable sets, Doctoral Dissertation, Cornell Univ., Ithaca, N. Y., 1970.
- Recursively enumerable sets which are uniform for finite extensions, J. Symbolic Logic 36 (1971), 271–287. MR 292671, DOI 10.2307/2270262
- Victor L. Bennison and Robert I. Soare, Some lowness properties and computational complexity sequences, Theoret. Comput. Sci. 6 (1978), no. 3, 233–254. MR 479982, DOI 10.1016/0304-3975(78)90007-5 [Bi1] G. Birkhoff, On the combination of subalgebras, Proc. Cambridge Philos. Soc. 29 (1933), 441-464.
- Garrett Birkhoff, Lattice theory, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
- M. Blum and I. Marques, On complexity properties of recursively enumerable sets, J. Symbolic Logic 38 (1973), 579–593. MR 332455, DOI 10.2307/2271984
- William W. Boone, Certain simple, unsolvable problems of group theory. I, Nederl. Akad. Wetensch. Proc. Ser. A. 57 (1954), 231–237 = Indag. Math. 16, 231–237 (1954). MR 0066372
- William W. Boone, The word problem, Ann. of Math. (2) 70 (1959), 207–265. MR 179237, DOI 10.2307/1970103
- William 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, DOI 10.2307/1970530
- Paul F. Cohen and Carl 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, DOI 10.2307/2371045 [Cp1] S. B. Cooper, Sets recursively enumerable in high degrees, Notices Amer. Math. Soc. 19 (1972), A-20.
- S. B. Cooper, Minimal upper bounds for sequences of recursively enumerable degrees, J. London Math. Soc. (2) 5 (1972), 445–450. MR 357092, DOI 10.1112/jlms/s2-5.3.445
- S. B. Cooper, Degrees of unsolvability complementary between recursively enumerable degrees. I, Ann. Math. Logic 4 (1972), 31–73. MR 294126, DOI 10.1016/0003-4843(72)90011-3
- S. B. Cooper, Jump equivalence of the $\Delta ^{0}_{2}$ hyperhyperimmune sets, J. Symbolic Logic 37 (1972), 598–600. MR 360240, DOI 10.2307/2272750 [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.
- S. B. Cooper, Minimal pairs and high recursively enumerable degrees, J. Symbolic Logic 39 (1974), 655–660. MR 371626, DOI 10.2307/2272849 [Cp7] S. B. Cooper, On a theorem of C. E. M. Yates (preprint), 1974.
- 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
- Martin Davis (ed.), The undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions, Raven Press, Hewlett, N.Y., 1965. MR 0189996
- Martin Davis, Hilbert’s tenth problem is unsolvable, Amer. Math. Monthly 80 (1973), 233–269. MR 317916, DOI 10.2307/2318447
- A. N. Degtev, Hypersimple sets with retraceable complements, Algebra i Logika 10 (1971), 235–246 (Russian). MR 0288023
- J. C. E. Dekker, Two notes on recursively enumerable sets, Proc. Amer. Math. Soc. 4 (1953), 495–501. MR 58533, DOI 10.1090/S0002-9939-1953-0058533-7
- J. C. E. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791–796. MR 63995, DOI 10.1090/S0002-9939-1954-0063995-6
- J. C. E. Dekker, Productive sets, Trans. Amer. Math. Soc. 78 (1955), 129–149. MR 67049, DOI 10.1090/S0002-9947-1955-0067049-X
- J. C. E. Dekker and J. Myhill, Some theorems on classes of recursively enumerable sets, Trans. Amer. Math. Soc. 89 (1958), 25–59. MR 97310, DOI 10.1090/S0002-9947-1958-0097310-7
- J. C. E. Dekker and J. Myhill, Retraceable sets, Canadian J. Math. 10 (1958), 357–373. MR 99292, DOI 10.4153/CJM-1958-035-x
- 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
- 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, DOI 10.1023/A:1025005309632
- Solomon Feferman, Degrees of unsolvability associated with classes of formalized theories, J. Symbolic Logic 22 (1957), 161–175. MR 98675, DOI 10.2307/2964178 [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.
- Richard M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944), Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236–238. MR 84474, DOI 10.1073/pnas.43.2.236
- Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, DOI 10.2307/2964177
- 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 and Hartley Rogers Jr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math. 5 (1959), 117–125. MR 112831, DOI 10.1002/malq.19590050703
- John T. Gill III and Paul H. Morris, On subcreative sets and $S$-reducibility, J. Symbolic Logic 39 (1974), 669–677. MR 363840, DOI 10.2307/2272852
- 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, DOI 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].
- William Hanf, Model-theoretic methods in the study of elementary logic, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 132–145. MR 0210570
- Louise Hay, The class of recursively enumerable subsets of a recursively enumerable set, Pacific J. Math. 46 (1973), 167–183. MR 392525, DOI 10.2140/pjm.1973.46.167
- Louise Hay, The halting problem relativized to complements, Proc. Amer. Math. Soc. 41 (1973), 583–587. MR 327495, DOI 10.1090/S0002-9939-1973-0327495-X
- Carl G. Jockusch Jr., The degrees of hyperhyperimmune sets, J. Symbolic Logic 34 (1969), 489–493. MR 252224, DOI 10.2307/2270912
- Carl G. Jockusch Jr., Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229–237. MR 245439, DOI 10.1090/S0002-9947-1969-0245439-X
- Carl G. Jockusch Jr., Degrees in which the recursive sets are uniformly recursive, Canadian J. Math. 24 (1972), 1092–1099. MR 321716, DOI 10.4153/CJM-1972-113-9 [J4] C. G. Jockusch, Jr., Review of Lerman [Le3], MR 45 #3200.
- Carl G. Jockusch Jr., $\Pi ^{0}_{1}$ classes and Boolean combinations of recursively enumerable sets, J. Symbolic Logic 39 (1974), 95–96. MR 344094, DOI 10.2307/2272348
- Carl G. Jockusch Jr. and Robert I. Soare, A minimal pair of $\Pi _{1}{}^{0}$ classes, J. Symbolic Logic 36 (1971), 66–78. MR 282834, DOI 10.2307/2271516
- Carl G. Jockusch Jr. and Robert I. Soare, Degrees of members of $\Pi ^{0}_{1}$ classes, Pacific J. Math. 40 (1972), 605–616. MR 309722, DOI 10.2140/pjm.1972.40.605
- Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
- Carl G. Jockusch Jr. and Robert I. Soare, Post’s problem and his hypersimple set, J. Symbolic Logic 38 (1973), 446–452. MR 337544, DOI 10.2307/2273042
- S. Kallibekov, Index sets of degrees of unsolvability, Algebra i Logika 10 (1971), 316–326 (Russian). MR 0294129
- Clement F. Kent, Constructive analogues of the group of permutations of the natural numbers, Trans. Amer. Math. Soc. 104 (1962), 347–362. MR 140406, DOI 10.1090/S0002-9947-1962-0140406-2 [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, DOI 10.1007/BF01565439
- Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI 10.2307/1969708
- A. V. Kuznecov, On primitive recursive functions of large oscillation, Doklady Akad. Nauk SSSR (N.S.) 71 (1950), 233–236 (Russian). MR 0034731
- A. H. Lachlan, Some notions of reducibility and productiveness, Z. Math. Logik Grundlagen Math. 11 (1965), 17–44. MR 172795, DOI 10.1002/malq.19650110104
- A. H. Lachlan, On a problem of G. E. Sacks, Proc. Amer. Math. Soc. 16 (1965), 972–979. MR 182560, DOI 10.1090/S0002-9939-1965-0182560-0
- A. H. Lachlan, A note on universal sets, J. Symbolic Logic 31 (1966), 573–574. MR 211857, DOI 10.2307/2269692
- A. H. Lachlan, The impossibility of finding relative complements for recursively enumerable degrees, J. Symbolic Logic 31 (1966), 434–454. MR 205847, DOI 10.2307/2270459
- A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569. MR 204282, DOI 10.1112/plms/s3-16.1.537
- A. H. Lachlan, The priority method. I, Z. Math. Logik Grundlagen Math. 13 (1967), 1–10. MR 210582, DOI 10.1002/malq.19670130102
- A. H. Lachlan, Complete recursively enumerable sets, Proc. Amer. Math. Soc. 19 (1968), 99–102. MR 221933, DOI 10.1090/S0002-9939-1968-0221933-7
- 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, The elementary theory of recursively enumerable sets, Duke Math. J. 35 (1968), 123–146. MR 227008, DOI 10.1215/S0012-7094-68-03513-8
- A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457–472. MR 237331, DOI 10.1002/malq.19680143002
- 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, 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
- A. H. Lachlan, Embedding nondistributive lattices in the recursively enumerable degrees, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Lecture Notes in Math., Vol. 255, Springer, Berlin, 1972, pp. 149–177. MR 0376318
- A. H. Lachlan, The priority method for the construction of recursively enumerable sets, Cambridge Summer School in Mathematical Logic (Cambridge, 1971) Lecture Notes in Math., Vol. 337, Springer, Berlin, 1973, pp. 299–310. MR 0335247 [La15] A. H. Lachlan, Recursively enumerable degrees, Handwritten notes from lectures in Warsaw, April, 1973.
- Alistair H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1976), no. 4, 307–365. MR 409150, DOI 10.1016/0003-4843(76)90016-4
- A. H. Lachlan, Uniform enumeration operations, J. Symbolic Logic 40 (1975), no. 3, 401–409. MR 379156, DOI 10.2307/2272164
- A. H. Lachlan, $\textrm {wtt}$-complete sets are not necessarily $\textrm {tt}$-complete, Proc. Amer. Math. Soc. 48 (1975), 429–434. MR 357087, DOI 10.1090/S0002-9939-1975-0357087-X
- A. H. Lachlan, Bounding minimal pairs, J. Symbolic Logic 44 (1979), no. 4, 626–642. MR 550390, DOI 10.2307/2273300
- Richard E. Ladner, A completely mitotic nonrecursive r.e. degree, Trans. Amer. Math. Soc. 184 (1973), 479–507 (1974). MR 398805, DOI 10.1090/S0002-9947-1973-0398805-7
- Richard E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973), 199–211. MR 342381, DOI 10.2307/2272056
- Richard E. Ladner and Leonard P. Sasso Jr., The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), no. 4, 429–448. MR 379157, DOI 10.1016/0003-4843(75)90007-8
- Manuel Lerman, Recursive functions modulo $\textrm {CO}-r$-maximal sets, Trans. Amer. Math. Soc. 148 (1970), 429–444. MR 265157, DOI 10.1090/S0002-9947-1970-0265157-X
- Manuel Lerman, Turing degrees and many-one degrees of maximal sets, J. Symbolic Logic 35 (1970), 29–40. MR 278948, DOI 10.2307/2271152
- Manuel Lerman, Some theorems on $r$-maximal sets and major subsets of recursively enumerable sets, J. Symbolic Logic 36 (1971), 193–215. MR 294127, DOI 10.2307/2270255
- Manuel Lerman, Congruence relations, filters, ideals, and definability in lattices of $\alpha$ recursively enumerable sets, J. Symbolic Logic 41 (1976), no. 2, 405–418. MR 414334, DOI 10.2307/2272239
- Manuel Lerman, Admissible ordinals and priority arguments, Cambridge Summer School in Mathematical Logic (Cambridge, 1971) Lecture Notes in Math., Vol. 337, Springer, Berlin, 1973, pp. 311–344. MR 0379153
- Manuel Lerman, Congruence relations, filters, ideals, and definability in lattices of $\alpha$ recursively enumerable sets, J. Symbolic Logic 41 (1976), no. 2, 405–418. MR 414334, DOI 10.2307/2272239 [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, DOI 10.1090/S0002-9947-1980-0549153-7
- 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, DOI 10.2140/pjm.1980.87.135
- 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
- Donald A. Martin, A theorem on hyperhypersimple sets, J. Symbolic Logic 28 (1963), 273–278. MR 177887, DOI 10.2307/2271305
- Donald A. Martin, Completeness, the recursion theorem, and effectively simple sets, Proc. Amer. Math. Soc. 17 (1966), 838–842. MR 216950, DOI 10.1090/S0002-9939-1966-0216950-5
- 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
- Donald A. Martin, On a question of G. E. Sacks, J. Symbolic Logic 31 (1966), 66–69. MR 204283, DOI 10.2307/2270620 [Ma5] D. A. Martin, The priority method of Sacks, mimeographed notes, 1966.
- Webb Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159–166. MR 228341, DOI 10.1002/malq.19680140704
- D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205–209. MR 280374, DOI 10.2307/2270510
- Ju. V. Matijasevič, Diophantine representation of enumerable predicates, Izv. Akad. Nauk SSSR Ser. Mat. 35 (1971), 3–30 (Russian). MR 0274289 [Mt2] Y. Matiyasevič, Enumerable sets are diophantine, Dokl. Akad. Nauk SSSR 191 (1970), 279-282. (Russian)
- T. G. McLaughlin, On a class of complete simple sets, Canad. Math. Bull. 8 (1965), 33–37. MR 182561, DOI 10.4153/CMB-1965-006-2
- Yu. T. Medvedev, On nonisomorphic recursively enumerable sets, Dokl. Akad. Nauk SSSR (N.S.) 102 (1955), 211–214 (Russian). MR 0080614
- G. Metakides and A. Nerode, Recursively enumerable vector spaces, Ann. Math. Logic 11 (1977), no. 2, 147–171. MR 446936, DOI 10.1016/0003-4843(77)90015-8
- Charles F. Miller III, On group-theoretic decision problems and their classification, Annals of Mathematics Studies, No. 68, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. MR 0310044
- Michael D. Morley and Robert I. Soare, Boolean algebras, splitting theorems, and $D^{0}_{2}$ sets, Fund. Math. 90 (1975), no. 1, 45–52. MR 398807, DOI 10.4064/fm-90-1-45-52
- A. A. Mučnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR (N.S.) 108 (1956), 194–197 (Russian). MR 0081859
- John Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97–108. MR 71379, DOI 10.1002/malq.19550010205 [My2] J. Myhill, The lattice of recursively enumerable sets, J. Symbolic Logic 21 (1956), 220 (abstract).
- P. S. Novikov, Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp, Izdat. Akad. Nauk SSSR, Moscow, 1955 (Russian). Trudy Mat. Inst. Steklov. no. 44. MR 0075197
- James C. Owings Jr., Recursion, metarecursion, and inclusion, J. Symbolic Logic 32 (1967), 173–179. MR 216951, DOI 10.2307/2271654 [O2] J. C. Owings, Jr., Review of Lachlan [La8], [La9] and Robinson [Ro3], [Ro4], J. Symbolic Logic 35 (1970), 153-155.
- 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
- H. G. Rice, Classes of recursively enumerable sets and their decision problems, Trans. Amer. Math. Soc. 74 (1953), 358–366. MR 53041, DOI 10.1090/S0002-9947-1953-0053041-6
- H. G. Rice, On completely recursively enumerable classes and their key arrays, J. Symbolic Logic 21 (1956), 304–308. MR 81243, DOI 10.2307/2269105 [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.
- 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
- Robert W. Robinson, Simplicity of recursively enumerable sets, J. Symbolic Logic 32 (1967), 162–172. MR 218235, DOI 10.2307/2271653
- 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
- Robert W. Robinson, Interpolation and embedding in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 285–314. MR 274286, DOI 10.2307/1970776
- Robert W. Robinson, Jump restricted interpolation in the recursively enumerable degrees, Ann. of Math. (2) 93 (1971), 586–596. MR 313037, DOI 10.2307/1970889
- Hartley Rogers Jr., Computing degrees of unsolvability, Math. Ann. 138 (1959), 125–140. MR 114752, DOI 10.1007/BF01342939
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- H. Rogers Jr., Some problems of definability in recursive function theory, Sets, Models and Recursion Theory (Proc. Summer School Math. Logic and Tenth Logic Colloq., Leicester, 1965) North-Holland, Amsterdam, 1967, pp. 183–201. MR 0223237 [Rs] B. Rosser, Extensions of some theorems of Gödel and Church, J. Symbolic Logic 1 (1936), 87-91.
- Gerald E. Sacks, A minimal degree less than $0’$, Bull. Amer. Math. Soc. 67 (1961), 416–419. MR 126380, DOI 10.1090/S0002-9904-1961-10652-6
- Gerald E. Sacks, On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231. MR 146078, DOI 10.2307/1970214
- Gerald E. Sacks, Recursive enumerability and the jump operator, Trans. Amer. Math. Soc. 108 (1963), 223–239. MR 155747, DOI 10.1090/S0002-9947-1963-0155747-3
- Gerald E. Sacks, A maximal set which is not complete, Michigan Math. J. 11 (1964), 193–205. MR 166090
- Gerald E. Sacks, The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964), 300–312. MR 166089, DOI 10.2307/1970393
- Gerald E. Sacks, A simple set which is not effectively simple, Proc. Amer. Math. Soc. 15 (1964), 51–55. MR 156780, DOI 10.1090/S0002-9939-1964-0156780-4
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- Gerald E. Sacks, On a theorem of Lachlan and Martin, Proc. Amer. Math. Soc. 18 (1967), 140–141. MR 207558, DOI 10.1090/S0002-9939-1967-0207558-7
- Gerald E. Sacks, R.E. sets higher up, Logic, foundations of mathematics and computability theory (Proc. Fifth Internat. Congr. Logic, Methodology and Philos. of Sci., Univ. Western Ontario, London, Ont., 1975) Univ. Western Ontario Ser. Philos. Sci., Vol. 9, Reidel, Dordrecht, 1977, pp. 173–194. MR 0472498
- Leonard P. Sasso Jr., Deficiency sets and bounded information reducibilities, Trans. Amer. Math. Soc. 200 (1974), 267–290. MR 469729, DOI 10.1090/S0002-9947-1974-0469729-2
- J. R. Shoenfield, Quasicreative sets, Proc. Amer. Math. Soc. 8 (1957), 964–967. MR 89808, DOI 10.1090/S0002-9939-1957-0089808-7
- J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644–653. MR 105355, DOI 10.2307/1970028
- J. R. Shoenfield, Undecidable and creative theories, Fund. Math. 49 (1960/61), 171–179. MR 130177, DOI 10.4064/fm-49-2-171-179
- J. R. Shoenfield, Applications of model theory to degrees of unsolvability, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 359–363. MR 0200154
- J. R. Shoenfield, Measurable cardinals, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 19–49. MR 0282830
- J. R. Shoenfield, The decision problem for recursively enumerable degrees, Bull. Amer. Math. Soc. 81 (1975), no. 6, 973–977. MR 387035, DOI 10.1090/S0002-9904-1975-13876-6
- J. R. Shoenfield, Degrees of classes of RE sets, J. Symbolic Logic 41 (1976), no. 3, 695–696. MR 485293, DOI 10.2307/2272046 [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.
- 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
- 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
- Recursion theory, Handbook of mathematical logic, Part C, Studies in Logic and the Foundations of Math., Vol. 90, North-Holland, Amsterdam, 1977, pp. 525–815. With contributions by Herbert B. Enderton, Martin Davis, Michael O. Rabin, Stephen G. Simpson, Richard A. Shore, Alexander Kechris, Yiannis N. Moschovakis, Peter Aczel and Donald A. Martin. MR 0485262 [Si] S. G. Simpson, Degrees of unsolvability: A survey of results, Handbook of Mathematical Logic, J. Barwise, ed., North-Holland, Amsterdam, 1978.
- Raymond M. Smullyan, Effectively simple sets, Proc. Amer. Math. Soc. 15 (1964), 893–895. MR 180485, DOI 10.1090/S0002-9939-1964-0180485-7
- Robert I. Soare, The Friedberg-Muchnik theorem re-examined, Canadian J. Math. 24 (1972), 1070–1078. MR 344096, DOI 10.4153/CJM-1972-110-4
- 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
- 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, The infinite injury priority method, J. Symbolic Logic 41 (1976), no. 2, 513–530. MR 429521, DOI 10.2307/2272252
- 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, DOI 10.1007/978-3-662-02460-7
- 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 [So7] R. I. Soare, Post’s program and complete recursively enumerable sets (to appear).
- Robert I. Soare, Computational complexity, speedable and levelable sets, J. Symbolic Logic 42 (1977), no. 4, 545–563. MR 485278, DOI 10.2307/2271876
- Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592. MR 82457, DOI 10.2307/1969604
- C. Spector, Inductively defined sets of natural numbers, Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959), Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warsaw, 1961, pp. 97–102. MR 0141593 [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.
- S. Tennenbaum, Degree of unsolvability and the rate of growth of functions, Proc. Sympos. Math. Theory of Automata (New York, 1962) Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., 1963, pp. 71–73. MR 0167406
- S. K. Thomason, Sublattices of the recursively enumerable degrees, Z. Math. Logik Grundlagen Math. 17 (1971), 273–280. MR 299475, DOI 10.1002/malq.19710170131 [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.
- V. A. Uspenskij, Some notes on recursively enumerable sets, Z. Math. Logik Grundlagen Math. 3 (1957), 157–170 (Russian, with English summary). MR 91917
- 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, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461–468. MR 180486
- C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 205851, DOI 10.2307/2269807
- 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
- C. E. M. Yates, Recursively enumerable degrees and the degrees less than ${\bf 0}^{(1)}$, Sets, Models and Recursion Theory (Proc. Summer School Math. Logic and Tenth Logic Colloq., Leicester, 1965) North-Holland, Amsterdam, 1967, pp. 264–271. MR 0219422
- C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249–266. MR 241295, DOI 10.1090/S0002-9947-1969-0241295-4
- C. E. M. Yates, Initial segments of the degrees of unsolvability. I. A survey, Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq., Jerusalem, 1968) North-Holland, Amsterdam, 1970, pp. 63–83. MR 0269505
- C. E. M. Yates, Initial segments and implications for the structure of degrees, Conference in Mathematical Logic—London ’70 (Proc. Conf., Bedford Coll., London, 1970) Lecture Notes in Math., Vol. 255, Springer, Berlin, 1972, pp. 305–335. MR 0357095
- C. E. M. Yates, Prioric games and minimal degrees below ${\bf 0}^{(1)}$, Fund. Math. 82 (1974/75), 217–237. MR 406784, DOI 10.4064/fm-82-3-217-237
- C. E. M. Yates, Banach-Mazur games, comeager sets and degrees of unsolvability, Math. Proc. Cambridge Philos. Soc. 79 (1976), no. 2, 195–220. MR 406783, DOI 10.1017/S0305004100052221
Additional Information
- 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