Counting the back-and-forth types (Q2907060)

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}\).