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

Initial segments of the lattice of ideals of r.e. degrees

Published online by Cambridge University Press:  12 March 2014

Frank P. Weber
Frank P. Weber*
Affiliation:
134 Zhong Shaw Road, Hsuei-Chia Chen, Tainan Shien, Taiwan ROC
Get access Rights & Permissions [Opens in a new window]

Extract

Embeddings into initial segments of (the lattice of ideals of r.e. degrees) are relevant for the investigation of decidability of (fragments of) the theory of (with constant-symbols denoting principal ideals). Interest in this investigation stems from open problems concerning decidability of fragments of the theory of R (the usl of r.e. degrees) and embeddings into R. Ambos-Spies and Lerman established comprehensive nonembeddability [AS/LR1] and embeddability [AS/LR2] conditions, but their complementarity is open. (For background on embeddings and decidability consult Lerman [LR1] and Lerman and Shore [LR/SH].) The first systematic investigation of embeddings into is in Calhoun [CL], where the existence of uniform bounds, in the case of embeddings into , on the number of “join traces” arising with nondistributive lattices is shown to remove “obstructions” to lattice-embeddings into R (such as typified in the nonembeddable lattice S8, see [LA/SR], [AS/LR1/). The analysis to follow extends this, by showing that it also removes the “obstruction” to lattice-embeddings into initial segments of R, arising with Lachlan's M5, which embeds into R, but not into every nontrivial initial segment R[0, a], by a result of Downey [DW]. The techniques are Lachlan's [LA], as adapted in Lerman's “pinball machine model” [LR1, LR2], combined with Fejer's “meet-trick” [FJ] as used by Downey [DW] in the proof that every distributive lattice is embeddable into every nontrivial initial segment of r.e. degrees R[0, a], a > 0. We present a sufficient condition, “allowing evasion” [Definition 4.2] for lattice embeddability into every [0, a], a > 0.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 4 , December 1994 , pp. 1326 - 1350
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

[AS/LR1]Ambos-Spies, K. and Lerman, M., Lattice embeddings into the recursively enumerable degrees. I, this Journal, vol. 51 (1986), pp. 257–272.Google Scholar
[AS/LR2]Ambos-Spies, K. and Lerman, M., Lattice embeddings into the recursively enumerable degrees. II, this Journal, vol. 54 (1989), pp. 735–760.Google Scholar
[CL]Calhoun, W. C., The lattice of ideals of recursively enumerable degrees, Ph.D. thesis, University of California, Berkeley, California, 1990.Google Scholar
[DW]Downey, R., Lattice non-embeddings and initial segments of the r.e. degrees, Annals of Pure and Applied Logic, vol. 49 (1990), pp. 97–119.CrossRefGoogle Scholar
[FJ]Fejer, P., The density of nonbranching degrees, Annals of Pure and Applied Logic, vol. 24 (1983), pp. 113–130.CrossRefGoogle Scholar
[LA]Lachlan, A. H., Embedding nondistributive lattices in the recursively enumerable degrees, Conference in mathematical logic, London, 1970 (Hodges, W., editor). Lecture Notes in Mathematics, vol. 255, Springer-Verlag, New York, 1972, pp. 149–177.Google Scholar
[LA/SR]Lachlan, A. H. and Soare, R. I., Not every finite lattice is embeddable in the recursively enumerable degrees, Advances in Mathematics, vol. 37 (1980), pp. 74–82.CrossRefGoogle Scholar
[LR]Lerman, M., Degrees of unsolvability, Perspectives of Mathematical Logic, Springer-Verlag, New York, 1983.CrossRefGoogle Scholar
[LR2]Lerman, M., The embedding problem for the recursively enumerable degrees, [NR/SH], pp. 13–20.Google Scholar
[LR/SH]Lerman, M. and Shore, R. A., Decidability and invariant classes for degree structures, Transactions of the American Mathematical Society, vol. 310 (1988), pp. 669–692.CrossRefGoogle Scholar
[NR/SH]Nerode, A. and Shore, R. A. (editors), Recursion theory, Proceedings of Symposia in Pure Mathematics, American Mathematical Society, Providence, Rhode Island, 1985.CrossRefGoogle Scholar
[SH/SL]Shore, R. A. and Slaman, T., Working below a high recursively enumerable degree, this Journal, vol. 58 (1993), pp. 824–859.Google Scholar
[SR1]Soare, R. I., Tree arguments in recursion theory and the 0″′-priority method, [NR/SH], pp. 53–106.Google Scholar
[SR2]Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, New York, 1986.Google Scholar