Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T16:09:04.359Z Has data issue: false hasContentIssue false

Degrees coded in jumps of orderings

Published online by Cambridge University Press:  12 March 2014

Julia F. Knight*
Affiliation:
Department of Mathematics, University of Illinois, Urbana, Illinois 61801
*
Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556

Extract

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1986

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable