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