World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Linear Orders and Categoricity Spectra

    https://doi.org/10.1142/9789813237551_0002Cited by:2 (Source: Crossref)
    Abstract:

    We study effective categoricity for computable linear orders. The categoricity spectrum of a computable structure S is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable presentations of S. The degree of categoricity for S is the least degree in this spectrum. The degree of categoricity d is strong if there are two computable copies of S such that any isomorphism between the copies computes d.

    We give a new series of computable linear orders with no degree of categoricity: for every computable successor ordinal α ≥ 4, the set of PA degrees over 0(α) is the categoricity spectrum for a scattered linear order. We also build the first examples of linear orders with non-strong degrees of categoricity: If α is a computable infinite ordinal, then there is a scattered linear order such that it is Δα+20 categorical, not Δα0 categorical, and has non-strong degree of categoricity.