Computable categoricity relative to a c.e. degree
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918012397813760 |
|---|---|
| author | Villano, Java Darleen |
| author_facet | Villano, Java Darleen |
| contents | A computable graph $\mathcal{G}$ is computably categorical relative to a degree $\mathbf{d}$ if and only if for all $\mathbf{d}$-computable copies $\mathcal{B}$ of $\mathcal{G}$, there is a $\mathbf{d}$-computable isomorphism $f:\mathcal{G}\to\mathcal{B}$. In this paper, we prove that for every computable partially ordered set $P$ and computable partition $P=P_0\sqcup P_1$, there exists a computable computably categorical graph $\mathcal{G}$ and an embedding $h$ of $P$ into the c.e. degrees where $\mathcal{G}$ is computably categorical relative to all degrees in $h(P_0)$ and not computably categorical relative to any degree in $h(P_1)$. This is a generalization of a 2021 result by Downey, Harrison-Trainor, and Melnikov. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06641 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computable categoricity relative to a c.e. degree Villano, Java Darleen Logic 03D25 A computable graph $\mathcal{G}$ is computably categorical relative to a degree $\mathbf{d}$ if and only if for all $\mathbf{d}$-computable copies $\mathcal{B}$ of $\mathcal{G}$, there is a $\mathbf{d}$-computable isomorphism $f:\mathcal{G}\to\mathcal{B}$. In this paper, we prove that for every computable partially ordered set $P$ and computable partition $P=P_0\sqcup P_1$, there exists a computable computably categorical graph $\mathcal{G}$ and an embedding $h$ of $P$ into the c.e. degrees where $\mathcal{G}$ is computably categorical relative to all degrees in $h(P_0)$ and not computably categorical relative to any degree in $h(P_1)$. This is a generalization of a 2021 result by Downey, Harrison-Trainor, and Melnikov. |
| title | Computable categoricity relative to a c.e. degree |
| topic | Logic 03D25 |
| url | https://arxiv.org/abs/2401.06641 |