Geodesic
Lattice properties of Rogers semilattices of compuatble and generalized computable familie
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1927-1936.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the distributivity property and the property of being a lattice of Rogers semilattices of generalized computable families. We prove that the Rogers semilattice of any nontrivial $A$-computable family is not a lattice for every non-computable set $A$. It is also proved that if a set $A$ is non-computable then the Rogers semilattice of any infinite $A$-computable family is not weakly distribuive. Furtermore, we find two infinite computable families with nontrivial distributive and properly weakly distributive nontrivial Rogers semilattices.
Keywords: computable enumeration, generalized computable enumeration, $A$-computable enumeration, Rogers semilattice. 
@article{SEMR_2019_16_a32,
     author = {M. Kh. Faizrahmanov},
     title = {Lattice properties of {Rogers} semilattices of compuatble and generalized computable familie},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1927--1936},
     publisher = {mathdoc},
     volume = {16},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2019_16_a32/}
}
TY  - JOUR
AU  - M. Kh. Faizrahmanov
TI  - Lattice properties of Rogers semilattices of compuatble and generalized computable familie
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2019
SP  - 1927
EP  - 1936
VL  - 16
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2019_16_a32/
LA  - ru
ID  - SEMR_2019_16_a32
ER  - 
%0 Journal Article
%A M. Kh. Faizrahmanov
%T Lattice properties of Rogers semilattices of compuatble and generalized computable familie
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2019
%P 1927-1936
%V 16
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2019_16_a32/
%G ru
%F SEMR_2019_16_a32
M. Kh. Faizrahmanov. Lattice properties of Rogers semilattices of compuatble and generalized computable familie. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 16 (2019), pp. 1927-1936. http://geodesic.mathdoc.fr/item/SEMR_2019_16_a32/

[1] S. S. Goncharov, A. Sorbi, “Generalized computable numerations and nontrivial Rogers semilattices”, Algebra and Logic, 36:6 (1997), 359–369 | DOI | MR | Zbl

[2] S. A. Badaev, S. S. Goncharov, A. Sorbi, “Isomorphism types and theories of Rogers semilattices of arithmetical nuberings”, Computability and models, eds. S. B. Cooper, S. S. Goncharov, Kluwer Academic/Plenum Publishers, New York, 2003, 79–91 | DOI | MR

[3] S. Yu. Podzorov, “Local Structure of Rogers Semilattices of $\Sigma^0_n$-Computable Numberings”, Algebra and Logic, 44:1 (2005), 82–94 | DOI | MR | Zbl

[4] S. A. Badaev, S. S. Goncharov, A. Sorbi, “Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy”, Algebra and Logic, 45:6 (2006), 361–370 | DOI | MR | Zbl

[5] S. Badaev, S. Goncharov, “Computability, numberings”, New computational paradigms. Changing conceptions of what is computable, eds. S. B. Cooper et al., Springer-Verlag, New York, NY, 2008, 19–34 | MR | Zbl

[6] S. S. Goncharov, “Computable numberings of hyperarithmetical sets and complexity of countable models”, Mathematical theory and computational practice, 5th Conf. on computability in Europe, CiE 2009 (Heidelberg, Germany, July 19–24), Univ. Heidelberg, 2009, 13–14

[7] S. A. Badaev, S. S. Goncharov, “Generalized computable universal numberings”, Algebra and Logic, 53:5 (2014), 355–364 | DOI | MR | Zbl

[8] M. Kh. Faizrakhmanov, “Universal generalized computable numberings and hyperimmunity”, Algebra and Logic, 56:4 (2017), 337–347 | DOI | MR | Zbl

[9] M. Kh. Faizrahmanov, “The Rogers semilattices of generalized computable enumerations”, Siberian Math. J., 58:6 (2017), 1104–1110 | DOI | MR | Zbl

[10] S. A. Badaev, A. A. Issakhov, “Some absolute properties of A-computable numberings”, Algebra and Logic, 57:4 (2018), 275–288 | DOI | MR | Zbl

[11] Yu. L. Ershov, Theory of Numberings, Nauka, M., 1977 | MR

[12] Yu. L. Ershov, “Enumeration of families of general recursive functions”, Siberian Math. J., 8:5 (1967), 1015–1025 | DOI | MR | Zbl

[13] V. L. Selivanov, “Two theorems on computable numberings”, Algebra and Logic, 15:4 (1976), 297–306 | DOI | MR | Zbl

[14] C. G. Jockusch, “Relationships between reducibilities”, Trans. Amer. Math. Soc., 142 (1969), 229–237 | DOI | MR | Zbl

[15] P. Odifreddi, Classical recursion theory: The theory of functions and sets of natural numbers, Elsevier, Amsterdam, 1992 | MR | Zbl