# An infinite generating set of a finite dimensional vector space contains a basis

Let $S$ be an infinite generating set of a finite dimensional vector space , then how do we prove that there is a subset of $S$ which is a basis of the vector space ?

-

You can pick vectors $v_1,v_2,\dots$ out of $S$ such that the elements of $\{v_1,\dots v_k\}$ are independent for $k=1,2,\dots$. That comes to an end because the space has finite dimension. If it can be done for $k=n$ and not for $k=n+1$ then $v_1,\dots v_n$ form a basis, because $S$ is generating.

-

You don't even need the fact that the set is infinite. You just need the fact that it is a generating set.

Since the dimension is finite, denote the dimension by $n$, then pick any nonzero vector $v_0$ from $S$, next pick $v_1\in S\setminus\operatorname{span}(\{v_0\})$, and continue by picking $v_k$ to be an arbitrary vector in $S\setminus\operatorname{span}(\{v_0,\ldots,v_{k-1}\})$.

It is immediate that for every $k$ that this process can get to, the set $\{v_0,\ldots,v_{k-1}\}$ is linearly independent. Therefore this process can continue only up to $k=n$, at which point we have selected $v_0,\ldots,v_{n-1}$ vectors which are linearly independent, so they must form a basis.

(Of course this uses the fact that all bases of a finite dimensional vector space have the same size as the dimension.)

To do the same thing for an infinite dimensional vector space, one would have to use the axiom of choice, and proceed by transfinite induction. Other approaches would be to use Zorn's lemma.

It might be interesting to point out that the statement "In every vector space, every spanning set contains a basis" is in fact equivalent to the axiom of choice.

-

A formal proof can be constructed using Zorn's lemma (and it isn't even neccessary for V to be finite-dimensional). Essentially it is the same as proving that every (possibly infinite dimensional) vector space has a basis. Show that a basis B can be created for S, then since S spans V, B is also a basis for V.

With S as a the generating set, consider L, the set of linearly independent subsets of S. Such sets certainly exist as we can take any single (non-zero) vector from S and it forms a linearly independent subset of S.

Being comprised of sets, L can be partially ordered by inclusion and we can consider chains (i.e. sequences of sets each included in the next) in L. Let C be such a chain.

The union of elements of a chain, ∪C, is an upper bound for the chain (i.e. it includes all elements of the chain). Now show that ∪C is linearly independent and therefore an element of L.

Consider any finite subset D ⊂∪C. Consider any two of its elements d1 and d2. They must be elements of linearly independent sets C1 and C2 which are elements of the chain C. Since C is a chain either C1 ⊂ C2 or vice versa and therefore d1 and d2 are elements of the same linearly independent set (say) C2. Since D is a finite set, we can proceed iteratively through its elements establishing that d3 is in the same C3 as d1 and d2. Ultimately, D is a subset of some Ci and since Ci is linearly independent so too must D be. So we establish that any finite subset of ∪C is linearly independent and hence that ∪C is linearly independent.

That establishes the conditions for Zorn's Lemma to apply, i.e. every chain in L has an upper bound in L. So from Zorn's Lemma we know that L has a maximal element, say B.

We claim that B is a basis, i.e. that it spans S (BL so we already know that it is linearly independent).

Suppose not, then there is some v ∈ S which is not a linear combination of a finite subset of the elements of B. Then B ' = B ∪ {v} is a linearly independent set, so B ' ∈ L and BB' contradicting B being maximal. So by contradiction, B is a basis for S.

-
Talk about an overkill. :-) –  Asaf Karagila Apr 18 at 10:01
I already had the proof typed up - you don't like it ? –  Tom Collinge Apr 18 at 10:08
No complaints about the proof. But just because something is infinite it doesn't mean we have to use Zorn's lemma! :-) –  Asaf Karagila Apr 18 at 10:11
Agreed. It isn't neccessary for a finite dimensional space (but perhaps interesting to see the more general proof). –  Tom Collinge Apr 18 at 11:15