Journal of Symbolic Logic 49 (4):1137-1145 (1984)

A subspace V of an infinite dimensional fully effective vector space V ∞ is called decidable if V is r.e. and there exists an r.e. W such that $V \oplus W = V_\infty$ . These subspaces of V ∞ are natural analogues of recursive subsets of ω. The set of r.e. subspaces forms a lattice L(V ∞ ) and the set of decidable subspaces forms a lower semilattice S(V ∞ ). We analyse S(V ∞ ) and its relationship with L(V ∞ ). We show: Proposition. Let U, V, W ∈ L(V ∞ ) where U is infinite dimensional and $U \oplus V = W$ . Then there exists a decidable subspace D such that U |oplus D = W. Corollary. Any r.e. subspace can be expressed as the direct sum of two decidable subspaces. These results allow us to show: Proposition. The first order theory of the lower semilattice of decidable subspaces, Th(S(V ∞ )), is undecidable. This contrasts sharply with the result for recursive sets. Finally we examine various generalizations of our results. In particular we analyse S * (V ∞ ), that is, S(V ∞ ) modulo finite dimensional subspaces. We show S * (V ∞ ) is not a lattice
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2274266
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,355
Through your library

References found in this work BETA

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
On a Question of A. Retzlaff.Rod Downey - 1983 - Mathematical Logic Quarterly 29 (6):379-384.
Recursively Enumerable Vector Spaces.G. Metakides - 1977 - Annals of Mathematical Logic 11 (2):147.
Direct Summands of Recursively Enumerable Vector Spaces.Allen Retzlaff - 1979 - Mathematical Logic Quarterly 25 (19‐24):363-372.
Direct Summands of Recursively Enumerable Vector Spaces.Allen Retzlaff - 1979 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 25 (19-24):363-372.

Add more references

Citations of this work BETA

Classifications of Degree Classes Associated with R.E. Subspaces.R. G. Downey & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 42 (2):105-124.
On Speedable and Levelable Vector Spaces.Frank A. Bäuerle & Jeffrey B. Remmel - 1994 - Annals of Pure and Applied Logic 67 (1-3):61-112.
Sound, Totally Sound, and Unsound Recursive Equivalence Types.R. G. Downey - 1986 - Annals of Pure and Applied Logic 31:1-20.
Bases of Supermaximal Subspaces and Steinitz Systems II.R. G. Downey - 1986 - Mathematical Logic Quarterly 32 (13‐16):203-210.

Add more citations

Similar books and articles


Added to PP index

Total views
46 ( #248,142 of 2,519,631 )

Recent downloads (6 months)
1 ( #406,756 of 2,519,631 )

How can I increase my downloads?


My notes