Definability of linear orders over negative equivalences (Q321260)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Definability of linear orders over negative equivalences
scientific article

    Statements

    Definability of linear orders over negative equivalences (English)
    0 references
    0 references
    0 references
    13 October 2016
    0 references
    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.
    0 references
    0 references
    linear order
    0 references
    positive and negative presentation
    0 references
    effectively limit point
    0 references
    computable automorphism
    0 references

    Identifiers