The degrees of r.e. sets without the universal splitting property

Downey, R. G.

doi:10.1090/S0002-9947-1985-0797064-9

The degrees of r.e. sets without the universal splitting property

Author: R. G. Downey
Journal: Trans. Amer. Math. Soc. 291 (1985), 337-351
MSC: Primary 03D25
DOI: https://doi.org/10.1090/S0002-9947-1985-0797064-9
MathSciNet review: 797064
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that every nonzero r.e. degree contains an r.e. set without the universal splitting property. That is, if $\delta$ is any r.e. nonzero degree, there exist r.e. sets $\emptyset < {}_TB < {}_TA$ with $\deg (A) = \delta$ such that if ${A_0} \sqcup {A_1}$ is an r.e. splitting of , then ${A_0}\not \equiv {}_TB$ . Some generalizations are discussed.

[AS] K. Ambos-Spies, Anti-mitotic recursively enumerable sets, Z. Math. Logik Grundlag. Math. (to appear). MR 808773 (87d:03113)
[AF] K. Ambos-Spies and P. Fejer, Degree theoretic splitting properties of r.e. sets (to appear).
[DR] R. G. Downey and J. B. Remmel, The universal complementation property, J. Symbolic Logic 49 (1984), 1125-1136. MR 771781 (87j:03064)
[DS] R. Downey and M. Stob, Structural interactions of the recursively enumerable - and -degrees (to appear).
[DRW] R. G. Downey, J. B. Remmel and L. V. Welch, Degrees of bases and splittings of r.e. subspaces (in preparation).
[DW] R. G. Downey and L. V. Welch, Splitting properties of r.e. sets and degrees, J. Symbolic Logic (to appear). MR 830076 (87j:03059)
[Fe] P. Fejer, The density of the nonbranching degrees, Ann. Pure Appl. Logic 24 (1983), 113-130. MR 713296 (85g:03062)
[Fr] R. M. Friedberg, Three theorems on recursive enumeration, J. Symbolic Logic 23 (1958), 309-316. MR 0109125 (22:13)
[In] M. A. Ingrassia, -genericity for recursively enumerable sets, Ph.D. thesis, Univ. of Illinois at Urbana-Champaign, 1981.
[La] A. H. Lachlan, Decomposition of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), 629-634. MR 572317 (81i:03065)
[Ld1] R. E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973), 199-211. MR 0342381 (49:7127)
[Ld2] -, A completely mitotic nonrecursive r.e. degree, Trans. Amer. Math. Soc. 184 (1973), 479-507. MR 0398805 (53:2656)
[LS] R. E. Ladner and L. P. Sasso, The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 4 (1975), 429-448. MR 0379157 (52:63)
[LR1] M. Lerman and J. B. Remmel, The universal splitting property. I, Logic Colloquium '80 (D. Van Dalen, ed.), North-Holland, New York, 1983, pp. 181-208. MR 673793 (84d:03054)
[LR2] -, The universal splitting property. II, J. Symbolic Logic 49 (1984), 137-150. MR 736609 (86f:03066)
[MS] M. D. Morley and R. I. Soare, Boolean algebras, splitting theorems and $\Delta _2^0$ sets, Fund. Math. 90 (1975), 45-52. MR 0398807 (53:2658)
[Ow] J. C. Owings, Jr., Recursion, metarecursion, and inclusion, J. Symbolic Logic 32 (1967), 173-178. MR 0216951 (36:46)
[Sa] G. E. Sacks, On the degrees less than ${\mathbf{0}}'$ , Ann. of Math. (2) 77 (1963), 211-231. MR 0146078 (26:3604)
[So1] R. I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), 513-530. MR 0429521 (55:2534)
[So2] -, Recursively enumerable sets and degrees, Omega Series, Springer-Verlag, Berlin and New York (to appear). MR 882921 (88m:03003)
[So3] -, Tree arguments in recursion theory and the ${\mathbf{0}}'''$ -priority method, (A. Nerode and R. Shore, eds.), Recursion Theory, Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, R. I., 1985. MR 791047 (86f:03004)
[St] M. Stob, Wtt-degrees and -degrees of r.e. sets, J. Symbolic Logic 48 (1983), 125-134. MR 727783 (85b:03072)