Switching Categoricity Behavior with a Given Degree
En palabras de los autores
Given a noncomputable, computably enumerable set , we construct a computable structure such that any two computable copies of are computably isomorphic while there are two -computable copies of that are not -computably isomorphic. In other words, is computably categorical, but not computably categorical relative to . Conversely, we construct a computable structure that is not computably categorical, but is computably categorical relative to . These results differ from those in the literature regarding computable categoricity and its relativiziations because the degree is given instead of constructed. Our work negatively answers a question of Downey, Harrison-Trainor and Melnikov in the computably enumerable case.
Apareció: lunes, 21 de septiembre. arXiv. Preprint, todavía sin revisión por pares.