Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T05:37:05.094Z Has data issue: false hasContentIssue false

Local Definitions in Degree Structures: The Turing Jump, Hyperdegrees and Beyond

Published online by Cambridge University Press:  15 January 2014

Richard A. Shore*
Affiliation:
Department of Mathematics, Cornell University, Ithaca, NY 14853, USA E-mail: shore@math.cornell.edu, URL: http://www.math.cornell.edu/~shore/

Abstract

There are Π5 formulas in the language of the Turing degrees, D, with ≤, ⋁ and ⋀, that define the relations x″ ≤ y″, x″ = y″ and so x ∈ L 2(y) = {x ≥ y ∣ x″ = y″} in any jump ideal containing 0 (ω). There are also Σ6 & Π6 and Π8 formulas that define the relations w = x″ and w = x′, respectively, in any such ideal I. In the language with just ≤ the quantifier complexity of each of these definitions increases by one. On the other hand, no Π2 or Σ2 formula in the language with just ≤ defines L 2 or x ∈ L 2(y). Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of I is fixed on every degree above 0″ and every relation on I that is invariant under double jump or joining with 0″ is definable over I if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in I. Similar direct coding arguments show that every hyperjump ideal I is rigid and biinterpretable with second order arithmetic with set quantification ranging over sets with hyperdegrees in I. Analogous results hold for various coarser degree structures.

Information

Type
Communications
Copyright
Copyright © Association for Symbolic Logic 2007

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