Degrees coded in jumps of orderings
Julia F. Knight · Journal of Symbolic Logic · 1986
All structures to be considered here have universe ω, and all languages come equipped with Gödel numberings. If is a structure, then D( ), the open diagram of , can be thought of as a subset of ω, and it makes sense to talk about the Turing degree deg(D( )). This depends on the presentation as well as the isomorphism type of . For example, consider the ordering = (ω, <). For any B ⊆ ω, it is possible to code B in a copy of as follows: Let π be the permutation of ω such that for each n ∈ ω, π leaves 2n and 2n + 1 fixed if n ∈ B and switches 2n with 2n + 1 if n ∉ B. Let be the copy of such that ≃π . Then n ∈ B iff the sentence 2n < 2n + 1 is in D( ). In §4, this idea will be used to show that for any structure that is not completely trivial, {deg(D( )): ≃ } is closed upwards. It would be satisfying to have a way of assigning Turing degrees to structures such that the degree assigned to a given structure measured the recursion-theoretic complexity of the isomorphism type and was independent of the presentation. Jockusch suggested the following.