On a question of Slaman and Steel
Abstract
We consider an old question of Slaman and Steel: whether Turing equivalence is an increasing union of Borel equivalence relations none of which contain a uniformly computable infinite sequence. We show this question is deeply connected to problems surrounding Martin’s conjecture and in the theory of countable Borel equivalence relations. In particular, if Slaman and Steel’s question has a positive answer, it implies there is a universal countable Borel equivalence relation which is not uniformly universal, that there is a ( ≡ T , ≡ m ) (\equiv _T,\equiv _m) -invariant function which is not uniformly invariant on any pointed perfect set, and which is everywhere ≤ m \leq _m -incomparable with both the Turing jump j j and its complement.
Fields of Study & Subjects
Computability
Logic
AI Algorithms
Advanced Topology and Set Theory
semigroups and automata theory
Publication details
- Journal / source
- Transactions of the American Mathematical Society Series B
- Volume
- 13
- Issue
- 11
- Pages
- 379–402
- Publication date
- 24 June 2026
- Language
- EN