On a Computable Presentation of Low Linear Orderings

Аннотация

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.