|
|
Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2017, Volume 159, Book 4, Pages 518–528
(Mi uzku1424)
|
|
|
|
On a computable presentation of low linear orders
A. N. Frolov Kazan Federal University, Kazan, 420008 Russia
Abstract:
R. Downey in the review paper of 1998 stated the research program on studying and description of sufficient conditions of computable representability of linear orders, namely, the problem of description of the order type $P$ such that, for any low linear order $L$, from $P(L)$ it follows that $L$ has a computable presentation.
This paper is a part of the program initiated by R. Downey. We have shown that each low linear order with $\eta$ condensation and no infinite strongly $\eta$-like interval has a computable presentation via a $\mathbf0''$-computable isomorphism. The countable linear order is called $\eta$-like if there exists some natural number $k$ such that each maximal block of the order has power no more than $k$.
We have also proven that the above-discussed result does not hold for $\mathbf0'$-computable isomorphism instead of $\mathbf0''$-computable. Namely, we have constructed a low linear order $L$ with $\eta$ condensation and no infinite strongly $\eta$-like interval such that $L$ is not $\mathbf0'$-computably isomorphic to a computable one.
Keywords:
linear order, computable presentation, low degree, strongly $\eta$-like linear order.
Received: 12.09.2017
Citation:
A. N. Frolov, “On a computable presentation of low linear orders”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 159, no. 4, Kazan University, Kazan, 2017, 518–528
Linking options:
https://www.mathnet.ru/eng/uzku1424 https://www.mathnet.ru/eng/uzku/v159/i4/p518
|
|