Extensions of categoricity relative to a degree

Abstract

In this paper, we apply the machinery developed in Villano (2025) 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 computably categorical behavior relative to different degrees.