Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2505.14920 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918027867455488 |
|---|---|
| author | Arant, Tyler |
| author_facet | Arant, Tyler |
| contents | This paper studies when an arithmetical equivalence relation $E$ can be realized as the connectedness relation of a graph $G$ which is simpler to define than $E$. Several examples of such equivalence relations are established. In particular, it is proved that the $Σ^0_3$ relation of computable isomorphism of structures on $\N$ in a computable first-order language is $Π^0_2$-graphable, i.e., is the connectedness relation of a $Π^0_2$ graph. Graphings of Friedman-Stanley jumps are studied, including an arithmetical construction of a graphing of the Friedman-Stanley jump of $E$ from a graphing of $E$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14920 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graphings of arithmetical equivalence relations Arant, Tyler Logic This paper studies when an arithmetical equivalence relation $E$ can be realized as the connectedness relation of a graph $G$ which is simpler to define than $E$. Several examples of such equivalence relations are established. In particular, it is proved that the $Σ^0_3$ relation of computable isomorphism of structures on $\N$ in a computable first-order language is $Π^0_2$-graphable, i.e., is the connectedness relation of a $Π^0_2$ graph. Graphings of Friedman-Stanley jumps are studied, including an arithmetical construction of a graphing of the Friedman-Stanley jump of $E$ from a graphing of $E$. |
| title | Graphings of arithmetical equivalence relations |
| topic | Logic |
| url | https://arxiv.org/abs/2505.14920 |