Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-23T10:42:18.894Z Has data issue: false hasContentIssue false
  • English
  • Français

On the structures inside truth-table degrees

Published online by Cambridge University Press:  12 March 2014

Frank Stephan
Frank Stephan*
Affiliation:
Universität Heidelberg, Mathematisches Institut, IM Neuenheimer Feld 294, 69120, Heidelberg, GermanyEU, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The following theorems on the structure inside nonrecursive truth-table degrees are established: Dëgtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one degrees? Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and therefore do not contain any objective set. Furthermore, a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of coenumerable semirecursive sets and one of sets, which are neither enumerable nor coenumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integer as for example nineteen, but it is never an even finite number.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 66 , Issue 2 , June 2001 , pp. 731 - 770
Copyright
Copyright © Association for Symbolic Logic 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ambos-Spies, K., Sublattices of the polynomial time degrees, Information and Control, vol. 65 (1985), no. 1, pp. 63–84.CrossRefGoogle Scholar
[2]Ambos-Spies, K., Inhomogeneities in the polynomial time degrees: the degrees of supersparse sets, Information Processing Letters, vol. 22 (1986), pp. 113–117.CrossRefGoogle Scholar
[3]Arslanov, M., On some generalizations of a fixed-point theorem, Soviet Mathematics, vol. 25 (1981), no. 5, pp. 9–16 (in Russian), vol. 25 (1981), no. 5, pp. 1–10 (English translation).Google Scholar
[4]Beigel, R., Gasarch, W., Gill, J., and Owings, J., Terse, superterse and verbose sets, Information and Computation, vol. 103 (1993), pp. 68–85.CrossRefGoogle Scholar
[5]Beigel, R., Gasarch, W., and Owings, J., Nondeterministic bounded query reducibilities, Annals of Pure and Applied Logic, vol. 41 (1989), pp. 107–118.CrossRefGoogle Scholar
[6]Beigel, R., Kummer, M., and Stephan, F., Quantifying the amount of verboseness, Information and Computation, vol. 118 (1995), pp. 73–90.CrossRefGoogle Scholar
[7]Bulitko, V. K., Reducibility by linear Zhegalkin tables, Siberian Mathematical Journal, vol. 21 (1980), pp. 23–31 (in Russian), vol. 21 (1980), pp. 332–339 (English translation).Google Scholar
[8]Cholak, P. and Downey, R., Recursive enumerable m- and tt-degrees. Part III: Realizing all finite distributive lattices, The Journal of the London Mathematical Society, vol. 50 (1994), pp. 440–453.CrossRefGoogle Scholar
[9]Dëgtev, A., Comparison of linear reducibility with other reducibilities of tabular type, Algebra and Logic, vol. 21 (1982), pp. 511–529 (in Russian), vol. 21 (1982), pp. 339–353 (English translation).CrossRefGoogle Scholar
[10]Dëgtev, A., Three theorems on tt-degrees, Algebra and Logic, vol. 17 (1973), no. 3, pp. 270–281 (in Russian), vol. 17 (1978), pp. 187–194 (English translation).Google Scholar
[11]Dëgtev, A., tt- and m-degrees, Algebra and Logic, vol. 12 (1973), pp. 143–161 (in Russian), vol. 12 (1973), pp. 78–89, (English translation).CrossRefGoogle Scholar
[12]Dekker, J. and Myhill, J., Retraceable sets, Canadian Journal of Mathematics, vol. 10 (1958), pp. 357–373.CrossRefGoogle Scholar
[13]Downey, R., Recursively enumerable m- and tt-degrees. Part I: The quantity of m-degrees, this Journal, vol. 54 (1989), pp. 553–567.Google Scholar
[14]Downey, R., Recursively enumerable m- and tt-degrees. Part II: The distribution of singular degrees, Archive for Mathematical Logic, vol. 27 (1988), pp. 135–148.CrossRefGoogle Scholar
[15]Friedberg, R., Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Sciences, vol. 43, 1957, pp. 236–238.CrossRefGoogle ScholarPubMed
[16]Friedberg, R. and Rogers, H., Reducibilities and completeness for sets of integers, Zeitschrift fÜr Mathematische Logik and Grundlagen der Mathematik, vol. 5 (1959), pp. 117–125.CrossRefGoogle Scholar
[17]Harrington, L. and Soare, R., Post's program and incomplete recursive enumerable sets, Proceedings of the National Academy of Science, vol. 88, 1991, pp. 10242–10246.CrossRefGoogle ScholarPubMed
[18]Jockusch, C., Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 420–436.CrossRefGoogle Scholar
[19]Jockusch, C., Relationships between reducibilities, Transactions of the American Mathematical Society, vol. 142 (1969), pp. 229–237.CrossRefGoogle Scholar
[20]Kallibekov, S., On degrees of recursively enumerable sets, Siberian Mathematical Journal, vol. 14 (1973), no. 2, pp. 421–426 (in Russian), vol. 14 (1973), pp. 200–203 (English translation).CrossRefGoogle Scholar
[21]Kobzev, G., On btt-Reducibilities I, Algebra and Logic, vol. 12 (1973), no. 2, pp. 190–204 (in Russian), vol. 12 (1973), pp. 107–115 (English translation).CrossRefGoogle Scholar
[22]Kobzev, G., On btt-Reducibilities II, Algebra and Logic, vol. 12 (1973), no. 4, pp. 433–444 (in Russian), vol. 12 (1973), pp. 242–248 (English translation).CrossRefGoogle Scholar
[23]Kobzev, G., Recursive enumerable bw-degrees, Matematicheskie Zametki, vol. 21 (1977), no. 6, pp. 839–846 (in Russian), vol. 21 (1977), pp. 473–477 (English translation).Google Scholar
[24]Kobzev, G., On Γ-separable sets, Studies in Mathematical Logic and the Theory of Algorithms, (1975), pp. 19–30, (in Russian).Google Scholar
[25]Kummer, M., A proof of Beigel's cardinality conjecture, this Journal, vol. 57 (1992), pp. 677–681.Google Scholar
[26]Kummer, M. and Stephan, F., Recursion theoretic properties of frequency computation and bounded queries, Information and Computation, vol. 120 (1995), pp. 59–77.CrossRefGoogle Scholar
[27]Ladner, R., Lynch, N., and Selman, A., Comparison of polynomial time reducibilities, Theoretical Computer Science, vol. 1 (1975), pp. 103–123.CrossRefGoogle Scholar
[28]Martin, D., Completeness, the recursion theorem and effectively simple sets, Proceedings of the American Mathematical Society, vol. 17, 1966, pp. 838–842.CrossRefGoogle Scholar
[29]McLaughlin, T., On a class of complete simple sets, Canadian Mathematical Bulleting, vol. 8 (1965), pp. 33–37.CrossRefGoogle Scholar
[30]Mehlhorn, K., Polynomial and abstract subrecursive classes, Journal of Computer and System Sciences, vol. 12 (1978), pp. 147–178.CrossRefGoogle Scholar
[31]Merkle, M., A generalized account of resource bounded reducibilities, Ph.D. thesis, UniversitÄt Heidelberg, 1997.Google Scholar
[32]Miller, W. and Martin, D., The degrees of hyperimmune sets, Zeitschrift fÜr Mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 159–16.CrossRefGoogle Scholar
[33]Muchnik, A. A., Negative answer to the problem of reducibility in the theory of algorithms, Doklady Akademii Nauk S.S.S.R., vol. 108 (1956), pp. 194–197.Google Scholar
[34]Nerode, A., General topology and partial recursive functionals, Talks Cornell Summer Institute on Symbolic Logic, Cornell, 1957, pp. 247–257.Google Scholar
[35]Odifreddi, P., Classical Recursion Theory, North-Holland, Amsterdam, 1989.Google Scholar
[36]Post, E., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284–316.CrossRefGoogle Scholar
[37]Robinson, R. W., Interpolation and embedding in the recursive enumerable degrees, Annals of Mathematics, Second Series, vol. 93 (1971), pp. 285–314.CrossRefGoogle Scholar
[38]Robinson, R. W., Jump restricted interpolation in the recursive enumerable degrees, Annals of Mathematics, Second series, vol. 93, 1971, pp. 586–596.CrossRefGoogle Scholar
[39]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[40]Sacks, G. E., Degrees of unsohability, Annals of Mathematics, Studies 55, Princeton University Press, Princeton, New Jersey, 1966.Google Scholar
[41]Shoenfield, J., A theorem on minimal degrees, this Journal, vol. 31 (1966), pp. 539–544.Google Scholar
[42]Sloane, N. J. A., The on-line encyclopedia of integer sequences. Homepage: http://www.research.att.com/~njas/sequences/index.html.Google Scholar
[43]Soare, R., Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets, Springer-Verlag, Heidelberg, 1987.Google Scholar
[44]Spector, C., On degrees of unsolvability, Annals of Mathematics, vol. 64 (1956), pp. 581–592.CrossRefGoogle Scholar
[45]Trakhtenbrot, B. A., Tabular representation of recursive operators, Doklady Akademii Nauk S.S.S.R., vol. 101 (1955), pp. 417–420.Google Scholar
[46]Young, P., On reducibility by recursive functions, Proceedings of the American Mathematical Society, vol. 15, 1964, pp. 889–892.CrossRefGoogle Scholar
[47]Young, P., A theorem on recursively enumerable classes and splinters, Proceedings of the American Mathematical Society, vol. 17, 1966, pp. 1050–1056.CrossRefGoogle Scholar