Undecidability of the degree structure of primitive recursive m-reducibility
Birzhan Kalmurzayev, Nikolay A. Bazhenov, Alibek M Iskakov · Journal of Logic and Computation · 2024
Abstract Let $\mathbf{C}^{pr}_{m}$ be the upper semilattice of degrees of computable sets with respect to primitive recursive $m$-reducibility. We prove that the first-order theory of $\mathbf{C}^{pr}_{m}$ is hereditarily undecidable.