×

Localization of a theorem of Ambos-Spies and the strong anti-splitting property. (English) Zbl 0634.03033

A pair of r.e. sets \(A_ 1\), \(A_ 2\) split an r.e. set A (written \(A_ 1\sqcup A_ 2=A)\) if \(A_ 1\cup A_ 2=A\) and \(A_ 1\cap A_ 2=\emptyset\). We say A has the strong antisplitting property if there exists an r.e. set B with \(\emptyset <_ TB<_ TA\) such that if \(A_ 1\sqcup A_ 2=A\) then (i) \(A_ 1\leq_ TB\) implies \(A_ 1\equiv_ T\emptyset\), and (ii) \(A_ 1\geq_ TB\) implies \(A_ 1\equiv_ TB\). The main result of this paper is the following Theorem. Let B be an r.e. set with deg(B) high. Then there exist \(A\leq_ TB\) such that A has the strong antisplitting property.
The main ingredient of the proof is a “localisation” of Ambos-Spies’ result that the “cup or cap” theorem fails for W-degrees. Some open questions are also given.

MSC:

03D25 Recursively (computably) enumerable sets and degrees
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Ambos-Spies, K.: Contiguous r.e. degrees. In: Logic Colloquium ’83. Springer Lecture notes1104, 1–37 (1984).
[2] Ambos-Spies, K.: Cupping and noncapping in the r.e. weak truth table and Turing degrees. Archiv für Math. Logik.25, 109–126 (1985). · Zbl 0619.03032 · doi:10.1007/BF02007561
[3] Ambos-Spies, K.: Anti-mitotic recursively enumerable sets. Z. Math. Logik Grund. Math.31, 461–477 (1985). · Zbl 0587.03029 · doi:10.1002/malq.19850312903
[4] Ambos-Spies, K., Fejer, P.: Degree-theoretic splitting properties of r.e. sets, (to appear). · Zbl 0673.03027
[5] Ambos-Spies, K., Jockusch, C., Shore, R., Soare, R.: An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees. Trans. A. M. S.281, 109–128 (1984). · Zbl 0539.03020 · doi:10.1090/S0002-9947-1984-0719661-8
[6] Downey, R.G.: The degrees of r.e. sets without the universal splitting property. Trans. A. M. S.291, 337–351 (1985). · Zbl 0576.03028
[7] Downey, R., Ingrassia, M., Stob, M., Welch, L.: unpublished manuscript.
[8] Downey, R.G., Jockusch, C.G.:T-degrees, jump classes and strong reducibilities, (to appear). Trans. A. M. S. · Zbl 0638.03039
[9] Downey, R.G., Stob, M.: Structural interactions of the recursively enumerableT- andW-degrees. Annals Pure and Applied Logic31, 205–236 (1986). · Zbl 0604.03015 · doi:10.1016/0168-0072(86)90071-0
[10] Downey, R.G., Welch, L.V.: Splitting properties of r.e. sets and degrees. J. S. L.51, 88–109 (1986). · Zbl 0597.03025
[11] Fejer, P., Soare, R.I.: The plus cupping theorem for the recursively enumerable degrees. In: Logic Year 1979–1980, (Ed. Lerman, Schmerl and Soare), pp. 49–62. New York: Springer 1981.
[12] Ladner, R., Sasso, L.: The weak truth table degrees of recursively enumerable sets. Ann. Math. Logic4, 429–448 (1975). · Zbl 0324.02028 · doi:10.1016/0003-4843(75)90007-8
[13] Lerman, M., Remmel, J.B.: The universal splitting property I. In: Logic Colloquium ’80, (Ed. Van Dalen, Lascar &amp; Smiley), pp. 181–209, New York: North Holland 1982.
[14] Lerman, M., Remmel, J.B.: The universal splitting property II. J. S. L.49, 137–150 (1984). · Zbl 0586.03033
[15] Soare, R.I.: The infinite injury priority method. J. S. L.41, 513–530 (1976). · Zbl 0329.02019
[16] Soare, R.I.: Recursively Enumerable Sets and Degrees, Springer-Verlag (Omega Series), New York (1987). · Zbl 0667.03030
[17] Stob, M.:Wtt-degrees andT-degrees of r.e. sets. J. S. L.48, 921–930 (1983). · Zbl 0563.03028
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.