Density of the lattice of \(m\)th degrees of conditional problems. (English. Russian original) Zbl 0873.03041

Sib. Math. J. 37, No. 6, 1110-1112 (1996); translation from Sib. Mat. Zh. 37, No. 6, 1266-1268 (1996).
A paper by Su Gao [J. Symb. Log. 59, 166-181 (1994; Zbl 0799.03047)] treated different notions of reducibility, including \(m\)-reducibility, for so-called conditional problems, represented by ordered pairs of sets of natural numbers. The present paper gives a simple Kleene-Post argument, alleged to prove the density of the lattice of \(m\)-degrees (rendered “\(m\)th degrees” in this translation) of conditional problems. However, the result is false in the form stated in the paper; there are errors in the handling of the distinction between what Gao called trivial and nontrivial degrees.


03D30 Other degrees and reducibilities in computability and recursion theory


Zbl 0799.03047
Full Text: DOI


[1] Gao Su, ”The degrees of conditional problems,” J. Symbol. Logic,59, No. 1, 166–181 (1994). · Zbl 0799.03047
[2] Yu. L. Ershov.”On index sets,” Sibirsk. Mat. Zh.,11, No. 2, 326–342 (1970).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.