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
HTML articles powered by AMS MathViewer

by R. G. Downey PDF

Trans. Amer. Math. Soc. 291 (1985), 337-351 Request permission

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

Klaus Ambos-Spies, Antimitotic recursively enumerable sets, Z. Math. Logik Grundlag. Math. 31 (1985), no. 5, 461–477. MR 808773, DOI 10.1002/malq.19850312903

Degree theoretic splitting properties of r.e. sets

R. G. Downey and J. B. Remmel, The universal complementation property, J. Symbolic Logic 49 (1984), no. 4, 1125–1136. MR 771781, DOI 10.2307/2274265

Structural interactions of the recursively enumerable

and

degrees

Degrees of bases and splittings of r.e. subspaces

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, DOI 10.2307/2273946
Peter A. Fejer, The density of the nonbranching degrees, Ann. Pure Appl. Logic 24 (1983), no. 2, 113–130. MR 713296, DOI 10.1016/0168-0072(83)90028-3
Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symbolic Logic 23 (1958), 309–316. MR 109125, DOI 10.2307/2964290

genericity for recursively enumerable sets

A. H. Lachlan, Decomposition of recursively enumerable degrees, Proc. Amer. Math. Soc. 79 (1980), no. 4, 629–634. MR 572317, DOI 10.1090/S0002-9939-1980-0572317-9
Richard E. Ladner, Mitotic recursively enumerable sets, J. Symbolic Logic 38 (1973), 199–211. MR 342381, DOI 10.2307/2272056
Richard E. Ladner, A completely mitotic nonrecursive r.e. degree, Trans. Amer. Math. Soc. 184 (1973), 479–507 (1974). MR 398805, DOI 10.1090/S0002-9947-1973-0398805-7
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 379157, DOI 10.1016/0003-4843(75)90007-8
M. Lerman and J. B. Remmel, The universal splitting property. I, Logic Colloquium ’80 (Prague, 1980) Studies in Logic and the Foundations of Mathematics, vol. 108, North-Holland, Amsterdam-New York, 1982, pp. 181–207. MR 673793
M. Lerman and J. B. Remmel, The universal splitting property. II, J. Symbolic Logic 49 (1984), no. 1, 137–150. MR 736609, DOI 10.2307/2274097
Michael D. Morley and Robert I. Soare, Boolean algebras, splitting theorems, and $D^{0}_{2}$ sets, Fund. Math. 90 (1975), no. 1, 45–52. MR 398807, DOI 10.4064/fm-90-1-45-52
James C. Owings Jr., Recursion, metarecursion, and inclusion, J. Symbolic Logic 32 (1967), 173–179. MR 216951, DOI 10.2307/2271654
Gerald E. Sacks, On the degrees less than 0′, Ann. of Math. (2) 77 (1963), 211–231. MR 146078, DOI 10.2307/1970214
Robert I. Soare, The infinite injury priority method, J. Symbolic Logic 41 (1976), no. 2, 513–530. MR 429521, DOI 10.2307/2272252
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, DOI 10.1007/978-3-662-02460-7
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, DOI 10.1090/pspum/042
Michael Stob, $\textrm {wtt}$-degrees and $\textrm {T}$-degrees of r.e. sets, J. Symbolic Logic 48 (1983), no. 4, 921–930 (1984). MR 727783, DOI 10.2307/2273658