Initial segments of recursive linear orders
From MaRDI portal
It is proved that any \({\Sigma}^{0}_{2}\)-initial segment of any recursive linear order can be presented recursively. The result narrows the gap in the result of \textit{M. J. S. Raw} [Complexity of automorphisms of recursive linear orders, Ph.D. Thesis, University of Wisconsin-Madison (1995)] on initial segments of recursive linear orders of arithmetical complexity.
Recommendations
- On initial segments of computable linear orders
- Initial segments of computable linear orders with additional computable predicates
- Initial segments of computable linear orders with computable natural relations
- scientific article; zbMATH DE number 749928
- Recursive Linear Orders with Incomplete Successivities
Cited in
(10)- On initial segments of computable linear orders
- Weak and strong orders of linear recurring sequences
- On computably enumerable structures
- \(\Sigma_{2}^{0}\)-initial segments of computable linear orders
- Graphs realised by r.e. equivalence relations
- On Choice Sets and Strongly Non-Trivial Self-Embeddings of Recursive Linear Orders
- Recursive Linear Orders with Incomplete Successivities
- Initial segments of computable linear orders with additional computable predicates
- scientific article; zbMATH DE number 749928 (Why is no real title available?)
- Reducibilities among equivalence relations induced by recursively enumerable structures
This page was built for publication: Initial segments of recursive linear orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1267600)
