A Borel graphable equivalence relation with no Borel graphing of diameter two
Abstract
We answer a question of Arant, Kechris and Lutz by showing that there is a Borel graphable equivalence relation with no Borel graphing of diameter less than 3. More specifically, we prove that there is an equivalence relation with a Borel graphing of diameter at most 4 but no Borel graphing of diameter less than 3. Our proof relies on a technical lemma about computability-theoretic genericity, which may have other applications.
Fields of Study & Subjects
Computability
Logic
AI Algorithms
Advanced Topology and Set Theory
programming
and type systems
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 7 January 2026
- Document type
- Preprint