Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-22T06:44:41.469Z Has data issue: false hasContentIssue false
  • English
  • Français

Co-immune subspaces and complementation in V∞

Published online by Cambridge University Press:  12 March 2014

R. Downey
R. Downey*
Affiliation:
Monash University, Clayton, Victoria 3168, Australia Chisholm Institute of Technology, 900 Dandenong Road, Caulfield East, Victoria 3145, Australia
*
National University of Singapore, Kent Ridge, 0511, Singapore
Get access Rights & Permissions [Opens in a new window]

Abstract

We examine the multiplicity of complementation amongst subspaces of V∞. A subspace V is a complement of a subspace W if V ∩ W = {0} and (V ∪ W)* = V∞. A subspace is called fully co-r.e. if it is generated by a co-r.e. subset of a recursive basis of V∞. We observe that every r.e. subspace has a fully co-r.e. complement.

Theorem. If S is any fully co-r.e. subspace then S has a decidable complement.

We give an analysis of other types of complements S may have. For example, if S is fully co-r.e. and nonrecursive, then S has a (nonrecursive) r.e. nowhere simple complement.

We impose the condition of immunity upon our subspaces.

Theorem. Suppose V is fully co-r.e. Then V is immune iff there exist M1, M2 ∈ L(V∞), with M1supermaximal and M2k-thin, such that M1, ⊕ V = M2 ⊕ V = V∞.

Corollary. Suppose V is any r.e. subspace with a fully co-r.e. immune complement W(e.g., V is maximal or V is h-immune). Then there exist an r.e. supermaximal subspace M and a decidable subspace D such that V ⊕ W = M ⊕ W = D ⊕ W = V∞.

We indicate how one may obtain many further results of this type. Finally we examine a generalization of the concepts of immunity and soundness. A subspace V of V∞ is nowhere sound if (i) for all Q ∈ L(V∞) if Q ⊃ V then Q = V∞, (ii) V is immune and (iii) every complement of V is immune. We analyse the existence (and ramifications of the existence) of nowhere sound spaces.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 49 , Issue 2 , June 1984 , pp. 528 - 538
Copyright
Copyright © Association for Symbolic Logic 1984

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Crossley, J. N. and Nerode, A., Recursive equivalence on matroids, Aspects of effective algebra (Proceedings of a conference, Monash University, Clayton, 1979; Crossley, J. N., editor). ∀ Book Company, Yarro Glen, 1981, pp. 69–86.Google Scholar
[2]Dekker, J. C. E., Countable vector spaces with recursive operations. Part I, this Journal, vol. 34 (1969), pp. 363–387.Google Scholar
[3]Downey, R., Abstract dependence, recursion theory and the lattice of recursively enumerable filters, Ph.D. Thesis, Monash University, Clayton, 1982.CrossRefGoogle Scholar
[3a]Downey, R., On a question of A. Retzlaff, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 29 (1983), pp. 379–384.CrossRefGoogle Scholar
[4]Downey, R., Bases of supermaximal subspaces and Steinitz systems, this Journal (to appear).Google Scholar
[5]Downey, R., Nowhere simplicity in matroids, Journal of the Australian Mathematical Society Series A, vol. 35 (1983), pp. 28–45.CrossRefGoogle Scholar
[5a]Downey, R. and Remmel, J. B., The universal complementation property, this Journal (to appear).Google Scholar
[6]Guhl, R., Two types of recursively enumerable vector spaces, Ph.D. Thesis, Rutgers University, New Brunswick, N.J., 1973.Google Scholar
[7]Guichard, D., Automorphisms and large submodels in effective algebra, Ph.D. Thesis, University of Wisconsin, Madison, Wisconsin, 1982.Google Scholar
[8]Jockusch, C. G. Jr.The degrees of bi-immune sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 15 (1969), pp. 135–140.CrossRefGoogle Scholar
[9]Kalantari, I. and Retzlaff, A., Maximal vector spaces under automorphisms of the lattice of recursively enumerable vector spaces, this Journal, vol. 42 (1977), pp. 481–491.Google Scholar
[10]Metakides, G. and Nerode, A., Recursively enumerable vector spaces, Annals of Mathematical Logic, vol. 11 (1977), pp. 147–171.CrossRefGoogle Scholar
[11]Metakides, G. and Nerode, A., Recursion theory on fields and abstract dependence, Journal of Algebra, vol. 65 (1980), pp. 36–59.CrossRefGoogle Scholar
[11a]Nerode, A. and Smith, R., Undecidability of the lattice of recursively enumerable subspaces, Proceedings of the Third Brazilian Conference on Mathematical Logic (Arruda, A. I., da Costa, N. C. A. and Sette, M. A., editors), 1982, pp. 245–252.Google Scholar
[11b]Nerode, A. and Remmel, J. B., Recursion theory on matroids, Patras Logic Symposion 1980 (Metakides, G., editor), North-Holland, Amsterdam, 1982, pp. 41–65.CrossRefGoogle Scholar
[12]Remmel, J. B., On r.e. and co-r.e. vector spaces with nonextendible bases, this Journal, vol. 45 (1980), pp. 20–34.Google Scholar
[12a]Remmel, J. B., Maximal and cohesive vector spaces, this Journal, vol. 42 (1977), pp. 400–418.Google Scholar
[13]Shore, R. A., Nowhere simple sets and the lattice of recursively enumerable sets, this Journal, vol. 43 (1978), pp. 322–330.Google Scholar
[14]Shore, R. A., Controlling the dependence degree of a recursively enumerable vector space, this Journal, vol. 43 (1978), pp. 13–22.Google Scholar