Isomorphism Spectra and Computably Composite Structures
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911379794952192 |
|---|---|
| author | Lakerdas-Gayle, Joey |
| author_facet | Lakerdas-Gayle, Joey |
| contents | Adapting a result of Bazhenov, Kalimullin, and Yamaleev, we show that if a Turing degree $\textbf{d}$ is the degree of categoricity of a computable structure $\mathcal{M}$ and is not the strong degree of categoricity of any computable structure, then $\mathcal{M}$ has a pair of computable copies whose isomorphism spectrum is not finitely generated. Motivated by this result, we introduce a class of computable structures called computably composite structures with the property that the isomorphisms between arbitrary computable copies of these structures are exactly the unions of isomorphisms between the computable copies of their components. We use this to show that any computable union of isomorphism spectra is also an isomorphism spectrum. In particular, this gives examples of isomorphism spectra that are not finitely generated. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16586 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Isomorphism Spectra and Computably Composite Structures Lakerdas-Gayle, Joey Logic 03D45, 03C57, 03D28 Adapting a result of Bazhenov, Kalimullin, and Yamaleev, we show that if a Turing degree $\textbf{d}$ is the degree of categoricity of a computable structure $\mathcal{M}$ and is not the strong degree of categoricity of any computable structure, then $\mathcal{M}$ has a pair of computable copies whose isomorphism spectrum is not finitely generated. Motivated by this result, we introduce a class of computable structures called computably composite structures with the property that the isomorphisms between arbitrary computable copies of these structures are exactly the unions of isomorphisms between the computable copies of their components. We use this to show that any computable union of isomorphism spectra is also an isomorphism spectrum. In particular, this gives examples of isomorphism spectra that are not finitely generated. |
| title | Isomorphism Spectra and Computably Composite Structures |
| topic | Logic 03D45, 03C57, 03D28 |
| url | https://arxiv.org/abs/2501.16586 |