Infinite dimensional proper subspaces of computable vector spaces

This article examines and distinguishes different techniques for coding incomputable information into infinite dimensional proper subspaces of a computable vector space, and is divided into two main parts. In the first part we describe different methods for coding into infinite dimensional subspaces. More specifically, we construct several computable infinite dimensional vector spaces each of which satisfies one of the following: (1) Every infinite/coinfinite dimensional subspace computes Turing's Halting Set empty set(0); (2) Every infinite/cofinite dimensional proper subspace computes Turing's Halting Set empty set(0)'; (3) There exists x E V such that every infinite dimensional proper subspace not containing x computes Turing's Halting Set empty set (0)'; (4) Every infinite dimensional proper subspace computes Turing's Halting Set empty set (0)'. Vector space (4) generalizes vector spaces (1) and (2), and its construction is more complicated. The same simple and natural technique is used to construct vector spaces (1) (3). Finally, we examine the reverse mathematical implications of our constructions (1)-(4). In the second part we examine the limitations of our simple and natural method for coding into infinite dimensional subspaces described in the previous paragraph. In particular, we prove that our simple and natural coding technique cannot produce a vector space of type (4) above, and that any vector space of type (4) must have densely many (from a certain point of view) finite dimensional computable subspaces. In other words, the construction of a vector space of type (4) is necessarily more complicated than the construction of vector spaces of types (1) (3). We also introduce a new statement (in second order arithmetic) about the existence of infinite dimensional proper subspaces in a restricted class of vector spaces related to (1) (3) above and show that it is implied by weak Konig's lemma in the context of reverse mathematics. In the context of reverse mathematics this gives rise to two statements from effective algebra about the existence of infinite dimensional proper subspaces (for a certain class of vector spaces) of the form (for all V) [X(V) -> A(V)] and (for all V)[X(V) -> B(V)], that each imply ACA(0) over RCA(0), but such that the seemingly weaker statement (for all V) [X(V) -> A(V) V B(V)] is provable via WKL0 over RCA(0). Furthermore, we highlight some general similarities between constructing of infinite dimensional proper subspaces of computable vector spaces and constructing solutions to computable instances of various combinatorial principles such as Ramsey's Theorem for pairs. (C) 2014 Elsevier Inc. All rights reserved.