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 is any r.e. nonzero degree, there exist r.e. sets
with
such that if
is an r.e. splitting of
, then
. 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
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
, 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
-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)
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