Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

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

 
 

 

Strong reducibilities


Author: Piergiorgio Odifreddi
Journal: Bull. Amer. Math. Soc. 4 (1981), 37-86
MSC (1980): Primary 03D30; Secondary 03D25
DOI: https://doi.org/10.1090/S0273-0979-1981-14863-1
MathSciNet review: 590818
Full-text PDF

References | Similar Articles | Additional Information

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

  • O. V. Belegradek, 𝑚-degrees of the word problem, Sibirsk. Mat. Zh. 19 (1978), no. 6, 1232–1236, 1436 (Russian). MR 515176
  • [Co] P. F. Cohen, Weak truth-table reducibility and the pointwise ordering of 1-1 recursive functions, Doctoral Dissertation, Univ. of Illinois, Urbana, Illinois, 1975.
  • [Da1] M. Davis, The undecidable, Raven Press, New York, 1965. MR 189996
  • Handbook of mathematical logic, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland Publishing Co., Amsterdam, 1977. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra. MR 457132
  • [Deg1] A. N. Degtev, Remarks on retraceable, regressive, and pointwise-decomposable sets, Algebra and Logic 9 (1970), 390-395. MR 286651
  • [Deg2] A. N. Degtev, Hypersimple sets with retraceable complements, Algebra and Logic 10 (1971), 147-154. MR 288023
  • [Deg3] A. N. Degtev, m-powers of simple sets, Algebra and Logic 11 (1972), 74-80.
  • [Deg4] A. N. Degtev, Hereditary sets and tabular reducibility, Algebra and Logic 11 (1972), 145-152.
  • [Deg5] A. N. Degtev, tt- and m-degrees, Algebra and Logic 12 (1973), 78-89. MR 424545
  • [Deg6] A. N. Degtev, Partially ordered sets of 1-degrees, contained in recursively enumerable m-degrees, Algebra and Logic 15 (1976), 153-164. MR 537543
  • [Deg7] A. N. Degtev, On minimal 1-degrees and tt-reducibility, Sibirsk. Math. Z. 17 (1976), 1014-1022. (Russian) MR 422004
  • A. N. Dëgtev, m-degrees of supersets of simple sets, Mat. Zametki 23 (1978), no. 6, 889–893 (Russian). MR 502057
  • A. N. Dëgtev, Three theorems on 𝑡𝑡-degrees, Algebra i Logika 17 (1978), no. 3, 270–281, 357–358 (Russian). MR 538297
  • [Den1] S. D. Denisov, On m-degrees of recursively enumerable sets, Algebra and Logic 9 (1970), 254-256. MR 286652
  • [Den2] A. N. Degtev, Three theorems on elementary theories and tt-reducibility, Algebra and Logic 13 (1974), 1-2.
  • [Dek] J. C. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791-796. MR 63995
  • [E1] Y. L. Ershov, Hyperhypersimple m-degrees, Algebra and Logic 8 (1969), 298-315. MR 280368
  • [E2] Y. L. Ershov, On inseparable pairs, Algebra and Logic 9 (1970), 396-399. MR 286653
  • [E3] Y. L. Ershov, Positive equivalences, Algebra and Logic 10 (1971), 378-394. MR 307896
  • [E4] Y. L. Ershov, The upper semilattice of numerations of a finite set, Algebra and Logic 14 (1975), 159-175. MR 416884
  • [EL] Y. L. Ershov and I. A. Lavrov, The upper semilattice L(γ), Algebra and Logic 12 (1973), 93-106. MR 409148
  • [ELTT] Y. L. Ershov et al., Elementary theories, Russian Math. Surveys 20 (1965), 35-105. MR 186553
  • Jeanne Ferrante and Charles W. Rackoff, The computational complexity of logical theories, Lecture Notes in Mathematics, vol. 718, Springer, Berlin, 1979. MR 537764
  • [Fr] 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 109125
  • [Go] R. L. Goodstein, Recursive analysis, North-Holland, Amsterdam, 1961. MR 131974
  • Peter G. Hinman, Recursion-theoretic hierarchies, Springer-Verlag, Berlin-New York, 1978. Perspectives in Mathematical Logic. MR 499205
  • [J1] C. G. Jockusch, Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420-436. MR 220595
  • [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
  • [JSo] C. G. Jockusch, Jr. and R. I. Soare, Post's problem and his hypersimple set, J. Symbolic Logic 38 (1973), 446-452. MR 337544
  • [Ka1] S. Kallibekov, Index sets of degrees of unsolvability, Algebra and Logic 10 (1971), 198-204. MR 294129
  • [Ka2] S. Kallibekov, On degrees of recursively enumerable sets, Sibirsk. Math. J. 14 (1973), 290-293. MR 329876
  • [Ka3] S. Kallibekov, Truth tabular degrees of recursively enumerable sets, Math. Notes 14 (1973), 958-961. MR 329876
  • [KM] A. S. Kechris and D. A. Martin, Infinite games and effective descriptive set theory, Proc. of London Conf. on Analytic Sets, 1978.
  • [Ko1] G. N. Kobzev, btt-reducibility, Algebra and Logic 12 (1973), 107-115. MR 401447
  • [Ko2] G. N. Kobzev, On btt-reducibility. II, Algebra and Logic 12 (1973), 242-248. MR 401447
  • [Ko3] G. N. Kobzev, On r-separable sets (preprint).
  • G. N. Kobzev, tt-degrees of recursively enumerable Turing degrees, Mat. Sb. 106(148) (1978), no. 4, 507–514 (Russian). MR 507813
  • G. N. Kobzev, The semilattice of tt-degrees, Sakharth. SSR Mecn. Akad. Moambe 90 (1978), no. 2, 281–283 (Russian, with English and Georgian summaries). MR 514301
  • [Ko6] G. N. Kobzev, Recursively enumerable bw-degrees, Math. Notes Acad. Sci. USSR 21 (1977), 473-477. MR 465827
  • G. L. Kurdjumov, An algorithm-theoretic method for the study of homogeneous random media, Dokl. Akad. Nauk SSSR 238 (1978), no. 5, 1047–1050 (Russian). MR 483738
  • [La1] A. H. Lachlan, A note on universal sets, J. Symbolic Logic 31 (1966), 573-574. MR 211857
  • [La2] A. H. Lachlan, Initial segments of one-one degrees, Pacific J. Math. 29 (1969), 351-366. MR 260591
  • [La3] A. H. Lachlan, Initial segments of many-one degrees, Canad J. Math. 22 (1970), 75-85. MR 256875
  • [La4] A. H. Lachlan, Solution to a problem of Spector, Canad J. Math. 23 (1971), 247-256. MR 317911
  • [La5] A. H. Lachlan, Recursively enumerable many-one degrees, Algebra and Logic 11 (1972), 186-202. MR 309721
  • [La6] A. H. Lachlan, Two theorems on many-one degrees of recursively enumerable sets, Algebra and Logic 11 (1972), 127-132. MR 309720
  • [La7] A. H. Lachlan, wtt-complete sets are not necessarily tt-complete, Proc. Amer. Math. Soc. 48 (1975), 429-434. MR 357087
  • [La8] A. H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 8 (1975), 307-365. MR 409150
  • [LL] A. H. Lachlan and R. Lebeuf, Countable initial segments of the degrees of unsolvability, J. Symbolic Logic 41 (1976), 289-300. MR 403937
  • [Lad] R. E. Ladner, On the structure of polynomial time reducibilities, J. Assoc. Comput. Mach. 22 (1975), 155-171. MR 464698
  • [LS] R. E. Ladner and L. P. Sasso, The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), 429-448. MR 379157
  • [Le] M. Lerman, Turing degrees and many-one degrees of maximal sets, J. Symbolic Logic 35 (1970), 29-40. MR 278948
  • [Ma1] S. S. Marchenkov, The existence of recursively enumerable minimal truth-table degrees, Algebra and Logic 14 (1975), 257-261. MR 409151
  • [Ma2] S. S. Marchenkov, On the congruence of the upper semilattices of recursively enumerable m-powers and tabular powers, Math. Notes Acad. Sci. USSR 20 (1976), 567-570.
  • [Ma3] S. S. Marchenkov, Tabular powers of maximal sets, Math. Notes Acad. Sci. USSR 20 (1976), 766-770.
  • [Ma4] S. S. Marchenkov, One class of partial sets, Math. Notes Acad. Sci. USSR 20 (1976), 823-825.
  • [Mt1] D. A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), 363-371. MR 403976
  • [Mt2] D. A. Martin, Descriptive set theory, Handbook of Math. Logic, (Barwise (ed.)), North-Holland, Amsterdam, 1977, pp. 783-815.
  • [MPE] D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205-209. MR 280374
  • G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289–320. MR 556895, https://doi.org/10.1016/0003-4843(79)90011-1
  • [Mi] D. P. Miller, Ph. D. dissertation, University of Chicago, 1981.
  • [MM] W. Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlag Math. 14 (1968), 159-166. MR 228341
  • [McL] T. G. McLaughlin, A theorem on intermediate reducibilities, Proc. Amer. Math. Soc. 19 (1968), 87-90. MR 219420
  • Anil Nerode and Richard A. Shore, Second order logic and first order theories of reducibility orderings, The Kleene Symposium (Proc. Sympos., Univ. Wisconsin, Madison, Wis., 1978), Stud. Logic Foundations Math., vol. 101, North-Holland, Amsterdam-New York, 1980, pp. 181–200. MR 591882
  • [O] P. G. Odifreddi, Classical recursion theory (to appear).
  • [Po] E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284-316. MR 10514
  • [PE] M. B. Pour-El, Effectively extensible theories, J. Symbolic Logic 33 (1968), 56-68. MR 234834
  • [Ro] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 224462
  • [Ru] J. M. Rubin, Ph.D. dissertation, Univ. Calif., Berkeley, 1981.
  • [Sh] J. R. Shoenfield, Undecidable and creative theories, Fund. Math. 49 (1961), 171-179. MR 130177
  • Robert I. Soare, Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149–1181. MR 508451, https://doi.org/10.1090/S0002-9904-1978-14552-2
  • [So2] R. I. Soare, Constructions in the recursively enumerable degrees, CIME Summer School, Bressanone (Italy), 1979 (to appear).
  • [S1] V. D. Solove'v, Q-reducibility and hyperhypersimple sets, Prob. Meth. and Cybern. 10-11 (1974), 121-128. (Russian) MR 476454
  • [V] V. V. V'yugin, Segments of recursively enumerable m-degrees, Algebra and Logic 13 (1974), 361-373. MR 401449
  • [Y1] C. E. M. Yates, Three theorems on the degree of recursively enumerable sets, Duke Math. J. 32 (1965), 461-468. MR 180486
  • [Y2] C. E. M. Yates, On the degrees of index sets, Trans. Amer. Math. Soc. 121 (1966), 309-328. MR 184855
  • [Y3] C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249-266. MR 241295
  • [Yo] P. R. Young, Linear orderings under one-one reducibility, J. Symbolic Logic 31 (1966), 70-85. MR 231720

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1980): 03D30, 03D25

Retrieve articles in all journals with MSC (1980): 03D30, 03D25


Additional Information

DOI: https://doi.org/10.1090/S0273-0979-1981-14863-1

American Mathematical Society