On a Computable Presentation of Low Linear Orderings
- Authors: Frolov A.N.1
-
Affiliations:
- Kazan (Volga Region) Federal University
- Issue: Vol 39, No 9 (2018)
- Pages: 1453-1459
- Section: Selected Articles from the Journal Uchenye Zapiski Kazanskogo Universiteta, Seriya Fiziko-Matematicheskie Nauki
- URL: https://journals.rcsi.science/1995-0802/article/view/203672
- DOI: https://doi.org/10.1134/S1995080218090020
- ID: 203672
Cite item
Abstract
In 1998, R. Downey in his review paper outlined a research agenda for the study and description of sufficient conditions for computable representability of linear orderings, namely, the problem of describing order properties P such that, for any low linear ordering Limplies that, the feasibility of the condition P(L) implies that L has a computable presentation. This paper is a part of the research program initiated by R. Downey. It is shown in the paper that any low linear ordering whose factor order (in other words, condensation) is η (the order type of naturally ordered natural numbers) has a computable presentation via a 0—computable isomorphism if this ordering does not contain a strongly η-like infinite interval. A countable linear ordering is said to be strongly η-like if there exists some natural number k such that each maximal block of the ordering is of cardinality no more than k. It is also proved that the above result does not hold for a 0—computable isomorphism instead of the 0—computable one. Namely, we construct a low linear ordering L with condensation η and without strongly η-like infinite interval so that L has no computable presentation via a 0— computable isomorphism.
About the authors
A. N. Frolov
Kazan (Volga Region) Federal University
Author for correspondence.
Email: andrey.frolov@kpfu.ru
Russian Federation, Kazan, 420008