Computable categoricity relative to a c.e. degree

Abstract

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

21 pages