Optimal syntactic definitions of back-and-forth types
Abstract
The back-and-forth relations M ≤ α N \mathcal {M} \leq _\alpha \mathcal {N} are central to computable structure theory and countable model theory. It is well-known that the relation { ( M , N ) : M ≤ α N } \{(\mathcal {M},\mathcal {N}) : \mathcal {M} \leq _\alpha \mathcal {N}\} is (lightface) Π 2 α 0 \Pi ^0_{2\alpha } . We show that this is optimal as the set is Π 2 α 0 \mathbf {\Pi }^0_{2\alpha } -complete. We are also interested in the one-sided relations { N : M ≤ α N } \{ \mathcal {N} : \mathcal {M} \leq _\alpha \mathcal {N}\} and { N : M ≥ α N } \{ \mathcal {N} : \mathcal {M} \geq _\alpha \mathcal {N}\} for a fixed
Fields of Study & Subjects
Advanced Topology and Set Theory
Computability
Logic
AI Algorithms
programming
and type systems
Publication details
- Journal / source
- Transactions of the American Mathematical Society
- Volume
- 379
- Issue
- 10
- Pages
- 7385–7419
- Publication date
- 14 January 2026
- Language
- EN