Definability of linear orders over negative equivalences (Q321260)

Let \(\eta\) be an equivalence on \(\omega\). A nonstrict linear order \(\langle L,\leq\rangle\) is negatively (positively) definable over \(\eta\) iff there exists a numbering \(\nu:\omega\to L\) whose numeration equivalence is \(\eta\) and such that the induced order \(\preceq\) on \(\omega/\eta\) is co-enumerable (enumerable). In this case, the equivalence \(\eta\) is also negative, i.e, co-enumerable (positive, i.e., enumerable). Definabilies of linear orders over equivalences of some special kinds are studied. For \(\alpha\subseteq\omega\), let \(\eta(\alpha)=\alpha^2\cup\text{id}_{\omega}\). It is proved that a discrete linear order is (negatively or positively) definable over \(\eta(\alpha)\) iff \(\alpha\) is decidable. If \(\alpha\) is co-enumerable and undecidable, a linear order \(\leq\) is negatively definable over \(\eta(\alpha)\) iff \(\leq\) is constructivizable and contains at least one limit point. If \(\alpha\) is enumerable and undecidable, the order types \(\omega+1\) and \(1+\omega^*\) are not positively definable over \(\eta(\alpha)\) if \(\bar\alpha\) is not immune and positively definable if \(\bar\alpha\) is regressive. Let \(\alpha=\{a_0<a_1<a_2<\ldots\}\) be an infinite subset of \(\omega\) and \(a_0=0\). Then, \(\eta^*(\alpha)\) is an equivalence with classes \([a_i,a_{a+1})=\{x\mid a_i\leq x<a_{i+1}\}\). If \(\alpha\) is enumerable then \(\omega\), \(\omega^*\), and \(\omega^*+\omega\) are negatively definable over \(\eta^*(\alpha)\). If \(\alpha\) is co-enumerable then \(\omega\) and \(\omega^*\) are positively definable over \(\eta^*(\alpha)\). If \(\alpha\) is co-enumerable and not immune then \(\omega^*+\omega\) is positively definable over \(\eta^*(\alpha)\). If \(\alpha\) is cohesive then \(\omega^*+\omega\) is not positively definable over \(\eta^*(\alpha)\). It is proved that each limit point of a negatively definable linear order is effectively limit. There exists a positively definable linear order isomorphic to the ordering of rational numbers all of whose elements are not effectively limit. Computable automorphisms of the negatively definable linear orders are studied. In particular, it is proved that there exists a negatively definable order of type \(\omega\times(\omega^*+\omega)\) with intinitely many computable automorphisms such that only the trivial one is computably reversible.