# Is the cardinality of linearly independent set always less than or equal to of a spanning set?

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.

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?

Thanks!

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

• 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! Commented Jul 9, 2017 at 20:16
• @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. Commented Jul 10, 2018 at 16:03
• @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/… Commented Jul 10, 2018 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|$.

• 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/…. Commented Jul 10, 2018 at 16:11
• Here where we use that $L$ is linearly independent? Commented Feb 13 at 13:11
• @MeetPatel It's necessary to have $L$ linearly independent to apply the finite case of the statement to subsets of $L$. Commented Feb 13 at 18:28