We are given a vector space $V$ with $dim(V)=n$. Also some $S\subseteq V$ generates $V$, i.e. $span(S)=V$
We need to prove that some subset of $S$ is a basis for $V$.
Now, if $S$ was a finite set, it's a matter of choosing vectors appropriately, i.e. we pick vectors one by one from $S$ checking whether it is a linear combination of the previous one.
But what if $S$ was infinite ?
Algorithmically speaking, we could be searching indefinitely until we have exactly $n$ linearly independent vectors that could form the basis for for $V$.
As Joey Tribbiani said and I quote : "There's gotta be a better way ! "
Can anyone help ?
Let $S$ be a set such that $span(S) = V$.
We will describe a process that gets you to a basis of $V$ with elements in $S$.
Pick $s_1 \in S, s_1 \neq 0$ and now consider $S_1 = S\setminus span(\{s_1\})$.
If $dim V > 1$ then $S \neq \emptyset$, is that clear to you?
Proceed iteratively... Assuming $s_k$ has been picked, we pick $s_{k+1} \in S_k, s_{k+1} \neq 0$ and set $S_{k+1} = S_k \setminus span\{s_1, \cdots, s_k, s_{k+1}\}$.
Keep going until $S_t = \emptyset$. You should have $t = n$ and the $\{s_1, s_2, \cdots, s_n\}$ should form a basis of $V$. Can you show that this set is, indeed, a basis for $V$?