Let $n$ and $m$ be positive integers, let $V$ be a finite-dimensional vector space, let $S = (s_1, \dots, s_n)$ be an ordered list (a sequence) of vectors from $V$ such that $S$ spans $V$, and let $L = (\ell_1, \dots, \ell_m)$ be a linearly independent list of vectors in $V$. Then no matter what, $m \leq n$; i.e. every finite linearly independent list is shorter than every finite spanning list.
I want to prove that it is impossible for $L$ to be an infinite sequence. I think the algorithm below will work; when $j = n + 1$, there will be a contradiction in step 3 that $(s_\alpha, \dots, s_\beta)$ is empty. But could it also follow from the theorem? More specifically, suppose $L$ is an infinite sequence. Then $L$ contains a finite, linearly independent sequence of length $m + 1$, which is a contradiction.
My question: does that last sentence rely on the axiom of choice in some way? And is there a simpler proof that no infinite sequence can be linearly independent in a finite dimensional vector space?
Algorithm (from Axler, The length of every linearly independent list of vectors is less than or equal to the length of every spanning list of vectors.):
- Set $j = 1$ and $Q = S$.
- Claim: for some subsequence $(s_\alpha, \dots, s_\beta)$ of $S$, $Q = (\ell_1, \dots, \ell_{j - 1}, s_{\alpha}, \dots, s_{\beta})$. Also, $Q$ contains $n$ vectors, and $\ell_j \in V = \text{span}(Q)$.
- It follows that $Q' = (\ell_1, \dots, \ell_{j - 1}, \ell_j, s_\alpha, \dots, s_\beta)$ is linearly dependent. Therefore, some vector in $Q'$ is in the span of the preceding vectors in the list. This cannot be a vector in $L$, since the subsequence $(\ell_1, \dots, \ell_j)$ of $L$ is linearly independent, so $(s_\alpha, \dots, s_\beta)$ is nonempty and contains a redundant vector $s_\gamma$.
- Set $Q = Q' \setminus (s_\gamma)$, so $Q$ contains $n$ vectors, including $(\ell_1, \dots, \ell_j)$. If $j = m$, we are done. Else set $j = j + 1$ and go to Claim 1.
The algorithm terminates since $m$ is finite.
No. Much like how the axiom of choice is not involved in the statement "a subset of a finite set is finite".
But to your specific question, every infinite set contains finite sets of arbitrarily large cardinality. Otherwise, $A$ is an infinite set, and $B$ is a maximal finite subset, so $B\subsetneq A$, since one is finite and the other is not; but then take any $a\in A\setminus B$, and consider $B\cup\{a\}$, which is a strictly larger finite subset of $A$.
So in particular, if $M$ is linearly independent and infinite, it contains arbitrarily large subsets which are, well, linearly independent.
The only one thing you need to make sure, though, is that when you consider your infinite set of vectors, it is not "a list" which somehow implies that you think about it as indexed by $\Bbb N$. It is perfectly possible to have a field (and a finite dimensional vector space over it) which is infinite, but has no countably infinite subset.
Nevertheless, the question is about infinite subsets. Not infinite lists. So this is a minor point on your choice of language.