Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-29T18:05:29.880Z Has data issue: false hasContentIssue false
  • English
  • Français

Some remarks on the algebraic structure of the Medvedev Lattice

Published online by Cambridge University Press:  12 March 2014

Andrea Sorbi
Andrea Sorbi*
Affiliation:
Dipartimento di Matematica, Università di Siena, 53100 Siena, Italy
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper investigates the algebraic structure of the Medvedev lattice . We prove that is not a Heyting algebra. We point out some relations between and the Dyment lattice and the Mučnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 55 , Issue 2 , June 1990 , pp. 831 - 853
Copyright
Copyright © Association for Symbolic Logic 1990

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

[BD]Balbes, R. and Dwinger, P., Distributive lattices, University of Missouri Press, Columbia, Missouri, 1974.Google Scholar
[CO]Cooper, S. B., Partial degrees and the density problem, this Journal, vol. 47 (1982), pp. 854–859.Google Scholar
[DT]de Jongh, D. H. J. and Troelstra, A. S., On the connection of partially ordered sets with some pseudo-Boolean algebras, Indigationes Mathematicae, vol. 28 (1966), pp. 317–329.CrossRefGoogle Scholar
[DY1]Dyment, E. Z., Certain properties of the Medvedev lattice, Matematičeskiĭ Sbornik, vol. 101 (143) (1976), pp. 360–379; English translation, Mathematics of the USSR Sbornik, vol. 30 (1976), pp. 321–340.Google Scholar
[DY2]Dyment, E. Z., Exact bounds of denumerable collections of degrees of difficulty, Matematičeskie Zametki, vol. 28 (1980), pp. 899–910; English translation, Mathematical Notes, vol. 28 (1980), pp. 904–909.Google Scholar
[JP]Jockusch, C. G. Jr., and Posner, D., Automorphism bases for degrees of unsolvability, Israel Journal of Mathematics, vol. 40 (1981), pp. 150–164.CrossRefGoogle Scholar
[LE]Lerman, M., Degrees of unsolvability, Springer-Verlag, Berlin, 1983.CrossRefGoogle Scholar
[MA]Magari, R., Modal diagonalizable algebras, Bollettino dell'Unione Matematica Italiana B, ser. 5, vol. 15 (1978), pp. 303–320.Google Scholar
[ML]Lane, S. Mac, Categories for the working mathematician, Springer-Verlag, Berlin, 1971.CrossRefGoogle Scholar
[ME]Medvedev, Ju. T., Degrees of difficulty of the mass problems, Doklady Akademii Nauk SSSR, vol. 104 (1955), pp. 501–504. (Russian)Google Scholar
[MU]Mučnik, A. A., On strong and weak reducibility of algorithmic problems, Sibirskiĭ Matematičeskiĭ Žurnal, vol. 4 (1963), pp. 1328–1341. (Russian)Google Scholar
[PL]Platek, R. A., A note on the cardinality of the Medvedev lattice, Proceedings of the American Mathematical Society, vol. 25 (1970), p. 917.Google Scholar
[RO]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[RZ]Rozinas, M., The semilattice of e-degrees, Recursive functions (Poljakov, E. A., editor), Ivanovskiĭ Gosudarstvennyĭ Universitet, Ivanovo, 1978, pp. 71–84. (Russian) MR 82i:03057.Google Scholar
[SA]Sambin, G., An effective fixed point theorem in intuitionistic diagonalizable algebras, Studia Logica, vol. 35 (1976), pp. 345–361.CrossRefGoogle Scholar
[SO]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[SR1]Sorbi, A., On some filters and ideals of the Medvedev lattice (to appear).Google Scholar
[SR2]Sorbi, A., Embedding Brouwer algebras in the Medvedev lattice (to appear).Google Scholar
[SR3]Sorbi, A., The fine structure of the Medvedev lattice and the partial degrees, Ph.D. thesis, Graduate Center, City University of New York, New York, 1987.Google Scholar
[UR]Ursini, A., Intuitionistic diagonalizable algebras, Algebra Universalis, vol. 9 (1979), pp. 229–237.CrossRefGoogle Scholar