GENERALIZED NUMBERING FOR LINEAR ORDERS
A. A. Issakhov, B. S. Kalmurzayev, F. Rakymzhankyzy · Herald of Kazakh-British technical university · 2025
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 S0 of c.e. linear preorders such that any c.e. linear preorder lies in lower cone for some c.e. linear order from S0. 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.