On a problem of Ishmukhametov (Q377474)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On a problem of Ishmukhametov
scientific article

    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
    0 references
    0 references
    0 references
    0 references
    d.c.e. degrees
    0 references
    Lachlan sets
    0 references
    Turing degrees
    0 references
    0 references