Abstract
We deal with some upper semilattices of m-degrees and of numberings of finite families. It is proved that the semilattice of all c.e. m-degrees, from which the greatest element is removed, is isomorphic to the semilattice of simple m-degrees, the semilattice of hypersimple m-degrees, and the semilattice of Σ 02 -computable numberings of a finite family of Σ 02 -sets, which contains more than one element and does not contain elements that are comparable w.r.t. inclusion.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. H. Lachlan, “Recursively enumerable many-one degrees,” Algebra Logika, 11, No. 3, 326–358 (1972).
S. Yu. Podzorov, “Local structure of Rogers semilattices of Σ 0n -computable numberings,” Algebra Logika, 44, No. 2, 148–172 (2005).
S. Yu. Podzorov, “Numbered distributive semilattices,” to appear in Mat. Tr.
S. D. Denisov, “The structure of an upper semilattice of recursively enumerable m-degrees and related problems. 1,” Algebra Logika, 17, No. 6, 643–683 (1978).
Yu. L. Ershov, “Rogers semilattices of finite partially ordered sets,” Algebra Logika, 45, No. 1, 44–84 (2006).
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
G. Grätzer, General Lattice Theory, Academie-Verlag, Berlin (1978).
Yu. L. Ershov, Numeration Theory [in Russian], Nauka, Moscow (1977).
S. A. Badaev, S. S. Goncharov, and A. Sorbi, “Completeness and universality of arithmetical numberings,” in Computability and Models, S. B. Cooper and S. S. Goncharov (eds.), Kluwer Academic/Plenum Publishers, New York (2003), pp. 11–44.
Yu. L. Ershov, “Hypersimple m-degrees,” Algebra Logika, 8, No. 5, 523–552 (1969).
Author information
Authors and Affiliations
Additional information
Supported by the Grant Council (under RF President) for Young Russian Scientists via project MK-1820.2005.1.
__________
Translated from Algebra i Logika, Vol. 46, No. 3, pp. 299–345, May–June, 2007.
Rights and permissions
About this article
Cite this article
Podzorov, S.Y. The universal Lachlan semilattice without the greatest element. Algebr Logic 46, 163–187 (2007). https://doi.org/10.1007/s10469-007-0016-0
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s10469-007-0016-0