RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2022 Volume 61, Number 3, Pages 280–307 (Mi al2711)

This article is cited in 1 paper

Minimal generalized computable numberings and families of positive preorders

F. Rakymzhankyzya, N. A. Bazhenovb, A. A. Issakhova, B. S. Kalmurzayevca

a Kazakh-British Technical University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
c Al-Farabi Kazakh National University

Abstract: We study $A$-computable numberings for various natural classes of sets. For an arbitrary oracle $A\geq_T \mathbf{0'}$, 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 by S. A. Badaev and S. Yu. Podzorov 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' \geq_T \mathbf{0}''$. We obtain a series of results on minimal $A$-computable numberings, in particular, Friedberg numberings and positive undecidable numberings.

Keywords: $A$-computable numbering, positive linear preorder, Rogers semilattice, Friedberg numbering, positive numbering, minimal cover.

UDC: 510.5

Received: 03.11.2021
Revised: 28.10.2022

DOI: 10.33048/alglog.2022.61.302



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024