Counting the back-and-forth types

Author:
  • AMAntonio Montalbán
    Antonio Montalbán
Publisher website
Google Scholar
Abstract
Given a class of structures and n∈ω, we study the dichotomy between there being countably many n-back-and-forth equivalence classes and there being continuum many. In the latter case, we show that, relative to some oracle, every set can be weakly coded in the (n-1)st jump of some structure in . In the former case, we show that there is a countable set of infinitary Πn relations that captures all of the Πn information about the structures in . In most cases, where there are countably many n-back-and-forth equivalence classes, there is a computable description of them. We will show how to use this computable description to get a complete set of computably infinitary Πn formulas. This will allow us to completely characterize the relatively intrinsically ∑n+10 relations in the computable structures of , and to prove that no Turing degree can be coded by the (n-1)st jump of any structure in unless that degree is already below 0(n-1).

This publication has 13 references indexed in Scilit: