Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-16T23:15:25.526Z Has data issue: false hasContentIssue false
  • English
  • Français

Embedding lattices into the wtt-degrees below 0′

Published online by Cambridge University Press:  12 March 2014

Rod Downey  and
Christine Haught
Rod Downey
Affiliation:
Mathematics Department, Victoria University of Wellington, Wellington, New Zealand, E-mail: [email protected]
Christine Haught
Affiliation:
Department of Mathematical Sciences, Loyola University Chicago, Chicago, Illinois 60626, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

A reducibility ≤p is a procedure whereby a set A can be computed from a set B. The most general and most extensively studied reducibility is Turing reducibility (≤T). However, when one analyzes effectiveness considerations in classical mathematics, one often discovers that the relevant reducibilities are stronger (i.e., more restrictive) than ≤T. To illustrate, in combinatorial group theory we find that the word problem is many-one reducible to the conjugacy problem, and that word problems occur in each r.e. truth table (tt-) degree (see, for example, Miller [17]).

In the present paper we are concerned with another strong reducibility: weak truth table (wtt-) reducibility. Here the reader should recall that A ≤wtt, β means that there is a procedure Φ and a recursive function φ such that Φ(β) = A and for all x, the u(Φ(β; X)) < φ (x). That is, the amount of information used in the computation is bounded by φ. The critical difference between truth table and weak truth table reducibilities is that for tt we will at once be “given the whole table.” Thus if Δ is a tt-procedure and δ is its use, then for all x and all strings σ of length δ(x) we can figure out Δ(σ; x). On the other hand if Δ is merely a wtt-procedure it may be that for some string σ, Δ(σ; x)↓, whilst for another string μ of the same length it may be that Δ{μ; x) ↑. We remark that wtt-reducibility arises very naturally both in effective algebra and in the structure of the r.e. T-degrees R. The reader should see, for instance, Downey and Remmel [3], where it is shown that the complexity of r.e. bases of an r.e. vector space V is characterised precisely by the wtt-degrees below V, and also Ladner and Sasso [14] or Downey [1], where the wtt-degrees are used to investigate cupping and capping in R.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 4 , December 1994 , pp. 1360 - 1382
Copyright
Copyright © Association for Symbolic Logic 1994

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]Downey, R. G., degrees and transfer theorems, Illinois Journal of Mathematics, vol. 31 (1987), pp. 419–427.CrossRefGoogle Scholar
[2]Downey, R. G., D.r.e. degrees and the nondiamond theorem, Bulletin of the London Mathematical Society, vol. 21 (1989), pp. 43–50.CrossRefGoogle Scholar
[3]Downey, R. G. and Remmel, J. B., Classification of degree classes associated with r.e. suhspaees, Annals Pure and Applied Logic, vol. 42 (1989), pp. 105–125.CrossRefGoogle Scholar
[4]Epstein, R. L., Haas, R., and Kramer, R., Hierarchies of sets and degrees below 0′, Logic year 1979–80, (Lerman, M., Schmerl, J., and Soare, R. I., eds.), Lecture Notes in Mathematics, vol. 859, Springer-Verlag, Berlin, 1981, pp. 32–48.CrossRefGoogle Scholar
[5]Ershov, Y. L., The hierarchy of , sets, Proceedings of the Fourth International Congress of Logic, Methodology and Philosophy of Science, North-Holland, Amsterdam, 1973, pp. 69–76.Google Scholar
[6]Fejer, P. and Shore, R., Embeddings and extensions in the r.e. tt- and wtt-degrees, Recursion theory week, Proceedings Oberwolfach, 1984, Lecture Notes in Mathematics, vol. 1141, Springer-Verlag, New York, 1985, pp. 121–140.Google Scholar
[7]Fejer, P. and Shore, R., A direct construction of a minimal recursively enumerable truth table degree, Recursion theory week, Proceedings Oberwolfach, 1989, Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, New York, 1990, pp. 187–204.Google Scholar
[8]Haught, C. A., Turing and truth table degrees of generic and recursively enumerable sets, Ph.D. Thesis, Cornell University, Ithaca, New York, 1985.Google Scholar
[9]Haught, C. A., Lattice embeddings in the r.e. tt-degrees, Transactions of the American Mathematical Society, vol. 301 (1987), pp. 515–535.CrossRefGoogle Scholar
[10]Haught, C. A. and Shore, R. A., Undecidability and initial segments of the (r.e.) tt-degrees, this Journal, vol. 55 (1990), pp. 987–1006.Google Scholar
[11]Haught, C. A. and Shore, R. A., Undecidability and initial segments of the wtt-degrees below 0′, Recursion theory week, Proceedings Oberwolfach, 1989, Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, New York, 1990, pp. 223–244.Google Scholar
[12]Jockusch, C. G. and Mohrherr, J., Embedding the diamond lattice in the recursively enumerable truth table degrees, Proceedings of the American Mathematical Society, vol. 94 (1985), pp. 123–128.CrossRefGoogle Scholar
[13]Kobzev, G. N., On tt-degrees of recursively enumerable Turing degrees, Matematischeskiĭ Sbornik (Novaya Seriya), vol. 106 (1978), pp. 507–514; English translation, Mathematics of the USSR—Sbornik, vol. 35 (1979), pp. 173–180.Google Scholar
[14]Ladner, R. and Sasso, P., The weak truth table degrees of recursively enumerable sets, Annals of Mathematical Logic, vol. 8 (1975), pp. 429–448.CrossRefGoogle Scholar
[15]Lerman, M., Degrees of unsolvability, Springer-Verlag, New York, 1983.CrossRefGoogle Scholar
[16]Marchenkov, S. S., The existence of recursively enumerable truth table degrees, Algebra and Logic, vol. 14 (1975), pp. 257–261.CrossRefGoogle Scholar
[17]Miller, C. F., Decision problems for groups—survey and reflections, Algorithms and classification in combinatorial group theory (Baumslag, G. and Miller, C. F. III, editors), Mathematical Sciences Research Institute Publications, vol. 23. Springer-Verlag, Berlin, 1992, pp. 1–59.CrossRefGoogle Scholar
[18]Odifreddi, P., Strong reducibilities, Bulletin (New Series) of the American Mathematical Society, vol. 4 (1981), pp. 37–86.CrossRefGoogle Scholar
[19]Odifreddi, P., Classical recursion theory, North-Holland, New York, 1989.Google Scholar
[20]Pudlák, P. and Tůma, J., Every finite lattice can be embedded into a finite partition lattice, Algebra Universalis, vol. 10 (1980), pp. 74–95.CrossRefGoogle Scholar
[21]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, New York, 1987.CrossRefGoogle Scholar