Finding a basis of an infinite-dimensional vector space?

The other day, my teacher was talking infinite-dimensional vector spaces and complications that arise when trying to find a basis for those. He mentioned that it's been proven that some (or all, do not quite remember) infinite-dimensional vector spaces have a basis (the result uses an Axiom of Choice, if I remember correctly), that is, an infinite list of linearly independent vectors, such that any element in the space can be written as a finite linear combination of them. However, my teacher mentioned that actually finding one is really complicated, and I got a sense that it was basically impossible, which reminded me of Banach-Tarski paradox, where it's technically 'possible' to decompose the sphere in a given paradoxical way, but this cannot be actually exhibited. So my question is, is the basis situation analogous to that, or is it actually possible to explicitly find a basis for infinite-dimensional vector spaces?

• I deleted my answer, since it wasn't really on point. The Axiom of choice is equivalent to the statement that every vector space has a basis. As far as constructions go, you might find this interesting scribd.com/doc/51294578/33/Hamel-basis – David Mitra Nov 29 '11 at 17:12
• In the general case we cannot construct a basis, in any generally accepted interpretation of the word construct. A basis is anyway often not what we need. For power series or Fourier series, we are interested in representations as infinite sums. – André Nicolas Nov 29 '11 at 17:32
• It is possible to explicitly find a basis for some infinite-dimensional vector spaces. For example the space of real polynomials in one variable. But it is not possible for other spaces. For example Hilbert space $l^2$. – GEdgar Nov 29 '11 at 18:53
• Every vector space has a basis. Search on "Hamel basis" for the general case. The problem is that they are hard to find and not as useful in the vector spaces we're more familiar with. In the infinite-dimensional case we often settle for a basis for a dense subspace. – Chris Godsil Nov 30 '11 at 4:18
• – Watson Feb 18 '18 at 10:03

It's known that the statement that every vector space has a basis is equivalent to the axiom of choice, which is independent of the other axioms of set theory. This is generally taken to mean that it is in some sense impossible to write down an "explicit" basis of an arbitrary infinite-dimensional vector space. On the other hand,

• Some infinite-dimensional vector spaces do have easily describable bases; for example, we are often interested in the subspace spanned by a countable sequence $v_1, v_2, ...$ of linearly independent vectors in some vector space $V$, and this subspace has basis $\{ v_1, v_2, ... \}$ by design.
• For many infinite-dimensional vector spaces of interest we don't care about describing a basis anyway; they often come with a topology and we can therefore get a lot out of studying dense subspaces, some of which, again, have easily describable bases. In Hilbert spaces, for example, we care more about orthonormal bases (which are not Hamel bases in the infinite-dimensional case); these span dense subspaces in a particularly nice way.
• Hmm, this whole question seems relevant for the subject of analysis of iteration of functions using Carleman-matrices. Iteration of functions, given their formal power series is then understood by powers of that matrices and the analytical expression of its entries. The idea of fractional powers (and thus fractional functional iteration) is then introduced by assumtion of the possibility of diagonalization or logarithmizing of such infinite matrices. Here your (Qiaochu's) contribution gets me burningly interested since I've not yet found much which is focused on this problem/idea... – Gottfried Helms Jan 20 '12 at 19:39
• ...(continued). How could I extract valuable information for that problem (for which I feel your statements could be an entry point)? Perhaps make it an explicite question? But it seems to me that my questions would to be too broad and unspecific? – Gottfried Helms Jan 20 '12 at 19:41
• @Gottfried: I don't understand what you're talking about (since I don't know what a Carleman matrix is), nor do I understand how what I wrote is relevant to it. Feel free to post a separate question with more detail, though. – Qiaochu Yuan Jan 20 '12 at 19:47
• Qiaochu, to ask such a question makes me feel like asking for some linguistic details in a language in which I'm rather able to call for a taxi... or to ask a medieval theologist in latin for some religious basic fact, where I'm only used to do good and deep prayers.:-) Hmm, I'll try my best. So far, if the vectors $\small v_0,v_1,v_2,\ldots$ contain the coeffs of the formal power series for, say, $\small f(x)=\exp(x)-1$ and $\small v_0,v_1,v_2,\ldots$ for $\small f(x)^0,f(x),f(x)^2,\ldots$ (powers,not iterations) then $\small V$ is the en.wikipedia.org/wiki/Carleman_matrix – Gottfried Helms Jan 20 '12 at 20:20
• ... and for triangular $\small V$ as in this case the coeffs of the formal power series for the functional iterates are taken from the second column of the powers of $\small V$. For triangular matrices these are also handled under the name of "Bell-matrix". For non-triangular matrices they are used under the name of "Carleman"-matrix. The assumtion of the possibility of diagonalization (and fractional powers) implies then also the assumtion that we have a meaningful representation of an infinite vectorspace, if I understand things correctly. – Gottfried Helms Jan 20 '12 at 20:27

The "hard case" is essentially equivalent to this one:

Find a basis for the real numbers $\mathbb{R}$ over the field of the rational numbers $\mathbb{Q}$.

The reals are obviously an extension field of the rationals, so they form a vector space over $\mathbb{Q}$. It should be clear that such a basis has to be uncountable (for if it were countable, the reals would likewise also be countable).

It should also be clear that such a basis is a subset of $\{1\} \cup \mathbb{R} \setminus \mathbb{Q}$. The trouble is, that the power set of the reals is "so big" that it's not even clear how to name the sets we need to apply the axiom of choice TO. Linearly independent subsets however, DO satisfy the requirements for Zorn's Lemma, a form of the Axiom of Choice.

A relatively easy-to-follow proof of the existence of a basis for any vector space using Zorn's Lemma can be found here: http://planetmath.org/encyclopedia/EveryVectorSpaceHasABasis.html