Abstract
We investigate differences in isomorphism types for Rogers semilattices of computable numberings of families of sets lying in different levels of the arithmetical hierarchy.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. S. Goncharov and A. Sorbi, “Generalized computable numerations and nontrivial Rogers semilattices,” Algebra Logika, 36, No. 6, 621–641 (1997).
S. A. Badaev, S. S. Goncharov, and A. Sorbi, “Isomorphism types and theories of Rogers semilattices of arithmetical numberings,” in Computability and Models, S. B. Cooper and S. S. Goncharov (eds.), Kluwer Academic/Plenum Publishers, New York (2003), pp. 79–91.
S. A. Badaev, S. S. Goncharov, and A. Sorbi, “Elementary properties of Rogers semilattices of arithmetical numberings,” in Proc. 7th and 8th Asian Logic Conf., R. Downey, D. Ding, S. H. Tung, etc. (eds.), World Scientific, Singapore (2003), pp. 1–10.
S. A. Badaev, S. S. Goncharov, and A. Sorbi, “Elementary theories for Rogers semilattices,” Algebra Logika, 44, No. 3, 261–268 (2005).
A. I. Mal’tsev, Algorithms and Recursive Functions [in Russian], Nauka, Moscow (1965).
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
R. I. Soare, Recursively Enumerable Sets and Degrees, A Study of Computable Functions and Computably Generated Sets, Springer, Berlin (1987).
Yu. L. Ershov, Theory of Numerations [in Russian], Nauka, Moscow (1977).
S. S. Goncharov, Countable Boolean Algebras and Decidability, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1996).
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.
S. A. Badaev, S. S. Goncharov, S. Yu. Podzorov, and A. Sorbi, “Algebraic properties of Rogers semilattices of arithmetical numberings,” in Computability and Models, S. B. Cooper and S. S. Goncharov (eds.), Kluwer Academic/Plenum Publishers, New York (2003), pp. 45–77.
V. D. Dzgoev, “Constructive enumerations of Boolean lattices,” Algebra Logika, 27, No. 6, 641–648 (1988).
L. Feiner, “Hierarchies of Boolean algebras,” J. Symb. Log., 35, No. 3, 365–374 (1970).
A. H. Lachlan, “On the lattice of recursively enumerable sets,” Trans. Am. Math. Soc., 130, No. 1, 1–37 (1968).
Author information
Authors and Affiliations
Additional information
Supported by RFBR grant No. 05-01-00819 and by INTAS grant No. 00-499.
Supported by NSFC grant No. 60310213.
__________
Translated from Algebra i Logika, Vol. 45, No. 6, pp. 637–654, November–December, 2006.
Rights and permissions
About this article
Cite this article
Badaev, S.A., Goncharov, S.S. & Sorbi, A. Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy. Algebr Logic 45, 361–370 (2006). https://doi.org/10.1007/s10469-006-0034-3
Received:
Issue Date:
DOI: https://doi.org/10.1007/s10469-006-0034-3