Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 $ A$, then $ {A_0}\not \equiv {}_TB$. Some generalizations are discussed.


References [Enhancements On Off] (What's this?)

  • [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 $ T$- and $ W$-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, $ P$-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 $ T$-degrees of r.e. sets, J. Symbolic Logic 48 (1983), 125-134. MR 727783 (85b:03072)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D25

Retrieve articles in all journals with MSC: 03D25


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1985-0797064-9
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society