Switching Categoricity Behavior with a Given Degree

David Gonzalez; Java Darleen Villano; and Jos\'e Jerem\'ias Valenzuela Morales

In the authors' words

Given a noncomputable, computably enumerable set $D$ , we construct a computable structure $G$ such that any two computable copies of $G$ are computably isomorphic while there are two $D$ -computable copies of $G$ that are not $D$ -computably isomorphic. In other words, $G$ is computably categorical, but not computably categorical relative to $D$ . Conversely, we construct a computable structure that is not computably categorical, but is computably categorical relative to $D$ . These results differ from those in the literature regarding computable categoricity and its relativiziations because the degree $D$ is given instead of constructed. Our work negatively answers a question of Downey, Harrison-Trainor and Melnikov in the computably enumerable case.

Main resultThe abstract does not state a limitation.

Switching Categoricity Behavior with a Given Degree

In the authors' words

More on Other mathematics that day

A variational approach for the 2D Abelian Yang-Mills-Higgs measure

Mathematics Graduate Training in the Age of AI

Double-wells in a strong magnetic field: absence of tunneling for infinitely many values of the coupling constant

A variational model of nonlinear poroelasticity

Topological isomorphism of procountable groups is universal analytic