Autostability spectra for decidable structures

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

We study autostability spectra relative to strong constructivizations (SC-autostability spectra). For a decidable structure , the SC-autostability spectrum of is the set of all Turing degrees capable of computing isomorphisms among arbitrary decidable copies of . The degree of SC-autostability for is the least degree in the spectrum (if such a degree exists). We prove that for a computable successor ordinal α, every Turing degree c.e. in and above 0 (α) is the degree of SC-autostability for some decidable structure. We show that for an infinite computable ordinal β, every Turing degree c.e. in and above 0 (2β+1) is the degree of SC-autostability for some discrete linear order. We prove that the set of all PA-degrees is an SC-autostability spectrum. We also obtain similar results for autostability spectra relative to n-constructivizations.

Original languageEnglish
Pages (from-to)392-411
Number of pages20
JournalMathematical Structures in Computer Science
Volume28
Issue number3
DOIs
Publication statusPublished - 1 Mar 2018

Keywords

  • STRONG CONSTRUCTIVIZATIONS
  • BOOLEAN-ALGEBRAS
  • INDEX SETS
  • COMPUTABLE CATEGORICITY
  • RECURSIVE STRUCTURES
  • HYPERARITHMETICAL DEGREES
  • LINEAR-ORDERINGS
  • MODELS
  • COMPLEXITY
  • STABILITY

Fingerprint Dive into the research topics of 'Autostability spectra for decidable structures'. Together they form a unique fingerprint.

Cite this