Jump embeddings in the Turing degrees (Q3984430)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 26209
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Jump embeddings in the Turing degrees |
scientific article; zbMATH DE number 26209 |
Statements
Jump embeddings in the Turing degrees (English)
0 references
27 June 1992
0 references
jump embedding
0 references
jump partial ordering
0 references
Turing degrees
0 references
Turing reducibility
0 references
Turing jump operator
0 references
jump trace
0 references
arithmetical degree
0 references
gap- \(n\) trace
0 references
0.8391680717468262
0 references
0.797286868095398
0 references
Let \({\mathcal P} = (P,\leq_ P,J_ P)\) be a partial ordering structure with a unary function \(J_ P:\;P \to P\). If \(J_ P\) is monotone and strictly increasing, i.e. \[ \forall p,q \in P \bigl( p \leq_ P q \to J_ P(p) \leq_ P J_ P(q)\bigr) \] and \[ \forall p \in P \bigl( p<_ P J_ P(p)\bigr) , \] then \({\mathcal P}\) is called a jump partial ordering. If for all \(p \in P\), there are at most finitely many \(q \in P\) such that \(p \leq_ P q \leq_ P J_ P(p)\), then the jump partial ordering \({\mathcal P}\) is called sparse. The paper under review shows the following general embedding results about the jump partial ordering: (1) Let \({\mathcal P} = (P,\leq_ P,J_ P,0)\) be a jump partial ordering such that \((P,\leq_ P)\) is a linear ordering (so-called jump linear ordering) with least element; if either (i) \({\mathcal P}\) is sparse and \((P,\leq_ P)\) is well-founded, or (ii) \(J_ P\) is an injective function and the relation \(\leq_{JP}\) defined by \(p \leq_{JP} q\) iff \(J_ P(p) \leq_ P q\) for all \(p,q \in P\) is well-founded, then \({\mathcal P}\) is embeddable in \((D,\leq_ T,J_ T,\underset\tilde{} 0)\), where \(D\) is the set of all Turing degrees, \(\leq_ T\) is the Turing reducibility, \(J_ T\) is the Turing jump operator and \(\underset\tilde{} 0\) of the Turing degree of recursive sets. (2) Every countable jump partial ordering is embeddable in \((D,\leq_ T,J_ T)\). Another interesting embedding result of the paper is given in terms of the jump trace of Turing degrees. For any arithmetical degree \(\underset\tilde{} a\), the jump trace of \(\underset\tilde{} a\) is the sequence \[ \hbox{JTr} (\underset\tilde{} a) = (h_ 0,h_ 1,\dots ,h_ n,\dots;\dots ,l_ n,\dots ,l_ 1,l_ 0), \] where, for all \(i\), \[ \underset\tilde{} 0^{(h_ i+i)} \leq_ T \underset\tilde{} a^{(i)} \leq_ T \underset\tilde{} 0^{(l_ i+i)}, \] and these bounds are best possible. It is easy to see that any jump trace is of the form \[ (h_ 0,h_ 1,\dots ,h_{k-1}, \overset\rightharpoonup h ; \overset\leftharpoonup l ,\l_{k-1},\dots ,l_ 1,l_ 0) \] with \[ h_ 0 \leq h_ 1 \leq \dots \leq h_{k-1} \leq h \leq l \leq l_{k- 1} \leq \dots \leq l_ 1 \leq l_ 0 \] and \(l_ i \leq l_{i+1}+l\). And any sequence of this form is called a gap-\((l-h)\) trace. A trace is called realized iff it is the jump trace of some degree. This paper shows that: (3) For \(n \leq 2\), every gap-\(n\) trace is realized. For \(n>2\), if the simplest gap-\(n\) trace \((\overset\rightharpoonup 0 ;\overset\leftharpoonup n)\) is realized, then every gap-\(n\) is realized.
0 references