Computable Categoricity Relative to a C.E. Degree

A computable graph G is computably categorical relative to a degree d if and only if for all d-computable copies B of G, there is a d-computable isomorphism f:G→B. In this paper, we prove that for every computable partially ordered set P and computable partition P=P0⊔P1, there exists a computable, computably categorical graph G and an embedding h of P into the c.e. degrees where G is computably categorical relative to all degrees in h(P0) and not computably categorical relative to any degree in h(P1). This is a generalization of a result by Downey, Harrison-Trainor, and Melnikov.