A hierarchy of families of recursively enumerable degrees (Q3701410)
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 3926897
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A hierarchy of families of recursively enumerable degrees |
scientific article; zbMATH DE number 3926897 |
Statements
A hierarchy of families of recursively enumerable degrees (English)
0 references
1984
0 references
0.9331063
0 references
0.9197844
0 references
0.9108942
0 references
0 references
0.8959005
0 references
Assume that e is a number, b is a r.e. degree, and A is a set. We say that e is a representative for b in A if \(e\in A\) and \(W_ e\in b\). Let A be a set and let \({\mathfrak A}\) be a family of r.e. degrees. We say that A is a basis for \({\mathfrak A}\) if the following two conditions hold: (1) every e in A is a representative in A for some b in \({\mathfrak A}\); (ii) every b in \({\mathfrak A}\) has a representative in A. Given any number n, we say that \({\tilde \Delta}{}_ n\) is the class of all \({\mathfrak A}\) which have a \(\Delta_ n\) basis, \({\tilde \Pi}{}_ n\) is the class of all \({\mathfrak A}\) which have a \(\Pi_ n\) basis, and \({\tilde \Sigma}{}_ n\) is the class of all \({\mathfrak A}\) which have a \(\Sigma_ n\) basis. In this paper it is shown that for all n, \({\tilde \Delta}{}_ n=\Sigma_ n\) and for any n, \({\tilde \Sigma}{}_ n\cup {\tilde \Pi}_ n={\tilde \Pi}_ n\) and \({\tilde \Sigma}{}_ n\cap {\tilde \Pi}_ n={\tilde \Delta}_ n\). The main results of this paper are the following theorems: Theorem 6. For all n, if \({\mathfrak A}\) is \({\tilde \Delta}{}_{n+1}\) then \({\mathfrak A}\) is \({\tilde \Pi}{}_ n\). Theorem 10. If \(n\geq 3\) then \({\tilde \Pi}{}_ n-{\tilde \Pi}_{n-1}\neq \emptyset\) (\({\tilde \Pi}{}_ 0={\tilde \Pi}_ 1={\tilde \Pi}_ 2)\). Theorem 11. If a is a Turing degree such that \(a\geq 0^{(3)}\) then there is a family \({\mathfrak A}\) such that deg(ind(\({\mathfrak A}))=a\). Theorem 12. If \({\mathfrak A}\) is a nonempty family of r.e. degrees such that 0' is not in \({\mathfrak A}\), then \(Rec\leq_ 1ind({\mathfrak A})\). Theorem 15. If \({\mathfrak A}\) is a nonempty family of r.e. degrees such that 0 is not in \({\mathfrak A}\), and if \({\mathfrak A}\) is \({\tilde \Pi}{}_ 0\), then \(Rec\leq_ 1ind({\mathfrak A})\).
0 references