Counting the back-and-forth types
The paper is devoted to the study of the interactions between the structural properties of a structure and computational properties of its presentations. Given a class of structures \({\mathcal K}\) and an integer \(n\), the author studies the dichotomy between there being countably many \(n\)-back-and-forth equivalence classes and there being continuum many. In the former case it is shown that there is a countable set of infinitary \(\Pi_n\) relations that captures all of the \(\Pi_n\) information about the structure in \({\mathcal K}\). In the latter case it is shown that, relative to some oracle, every set can be weakly coded in the \((n-1)\)st jump of a structure in \({\mathcal K}\).
- Coding and definability in computable structures
- On bi-embeddable categoricity of algebraic structures
- Learning families of algebraic structures from informant
- The back-and-forth method and computability without delay
- Rice sequences of relations
- A robuster Scott rank
- Measuring complexities of classes of structures
- The property ``arithmetic-is-recursive on a cone
- Optimal syntactic definitions of back-and-forth types
This page was built for publication: Counting the back-and-forth types
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2907060)
