Minimal Generalized Computable Numberings and Families of Positive Preorders

Rakymzhankyzy F. Bazhenov N.A. Issakhov A.A. Kalmurzayev B.S.
July 2022 Springer

Algebra and Logic
2022 #61 Issue 3 188 - 206 pp.

We study A-computable numberings for various natural classes of sets. For an arbitrary oracle A≥_T0^′, an example of an A-computable family S is constructed in which each A-computable numbering of S has a minimal cover, and at the same time, S does not satisfy the sufficient conditions for the existence of minimal covers specified in [Sib. Math. J., 43, No. 4, 616-622 (2002)]. It is proved that the family of all positive linear preorders has an A-computable numbering iff A^′≥_T0. We obtain a series of results on minimal A-computable numberings, in particular, Friedberg numberings and positive undecidable numberings.

Text of the article Перейти на текст статьи

Kazakh-British Technical University, Alma-Ata, Kazakhstan
Sobolev Institute of Mathematics, Novosibirsk, Russian Federation
Al-Farabi Kazakh National University, Alma-Ata, Kazakhstan

Kazakh-British Technical University
Sobolev Institute of Mathematics
Al-Farabi Kazakh National University

10 лет помогаем публиковать статьи Международный издатель

Книга Публикация научной статьи Волощук 2026 Book Publication of a scientific article 2026