It is proved that for every countable structure A and a successive computable ordinal α there is a countable structure A−α which is ≤Σ-least among all countable structures C such… Click to show full abstract
It is proved that for every countable structure A and a successive computable ordinal α there is a countable structure A−α which is ≤Σ-least among all countable structures C such that A is Σ-definable in the α-th jump C. We also show that this result does not hold for the limit α = ω. Moreover, we prove that there is no countable structure A with the degree spectrum {d : a ≤ d} for 1The research of the first author was funded by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities, project no. 1.1515.2017/4.6. 2The research of the third author was funded by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities, project no. 1.451.2016/1.4. 3The research was partially supported by the Packard Fellowship and by the NSF grant DMS-0901169 4The research was supported by the Grants Council (under RF President) for State Aid of Leading Scientific Schools (grant NSh-6848.2016.1) and by RFBR Grant No. 15-01-05114-a. Preprint submitted to Journal of Logic and Computation February 20, 2018 a > 0.
               
Click one of the above tabs to view related content.