# Linear algebra proof involving basis

Suppose $V$ is a vector space of dimension $n$ and $S$ is a subset of $V$ such that $\operatorname{span}(S)=V$. Prove there exists a basis for $V$ in $S$ without assuming $S$ is a finite set.

I'm not sure what direction to take when $S$ is infinite. I know a bunch of facts. I ultimately want to show that it's possible to pick a finite subset of $S$ that generates $V$ and is linearly independent.

-
The key property to use is that only finitely many vectors are involved in a given linear combination. –  Qiaochu Yuan Sep 7 '12 at 3:46

Inductively: choose $\,0\neq s\in S\,$ (why is there such a non-zero element?), and use the following (after, I presume, you properly prove it):

Theorem: Let $\,W\,$ be any vector space, $\,A\subset W\,$ a linearly independent set. Then, for any

$$w\in W\,\,\,,\,\,w\in Span A\Longleftrightarrow A\cup \{w\}\,\,\text{ is linearly *dependent*}$$

So, if there's some $\,s'\in S\,\,s.t.\,\,s'\notin Span\{s\}\,$ , then by the above $\,\{s,s'\}\,$ is linearly independent.

Continue in this fashion and, after at most $\,n\,$ steps, you'll get a basis (why?)

-

Let $B$ be a basis of $V$. Each element of $B$ is generated by $S$. That means there exists finite subset $T$ of $S$ such that $B \subseteq span(T)$. Make $T$ linearly independent by removing some elements. Then the final $T$ is your answer.

-