zbMATH — the first resource for mathematics

A superhigh diamond in the c.e. tt-degrees. (English) Zbl 1216.03054
A computably enumerable set \(A\) is superhigh if \(A'\equiv_{\text{tt}}0''\) . In this paper it is proved that there are superhigh computably enumerable sets \(A\) and \(B\) such that \({\mathbf 0}\), \(\text{deg}_{\text{tt}}(A)\), \(\text{deg}_{\text{tt}}(B)\), and \({\mathbf 0}'_{\text{tt}}\) form a diamond in the computably enumerable tt-degrees.

03D25 Recursively (computably) enumerable sets and degrees
03D30 Other degrees and reducibilities in computability and recursion theory
Full Text: DOI
[1] Cooper S.B.: Degrees of unsolvability complementary between recursively enumerable degrees I. Ann. Math. Logic 4, 31–73 (1972) · Zbl 0248.02045 · doi:10.1016/0003-4843(72)90011-3
[2] Downey R.: D.r.e. degrees and the nondiamond theorem. Bull. Lond. Math. Soc. 21, 43–50 (1989) · Zbl 0628.03030 · doi:10.1112/blms/21.1.43
[3] Epstein, R.L.: Minimal degrees of unsolvability and the full approximation construction. Mem. Amer. Math. Soc., 162(3), (1975) · Zbl 0315.02043
[4] Jockusch C.G. Jr, Mohrherr J.: Embedding the diamond lattice in the recursively enumerable truth-table degrees. Proc. Amer. Math. Soc. 94, 123–128 (1985) · Zbl 0534.03019
[5] Lachlan A.H.: Lower bounds for pairs of recursively enumerable degrees. Proc. Lond. Math. Soc. 16, 537–569 (1966) · Zbl 0156.00907 · doi:10.1112/plms/s3-16.1.537
[6] Martin D.: Classes of recursively enumerable sets and degrees of unsolvability. Z. Math. Logik Grundlag. Math. 12, 295–310 (1966) · Zbl 0181.30504 · doi:10.1002/malq.19660120125
[7] Mohrherr J.: A refinement of low n and high n for the r.e. degrees. Z. Math. Logik Grundlag. Math. 32, 5–12 (1986) · Zbl 0625.03022 · doi:10.1002/malq.19860320103
[8] Ng K.M.: On very high degrees. J. Symb. Logic 73, 309–342 (2008) · Zbl 1168.03031 · doi:10.2178/jsl/1208358755
[9] Simpson S.G.: Almost everywhere domination and superhighness. Math. Log. Q. 53, 462–482 (2007) · Zbl 1123.03040 · doi:10.1002/malq.200710012
[10] Soare R.I.: Recursively Enumerable Sets and Degrees. Springer, Heidelberg (1987) · Zbl 0667.03030
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.