Extensions of categoricity relative to a degree

Abstract

In this paper, we apply the machinery developed in arXiv:2401.06641(2) to study the behavior of computable categoricity relativized to non-c.e. degrees. In particular, we show that we can build a computable structure which is not computably categorical but is computably categorical relative to a $1$-generic degree. Additionally, we show that other classes of structures besides directed graphs admit a computable example which can change its computable categorical behavior relative to different degrees.

20 pages