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.):

  1. Set $j = 1$ and $Q = S$.
  2. 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)$.
  3. 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$.
  4. 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.


1 Answer 1


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.

  • $\begingroup$ Hello, I'm not OP, I have a question: you said: "it is perfectly possible to have a field which is infinite, but has no countably infinite subset." - this is astonishing, can you give an example? $\endgroup$
    – Pedro A
    Commented Aug 26, 2020 at 19:42
  • $\begingroup$ No, because the examples are not constructive (namely: AC, the Axiom of Choice, is consistent with ZF, so you can't "give example" to anything which directly contradicts AC). However I can describe it roughly, it is consistent that there is an algebraic closure of a finite field which does not have a countably infinite subset; and this property is preserved under finite products. So if $F$ is such algebraic closure, then $F^n$ is also without a countably infinite subset. (Note: in this situation the given finite field will have two non-isomorphic algebraic closures.) $\endgroup$
    – Asaf Karagila
    Commented Aug 26, 2020 at 19:46
  • $\begingroup$ hmmm, I don't know some of the terms you used, but then it seems that when you said "countably infinite subset" you meant "countably infinite subset with some property", right? I was surprised because I thought that whatever infinite set always had a countably infinite subset, and I read it as if you were contradicting this. $\endgroup$
    – Pedro A
    Commented Aug 26, 2020 at 19:51
  • $\begingroup$ No. I mean a countably infinite subset. Period. The point is that to prove that "every infinite set has a countably infinite subset" we need to use the axiom of choice. This means that in general we cannot provide an "explicit description" of a countably infinite subset, given an infinite set; but it also means that we can't provide an "explicit description of a counterexample" if all we know is that such counterexample exists. $\endgroup$
    – Asaf Karagila
    Commented Aug 26, 2020 at 19:53
  • $\begingroup$ Ah, I see! Amazing!! Thank you very much. $\endgroup$
    – Pedro A
    Commented Aug 26, 2020 at 20:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .