Degrees of splittings and bases of recursively enumerable subspaces

Downey, R. G.; Remmel, J. B.; Welch, L. V.

doi:10.1090/S0002-9947-1987-0891641-4

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

Trans. Amer. Math. Soc. 302 (1987), 683-714

DOI: https://doi.org/10.1090/S0002-9947-1987-0891641-4

PDF | 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

Degree theoretic splitting properties of recursively enumerable sets

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

Classification of degree classes associated with r.e. subspaces

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

On Cooper’s proof of a theorem of Yates

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

AMS Website Down

Transactions of the American Mathematical Society

Degrees of splittings and bases of recursively enumerable subspaces
HTML articles powered by AMS MathViewer

Abstract: