Computable categoricity relative to a degree

Abstract: A computable structure $\mathcal{A}$ is said to be computably categorical relative to a degree $\mathbf{d}$ if for all $\mathbf{d}$-computable copies $\mathcal{B}$ of $\mathcal{A}$, there exists a $\mathbf{d}$-computable isomorphism between $\mathcal{A}$ and $\mathcal{B}$. In 2021 result by Downey, Harrison-Trainor, and Melnikov, it was shown that there exists a computable graph $\mathcal{G}$ such that for an infinite increasing sequence of c.e.\ degrees $\mathbf{x}_0 <_T \mathbf{y}_0 <_T \mathbf{x}_1 <_T \mathbf{y}_1\dots$, $\mathcal{G}$ was computably categorical relative to each $\mathbf{x}_i$ but not computably categorical relative to each $\mathbf{y}_i$.  That is, the behavior of categoricity relative to a degree is not monotonic under $\mathbf{0}'$. In this talk, we will sketch how to extend this result for partial orders of c.e.\ degrees, and discuss some future directions of this project.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic