Local definitions in degeree structures: The Turing jump, hyperdegrees and beyond

Bulletin of Symbolic Logic 13 (2):226-239 (2007)
Abstract
There are $\Pi_5$ formulas in the language of the Turing degrees, D, with ≤, ∨ and $\vedge$ , that define the relations $x" \leq y"$ , x" = y" and so $x \in L_{2}(y)=\{x\geqy|x"=y"\}$ in any jump ideal containing $0^(\omega)$ . There are also $\Sigma_6$ & $\Pi_6$ and $\Pi_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 L2 or $x\inL_{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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
 
Download options
PhilPapers Archive


Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 12,047
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Citations of this work BETA

No citations found.

Similar books and articles
Analytics

Monthly downloads

Sorry, there are not enough data points to plot this chart.

Added to index

2009-02-05

Total downloads

3 ( #307,790 of 1,101,784 )

Recent downloads (6 months)

3 ( #128,762 of 1,101,784 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Start a new thread
Order:
There  are no threads in this forum
Nothing in this forum yet.