×

Initial segments of recursive linear orders. (English) Zbl 0909.03034

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 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.

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDFBibTeX XMLCite
Full Text: DOI