PreprintCC BY 4.0arXiv
Switching Categoricity Behavior with a Given Degree
Abstract
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.
Related
- Minimum Distance Spectral Radius of Tree with Given Maximum Degree
- Size and spectral radius conditions for the existence of k-factor in graphs with given minimum degree
- Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
- Weakly uniform computable categoricity and function composition
- Exact curve counting of given word length on the once-punctured torus
BibTeX
@misc{gonzalez2026switching,
title = {{Switching Categoricity Behavior with a Given Degree}},
author = {David Gonzalez and Java Darleen Villano and José Jeremías Valenzuela Morales},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21047},
eprint = {2609.21047},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21047},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Switching Categoricity Behavior with a Given Degree
AU - David Gonzalez
AU - Java Darleen Villano
AU - José Jeremías Valenzuela Morales
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.21047
UR - https://arxiv.org/abs/2609.21047
AB - 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.
ER -