On a Computable Presentation of Low Linear Orderings
A. N. Frolov · Lobachevskii Journal of Mathematics · 2018
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 L implies 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.