On the learning power of Friedman-Stanley jumps
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915115949883392 |
|---|---|
| author | Cipriani, Vittorio Marcone, Alberto Mauro, Luca San |
| author_facet | Cipriani, Vittorio Marcone, Alberto Mauro, Luca San |
| contents | Recently, a surprising connection between algorithmic learning of algebraic structures and descriptive set theory has emerged. Following this line of research, we define the learning power of an equivalence relation $E$ on a topological space as the class of isomorphism relations with countably many equivalence classes that are continuously reducible to $E$. In this paper, we describe the learning power of the finite Friedman-Stanley jumps of $=_{\mathbb{N}}$ and $=_{\mathbb{N}^\mathbb{N}}$, proving that these equivalence relations learn the families of countable structures that are pairwise distinguished by suitable infinitary sentences. Our proof techniques introduce new ideas for assessing the continuous complexity of Borel equivalence relations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12846 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the learning power of Friedman-Stanley jumps Cipriani, Vittorio Marcone, Alberto Mauro, Luca San Logic 03E15, 03C57, 68Q32 Recently, a surprising connection between algorithmic learning of algebraic structures and descriptive set theory has emerged. Following this line of research, we define the learning power of an equivalence relation $E$ on a topological space as the class of isomorphism relations with countably many equivalence classes that are continuously reducible to $E$. In this paper, we describe the learning power of the finite Friedman-Stanley jumps of $=_{\mathbb{N}}$ and $=_{\mathbb{N}^\mathbb{N}}$, proving that these equivalence relations learn the families of countable structures that are pairwise distinguished by suitable infinitary sentences. Our proof techniques introduce new ideas for assessing the continuous complexity of Borel equivalence relations. |
| title | On the learning power of Friedman-Stanley jumps |
| topic | Logic 03E15, 03C57, 68Q32 |
| url | https://arxiv.org/abs/2501.12846 |