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

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] Klaus Ambos-Spies, Antimitotic recursively enumerable sets, Z. Math. Logik Grundlag. Math. 31 (1985), no. 5, 461–477. MR 808773, https://doi.org/10.1002/malq.19850312903
[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), no. 4, 1125–1136. MR 771781, https://doi.org/10.2307/2274265
[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 51 (1986), no. 1, 88–109. MR 830076, https://doi.org/10.2307/2273946
[Fe] Peter A. Fejer, The density of the nonbranching degrees, Ann. Pure Appl. Logic 24 (1983), no. 2, 113–130. MR 713296, https://doi.org/10.1016/0168-0072(83)90028-3
[Fr] Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symb. Logic 23 (1958), 309–316. MR 0109125
[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), no. 4, 629–634. MR 572317, https://doi.org/10.1090/S0002-9939-1980-0572317-9
[Ld1] Richard E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973), 199–211. MR 0342381, https://doi.org/10.2307/2272056
[Ld2] Richard E. Ladner, A completely mitotic nonrecursive r.e. degree, Trans. Amer. Math. Soc. 184 (1973), 479–507 (1974). MR 0398805, https://doi.org/10.1090/S0002-9947-1973-0398805-7
[LS] Richard E. Ladner and Leonard P. Sasso Jr., The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), no. 4, 429–448. MR 0379157, https://doi.org/10.1016/0003-4843(75)90007-8
[LR1] M. Lerman and J. B. Remmel, The universal splitting property. I, Logic Colloquium ’80 (Prague, 1980) Stud. Logic Foundations Math., vol. 108, North-Holland, Amsterdam-New York, 1982, pp. 181–207. MR 673793
[LR2] M. Lerman and J. B. Remmel, The universal splitting property. II, J. Symbolic Logic 49 (1984), no. 1, 137–150. MR 736609, https://doi.org/10.2307/2274097
[MS] Michael D. Morley and Robert I. Soare, Boolean algebras, splitting theorems, and 𝐷⁰₂ sets, Fund. Math. 90 (1975), no. 1, 45–52. MR 0398807
[Ow] James C. Owings Jr., Recursion, metarecursion, and inclusion, J. Symbolic Logic 32 (1967), 173–179. MR 0216951, https://doi.org/10.2307/2271654
[Sa] Gerald E. Sacks, On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231. MR 0146078, https://doi.org/10.2307/1970214
[So1] Robert I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), no. 2, 513–530. MR 0429521, https://doi.org/10.2307/2272252
[So2] Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921
[So3] Anil Nerode and Richard A. Shore (eds.), Recursion theory, Proceedings of Symposia in Pure Mathematics, vol. 42, American Mathematical Society, Providence, RI, 1985. MR 791047
[St] Michael Stob, 𝑤𝑡𝑡-degrees and 𝑇-degrees of r.e. sets, J. Symbolic Logic 48 (1983), no. 4, 921–930 (1984). MR 727783, https://doi.org/10.2307/2273658