I am trying to prove (or disprove) this statement:

Let $V$ be a vector space, and let $L,S\subseteq V$. If $L$ is linearly independent and $\text{span}(S)=V$, then $|L|\leq |S|$.

Is this statement true? I have consulted many linear algebra books, but they only provide the proof under the additional assumption that $L$ and $S$ are finite. The proof of the finite case goes like this: we assume for the sake of contradiction that $|L|>|S|$, then we repeatedly substitute elements of $S$ by elements of $L$ until $S$ is exhausted before $L$ and thus we arrive at a contradiction.

I think, in essence, they prove it by using Recursion theorem. I have been trying to generalize this by using Transfinite Recursion, but there are some difficulties, like how to recursively define the operation to iterate which is a bit different from the finite case which does not involve infinite ordinals.

I have also read this:

Infinite dimensional vector space. Linearly independent subsets and spanning subsets

but it's mainly focused on a special case and dependency on Axiom of Choice. Can anyone hint me this statement's truth value? or where to find them?



It is true. It is a consequence of this reference: Bourbaki, Algebra, Ch. II, Linear Algebra, §7, Vector Spaces, n°1, theorem 2.

Given a generating system $S$ of a vector space $E$ over a field $L$ and a free subset $L$ of $E$ contained in $S$, there exists a basis $B$ of $E$ such that $L\subset B\subset S$.

The proof is rather short and relies on Zorn's lemma.

With your hypotheses, $L$ is not contained in $S$, but consider $S'=S\cup L$ and apply the above theorem.

  • $\begingroup$ So, the argument goes like this? Since $L$ is linearly independent, $L\subseteq B_1$ for some basis $B_1$. Since $S$ spans $V$, $B_2\subseteq S$ for some basis $B_2$. Since $|B_1|=|B_2|$, we have $|L|\leq |B_1|=|B_2|\leq |S|$. wow, thanks! $\endgroup$ – Tommjjerry Jul 9 '17 at 20:16
  • $\begingroup$ @Bernard How is your argument supposed to work? You get a basis $B$ such that $L \subseteq B \subseteq S \cup L$. So you know $|L| \leq |S \cup L|$, which was already clear. $\endgroup$ – MichaelGaudreau Jul 10 '18 at 16:03
  • $\begingroup$ @Tommjjerry But how do you prove $|B_1|=|B_2|$? It's equivalent to the Boolean Prime Ideal Theorem. Moreover, the standard proof is basically Daniel Scheper's argument, which uses that the cardinality of $X$ is equal to the cardinality of the set of finite subsets of $X$ whenever $X$ is infinite (which I would think requires at least Boolean Prime Ideal Theorem). See math.stackexchange.com/questions/27096/… $\endgroup$ – MichaelGaudreau Jul 10 '18 at 16:21

For each element of $L$, choose an expression as a (finite) linear combination of elements of $S$. If $|S|$ is infinite, the number of finite subsets of $S$ is equal to $|S|$. Now, for each such finite subset $E$ of $S$, the number of elements of $L$ using exactly the elements of $E$ in their chosen expressions is at most $|E| < \aleph_0$ by the finite case of the statement. Therefore, $|L| \le \aleph_0 |S| = |S|$.

  • $\begingroup$ I think the assertion "If |S| is infinite, the number of finite subsets of S is equal to |S|" requires the axiom of choice or at least Boolean Prime Ideal Theorem. It is implied by that statement that "for every infinite set $S$, $|S|=|S \times S|$" which is equivalent to the axiom of choice. See math.stackexchange.com/questions/27096/…. $\endgroup$ – MichaelGaudreau Jul 10 '18 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.