On a problem of Ishmukhametov (Q377474)

From MaRDI portal





scientific article; zbMATH DE number 6223053
Language Label Description Also known as
default for all languages
No label defined
    English
    On a problem of Ishmukhametov
    scientific article; zbMATH DE number 6223053

      Statements

      On a problem of Ishmukhametov (English)
      0 references
      0 references
      0 references
      0 references
      6 November 2013
      0 references
      For a d.c.e. set \(X\) with a d.c.e. enumeration \(\{X_s\}_{s \in \mathbb{N}}\), the corresponding Lachlan set \(L(X)\) is defined as \[ \{s : \exists x[x \in X_{s^{-}}X_{s-1}~\text{and}~ x \notin X]\}. \] In this paper it is proved that there exists a d.c.e. set \(D\) such that for any d.c.e. set \(B \equiv_{T} D\), there exists a d.c.e. set \(A \equiv_{T} D\) such that \(L(A)\leq_{T} L(B)\) and \(L(B) \nleq_{T} L (A)\). This answers a question posed by \textit{S. Ishmukhametov} [Arch. Math. Logic 38, No. 6, 373--386 (1999; Zbl 0942.03049)].
      0 references
      d.c.e. degrees
      0 references
      Lachlan sets
      0 references
      Turing degrees
      0 references

      Identifiers