Relativizing computable categoricity
Rodney G. Downey, Matthew Harrison‐Trainor, Alexander Melnikov · Proceedings of the American Mathematical Society · 2021
A recent thread in computable structure theory has been the investigation of computable structures after relativizing, the key idea being that facts which are true for algebraic/structural reasons tend to relativize. On the other hand, there are pathological examples such as a structure which is computably categorical but not relatively computably categorical; but such behaviour must eventually stabilize, as for example a structure is either computably categorical relative to all degrees above 0 \mathbf {0} or not computably categorical relative to all degrees above 0 \mathbf {0} . But what can happen in between? We show a surprising result: there is a structure which alternates between being computably categorical and not computably categorical relative to an infinite increasing sequence of c.e. degrees.