Definability of Linear Orders over Negative Equivalences

Abstract

We study linear orders definable over negative and positive equivalences and their computable automorphisms. Special attention is paid to equivalences like η(α) = α²∪id_ω, α ⊆ ω. In particular, we describe orders that have negative presentations over such equivalences for co-enumerable sets α. Presentable and nonpresentable order types are exemplified for equivalences with various extra properties. We also give examples of negative orders with computable automorphisms whose inverses are not computable.