Degrees of splittings and bases of recursively enumerable subspaces
HTML articles powered by AMS MathViewer
- by R. G. Downey, J. B. Remmel and L. V. Welch PDF
- Trans. Amer. Math. Soc. 302 (1987), 683-714 Request permission
Abstract:
This paper analyzes the interrelationships between the (Turing) of r.e. bases and of r.e. splittings of r.e. vector spaces together with the relationship of the degrees of bases and the degrees of the vector spaces they generate. For an r.e. subspace $V$ of ${V_\infty }$, we show that $\alpha$ is the degree of an r.e. basis of $V$ iff $\alpha$ is the degree of an r.e. summand of $V$ iff $\alpha$ is the degree and dependence degree of an r.e. summand of $V$. This result naturally leads to explore several questions regarding the degree theoretic properties of pairs of summands and the ways in which bases may arise.References
- Klaus Ambos-Spies, Contiguous r.e. degrees, Computation and proof theory (Aachen, 1983) Lecture Notes in Math., vol. 1104, Springer, Berlin, 1984, pp.Β 1β37. MR 775707, DOI 10.1007/BFb0099477
- 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 K. Ambos-Spies and P. FejΓ©r, Degree theoretic splitting properties of recursively enumerable sets (to appear).
- C. J. Ash and R. G. Downey, Decidable subspaces and recursively enumerable subspaces, J. Symbolic Logic 49 (1984), no.Β 4, 1137β1145. MR 771782, DOI 10.2307/2274266
- J. C. E. Dekker, Countable vector spaces with recursive operations. I, J. Symbolic Logic 34 (1969), 363β387. MR 252228, DOI 10.2307/2270903
- Rod Downey, On a question of A. Retzlaff, Z. Math. Logik Grundlag. Math. 29 (1983), no.Β 4, 379β384. MR 715258, DOI 10.1002/malq.19830290605
- R. Downey, Co-immune subspaces and complementation in $V_{\infty }$, J. Symbolic Logic 49 (1984), no.Β 2, 528β538. MR 745380, DOI 10.2307/2274184
- R. G. Downey, A note on decompositions of recursively enumerable subspaces, Z. Math. Logik Grundlag. Math. 30 (1984), no.Β 5, 465β470. MR 766904, DOI 10.1002/malq.19840303002
- R. G. Downey, The degrees of r.e. sets without the universal splitting property, Trans. Amer. Math. Soc. 291 (1985), no.Β 1, 337β351. MR 797064, DOI 10.1090/S0002-9947-1985-0797064-9
- 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 β, Effective algebras and relational systems: coding properties, in preparation. β, Classification of degree classes associated with r.e. subspaces, preprint, 1986.
- R. G. Downey and M. Stob, Structural interactions of the recursively enumerable T- and w-degrees, Ann. Pure Appl. Logic 31 (1986), no.Β 2-3, 205β236. Special issue: second Southeast Asian logic conference (Bangkok, 1984). MR 854294, DOI 10.1016/0168-0072(86)90071-0
- 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
- David R. Guichard, Automorphisms of substructure lattices in recursive algebra, Ann. Pure Appl. Logic 25 (1983), no.Β 1, 47β58. MR 722168, DOI 10.1016/0168-0072(83)90053-2
- David R. Guichard, A note on $r$-maximal subspaces of $V_{\infty }$, Ann. Pure Appl. Logic 26 (1984), no.Β 1, 1β9. MR 739909, DOI 10.1016/0168-0072(84)90037-X L. Harrington, On Cooperβs proof of a theorem of Yates. I and II, handwritten notes, 1976.
- Iraj Kalantari and J. B. Remmel, Degrees of recursively enumerable topological spaces, J. Symbolic Logic 48 (1983), no.Β 3, 610β622. MR 716622, DOI 10.2307/2273453
- Iraj Kalantari and Allen Retzlaff, Maximal vector spaces under automorphisms of the lattice of recursively enumerable vector spaces, J. Symbolic Logic 42 (1977), no.Β 4, 481β491. MR 505385, DOI 10.2307/2271869
- A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537β569. MR 204282, DOI 10.1112/plms/s3-16.1.537
- 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, 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
- G. Metakides and A. Nerode, Recursion theory and algebra, Algebra and logic (Fourteenth Summer Res. Inst., Austral. Math. Soc., Monash Univ., Clayton, 1974) Lecture Notes in Math., Vol. 450, Springer, Berlin, 1975, pp.Β 209β219. MR 0371580
- G. Metakides and A. Nerode, Recursively enumerable vector spaces, Ann. Math. Logic 11 (1977), no.Β 2, 147β171. MR 446936, DOI 10.1016/0003-4843(77)90015-8
- 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
- A. Nerode and J. Remmel, Recursion theory on matroids, Patras Logic Symposion (Patras, 1980) Stud. Logic Found. Math., vol. 109, North-Holland, Amsterdam, 1982, pp.Β 41β65. MR 694252, DOI 10.1016/S0049-237X(08)71356-9
- A. Nerode and J. Remmel, Recursion theory on matroids, Patras Logic Symposion (Patras, 1980) Stud. Logic Found. Math., vol. 109, North-Holland, Amsterdam, 1982, pp.Β 41β65. MR 694252, DOI 10.1016/S0049-237X(08)71356-9
- A. Nerode and J. Remmel, A survey of lattices of r.e. substructures, Recursion theory (Ithaca, N.Y., 1982) Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, 1985, pp.Β 323β375. MR 791067, DOI 10.1090/pspum/042/791067
- Piergiorgio Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no.Β 1, 37β86. MR 590818, DOI 10.1090/S0273-0979-1981-14863-1
- J. Remmel, On r.e. and co-r.e. vector spaces with nonextendible bases, J. Symbolic Logic 45 (1980), no.Β 1, 20β34. MR 560222, DOI 10.2307/2273351
- J. B. Remmel, Recursion theory on algebraic structures with independent sets, Ann. Math. Logic 18 (1980), no.Β 2, 153β191. MR 578542, DOI 10.1016/0003-4843(80)90016-9
- Allen Retzlaff, Direct summands of recursively enumerable vector spaces, Z. Math. Logik Grundlagen Math. 25 (1979), no.Β 4, 363β372. MR 541687, DOI 10.1002/malq.19790251908
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Gerald E. Sacks, On the degrees less than 0β², Ann. of Math. (2) 77 (1963), 211β231. MR 146078, DOI 10.2307/1970214
- Richard A. Shore, Controlling the dependence degree of a recursively enumerable vector space, J. Symbolic Logic 43 (1978), no.Β 1, 13β22. MR 491092, DOI 10.2307/2271945
- 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
- Robert I. Soare, Tree arguments in recursion theory and the $0''β$-priority method, Recursion theory (Ithaca, N.Y., 1982) Proc. Sympos. Pure Math., vol. 42, Amer. Math. Soc., Providence, RI, 1985, pp.Β 53β106. MR 791052, DOI 10.1090/pspum/042/791052
- 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
- C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159β168. MR 205851, DOI 10.2307/2269807
Additional Information
- © Copyright 1987 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 302 (1987), 683-714
- MSC: Primary 03D45; Secondary 03D25, 03D30
- DOI: https://doi.org/10.1090/S0002-9947-1987-0891641-4
- MathSciNet review: 891641