Central AsianResearch Index

GENERALIZED NUMBERING FOR LINEAR ORDERS

We study spectre of Turing degrees permitting to construct numbeings for the set of all linear orders isomorphic to the standard order of natural numbers. It is known that the index set of all linear orders isomorphic to the standard order of natural numbers is П 3 -comlete. This mean that this set has no computable numberings. In this work we show that the set of all linear orders isomorphic to the standard order of naturals has O ’’-computable numbering, and has no O ’ -computable numberings. In the Bazhenov, Kalmurzayev and Torebekova’s work they construct universal c.e. linear preorder in the structure under computably reducibility. They use the following fact: there is computable numbering for some subset S 0 of c.e. linear preorders such that any c.e. linear preorder lies in lower cone for some c.e. linear order from S 0 . We show that the similar fact is not hold for the structure of all linear orders isomorphic to the standard order of naturals. Moreover, for this structure there is no O ’ -computable numbering with simiral fact.

Сведения

Опубликовано
2025 · Т. 22, № 2, С. 200-206
Язык
Английский
ISSN
1998-6688 · 2959-8109
Издатель
Kazakh-British Technical University
Аффилиации
Kazakh-British Technical Universityж International Information Technology University
Kazakh-British Technical University
Al-Farabi Kazakh National University