Decidable Subspaces and Recursively Enumerable Subspaces
Ash, C. J. ; Downey, R. G.
J. Symbolic Logic, Tome 49 (1984) no. 1, p. 1137-1145 / Harvested from Project Euclid
A subspace $V$ of an infinite dimensional fully effective vector space $V_\infty$ 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_\infty$ are natural analogues of recursive subsets of $\omega$. The set of r.e. subspaces forms a lattice $L(V_\infty)$ and the set of decidable subspaces forms a lower semilattice $S(V_\infty)$. We analyse $S(V_\infty)$ and its relationship with $L(V_\infty)$. We show: Proposition. Let $U, V, W \in L(V_\infty)$ 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, $\mathrm{Th}(S(V_\infty))$, is undecidable. This contrasts sharply with the result for recursive sets. Finally we examine various generalizations of our results. In particular we analyse $S^\ast(V_\infty)$, that is, $S(V_\infty)$ modulo finite dimensional subspaces. We show $S^\ast(V_\infty)$ is not a lattice.
Publié le : 1984-12-14
Classification: 
@article{1183741693,
     author = {Ash, C. J. and Downey, R. G.},
     title = {Decidable Subspaces and Recursively Enumerable Subspaces},
     journal = {J. Symbolic Logic},
     volume = {49},
     number = {1},
     year = {1984},
     pages = { 1137-1145},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183741693}
}
Ash, C. J.; Downey, R. G. Decidable Subspaces and Recursively Enumerable Subspaces. J. Symbolic Logic, Tome 49 (1984) no. 1, pp.  1137-1145. http://gdmltest.u-ga.fr/item/1183741693/