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 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

      Identifiers