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 ∅′∅′;(2)Every infinite/cofinite dimensional proper subspace computes Turing's Halting Set ∅′∅′;(3)There exists x∈Vx∈V such that every infinite dimensional proper subspace not containing x   computes Turing's Halting Set ∅′∅′;(4)Every infinite dimensional proper subspace computes Turing's Halting Set ∅′∅′. 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 König'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 (∀V)[X(V)→A(V)](∀V)[X(V)→A(V)] and (∀V)[X(V)→B(V)](∀V)[X(V)→B(V)], that each imply ACA0ACA0 over RCA0RCA0, but such that the seemingly weaker statement (∀V)[X(V)→A(V)∨B(V)](∀V)[X(V)→A(V)∨B(V)] is provable via WKL0WKL0 over RCA0RCA0. 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.