A note on Rogers semilattices of families of two embedded sets in the Ershov hierarchy
57 31
Abstract
We show that for every ordinal notation a of a successor ordinal > 1, there is a −1 a family A = {A,B} with A ⊂ B such that the Rogers semilattice of A has exactly one element. This extends a result of Badaev and Talasbaeva, proved for the case in which a is the ordinal notation of 2.References
[1] M.M. Arslanov. Ershov hierarchy. Kazan, 2007. In Russian.
[2] S.A. Badaev and Zh.T. Talasbaeva. Computable numberings in the hierarchy of Ershov. To appear.
[3] Yu. L. Ershov. A hierarchy of sets, I. // Algebra and Logic, 7:47–73, 1968.
[4] Yu. L. Ershov. A hierarchy of sets, II. // Algebra and Logic, 7:15–47, 1968.
[5] Yu. L. Ershov. A hierarchy of sets, III. // Algebra and Logic, 9:34–51, 1970.
[6] Yu. L. Ershov. Theory of Numberings. Nauka, Moscow, 1977. In Russian.
[7] S. Goncharov and A. Sorbi. Generalized computable numerations and non-trivial Rogers semilattices. // Algebra and Logic, 36(6):359–369, 1997.
[8] S. Ospichev. Computable family of −1 a -sets without Friedberg numberings. // 6th
Conference on Computability in Eueope, CiE 2010, 6th Conference on Computability in Eueope,
CiE 2010. Ponta Delgada, Azores, pages 311–315, 2010.
[9] H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.
[2] S.A. Badaev and Zh.T. Talasbaeva. Computable numberings in the hierarchy of Ershov. To appear.
[3] Yu. L. Ershov. A hierarchy of sets, I. // Algebra and Logic, 7:47–73, 1968.
[4] Yu. L. Ershov. A hierarchy of sets, II. // Algebra and Logic, 7:15–47, 1968.
[5] Yu. L. Ershov. A hierarchy of sets, III. // Algebra and Logic, 9:34–51, 1970.
[6] Yu. L. Ershov. Theory of Numberings. Nauka, Moscow, 1977. In Russian.
[7] S. Goncharov and A. Sorbi. Generalized computable numerations and non-trivial Rogers semilattices. // Algebra and Logic, 36(6):359–369, 1997.
[8] S. Ospichev. Computable family of −1 a -sets without Friedberg numberings. // 6th
Conference on Computability in Eueope, CiE 2010, 6th Conference on Computability in Eueope,
CiE 2010. Ponta Delgada, Azores, pages 311–315, 2010.
[9] H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.
Downloads
How to Cite
Manat, M., & Sorbi, A. (2011). A note on Rogers semilattices of families of two embedded sets in the Ershov hierarchy. Journal of Mathematics, Mechanics and Computer Science, 68(1), 4–13. Retrieved from https://bm.kaznu.kz/index.php/kaznu/article/view/167
Issue
Section
Geometry and mathematical logic
