Abstract:
The paper studies Rogers semilattices for families of equivalence relations in the Ershov hierarchy. For an arbitrary notation a of a nonzero computable ordinal, we consider Σ−1a-computable numberings of the family of all Σ−1a equivalence relations. We show that this family has infinitely many pairwise incomparable Friedberg numberings and infinitely many pairwise incomparable positive undecidable numberings. We prove that the family of all c.e. equivalence relations has infinitely many pairwise incomparable minimal nonpositive numberings. Moreover, we show that there are infinitely many principal ideals without minimal numberings.
N. A. Bazhenov was supported by the Ministry of Education and Science of the Republic of Kazakhstan (Grant AP05131579 “Positive Preorders and Computable Reducibility on Them as a Mathematical Model of Databases”). B. S. Kalmurzaev was supported by the Russian Foundation for Basic Research (Grant 17-301-50022 mol_nr).
Citation:
N. A. Bazhenov, B. S. Kalmurzaev, “Rogers semilattices for families of equivalence relations in the Ershov hierarchy”, Sibirsk. Mat. Zh., 60:2 (2019), 290–305; Siberian Math. J., 60:2 (2019), 223–234
\Bibitem{BazKal19}
\by N.~A.~Bazhenov, B.~S.~Kalmurzaev
\paper Rogers semilattices for families of equivalence relations in the Ershov hierarchy
\jour Sibirsk. Mat. Zh.
\yr 2019
\vol 60
\issue 2
\pages 290--305
\mathnet{http://mi.mathnet.ru/smj3076}
\crossref{https://doi.org/10.33048/smzh.2019.60.204}
\elib{https://elibrary.ru/item.asp?id=38692309}
\transl
\jour Siberian Math. J.
\yr 2019
\vol 60
\issue 2
\pages 223--234
\crossref{https://doi.org/10.1134/S0037446619020046}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000465640100004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85064950874}
Linking options:
https://www.mathnet.ru/eng/smj3076
https://www.mathnet.ru/eng/smj/v60/i2/p290
This publication is cited in the following 2 articles:
F. Rakymzhankyzy, N. A. Bazhenov, A. A. Isakhov, B. S. Kalmurzaev, “Minimalnye obobschenno vychislimye numeratsii i semeistva pozitivnykh predporyadkov”, Algebra i logika, 61:3 (2022), 280–307
F. Rakymzhankyzy, N. A. Bazhenov, A. A. Issakhov, B. S. Kalmurzayev, “Minimal Generalized Computable Numberings and Families of Positive Preorders”, Algebra Logic, 61:3 (2022), 188