Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-30T21:45:35.538Z Has data issue: false hasContentIssue false
  • English
  • Français

On the embedding of α-recursive presentable lattices into the α-recursive degrees below 0′

Published online by Cambridge University Press:  12 March 2014

Dong Ping Yang
Dong Ping Yang*
Affiliation:
Cornell University, Ithaca, New York 14853
*
Institute of Computing Technology, Academia Sinica, Beijing, China
Get access Rights & Permissions [Opens in a new window]

Extract

An important problem, widely treated in the analysis of the structure of degree orderings, is that of partial order and lattice embeddings. Thus for example we have the results on embeddings of all countable partial orderings in the Turing degrees by Kleene and Post [3] and in the r.e. T-degrees by Sacks [10]. For lattice embeddings the work on T-degrees culminated in the characterization of countable initial segments by Lachlan and Lebeuf [4]. For the r.e. T-degrees there has been a continuing line of progress on this question. (See Soare [20] and Lerman, Shore, and Soare [8].) Similar projects have been undertaken for the T-degrees below 0′ (Kleene and Post [3], Lerman [6]) as well as for most other degree orderings. The results have been used not only to analyse individual orderings but also to distinguish between them (Shore [16], [19], [17]).

The situation for α-jecursive theory, the study of recursion in (admissible) ordinals, is similar to, though not as well developed as, that for Turing degrees. All afinite partial orderings have been embedded even in the α-r.e. degrees (see Lerman [5]). Lattice embedding results are somewhat fragmentary however. In terms of initial segments even the question of the existence of a minimal α-degree has not been settled for all admissibles. (See Shore [12] for a proof for Σ2-admissible ordinals, however.) Results on more complicated lattices have only reached to the finite distributive ones for Σ3-admissible ordinals (see Dorer [1]).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 49 , Issue 2 , June 1984 , pp. 488 - 502
Copyright
Copyright © Association for Symbolic Logic 1984

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]Dorer, D. J., Initial segments in ordinal recursion theory, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, 08, 1979.Google Scholar
[2]Jockusch, C. G. and Soare, R. I., Minimal covers and arithmetical sets, Proceedings of the American Mathematical Society, vol. 25 (1970), pp. 856–859.CrossRefGoogle Scholar
[3]Kleene, S. C. and Post, E. L., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, ser. 2, vol. 59 (1954), pp. 379–407.CrossRefGoogle Scholar
[4]Lachlan, A. H. and Lebeuf, R., Countable initial segments of the degrees of unsolvability, this Journal, vol. 41 (1976), pp. 289–300.Google Scholar
[5]Lerman, M., On suborderings of the α-recursively enumerable α-degrees. Annals of Mathematical Logic, vol. 4 (1972), pp. 369–392.CrossRefGoogle Scholar
[6]Lerman, M., Degrees of unsolvability, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
[7]Lerman, M. and Sacks, G. E., Some minimal pairs of α-recursively enumerable degrees, Annals of Mathematical Logic, vol. 4 (1972), pp. 415–442.CrossRefGoogle Scholar
[8]Lerman, M., Shore, R. A. and Soare, R. I., The elementary theory of the recursively enumerable degrees is not ℵ0-categorical (to appear).Google Scholar
[9]Odell, D., Ph.D. Thesis in recursion theory, Cornell University, Ithaca, N.Y., 1983.Google Scholar
[10]Sacks, G. E., Degrees of unsolvability, rev. ed., Annals of Mathematics Studies, No. 55, Princeton University Press, Princeton, New Jersey, 1966.Google Scholar
[11]Sacks, G. E. and Simpson, S. G., The α-finite injury method, Annals of Mathematical Logic, vol. 4 (1972), pp. 343–367.CrossRefGoogle Scholar
[12]Shore, R. A., Minimal α-degrees. Annals of Mathematical Logic, vol. 4 (1972), pp. 393–414.CrossRefGoogle Scholar
[13]Shore, R. A., Splitting an α-recursively enumerable set, Transactions of the American Mathematical Society, vol. 204 (1975), pp. 65–78.Google Scholar
[14]Shore, R. A., The r.e. α-degrees are dense, Annals of Mathematical Logic, vol. 9 (1976), pp. 123–155.CrossRefGoogle Scholar
[15]Shore, R. A., Some more minimal pairs of α-recursively enumerable degrees, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 24 (1978), pp. 409–418.CrossRefGoogle Scholar
[16]Shore, R. A., The theory of the degrees below 0′, The Journal of the London Mathematical Society, vol. 24 (1981), pp. 1–14.CrossRefGoogle Scholar
[17]Shore, R. A., The degrees of unsolvability: Global results, Logic Year 1979–80 (edited by Lerman, M., Schmerl, J. H. and Soare, R. I.), Lecture Notes in Mathematics, vol. 859, Springer-Verlag, Berlin, 1981, pp. 283–301.CrossRefGoogle Scholar
[18]Shore, R. A., Finitely generated coding and the degrees r.e. in a degree d, Proceedings of the American Mathematical Society, vol. 84 (1982), pp. 256–263.Google Scholar
[19]Shore, R. A., The Turing and truth-table degrees are not elementary equivalent (to appear).Google Scholar
[20]Soare, R. I., Recursively enumerable sets and degrees, Bulletin of the American Mathematical Society, vol. 84 (1978), pp. 1149–1181.CrossRefGoogle Scholar