1
$\begingroup$

Consider the following claim: Let $V$ be a vector space and let $A,B\subseteq V$ be two independent sets with $|A|<|B|<\infty $. Then there exists $b\in B$ such that $A\cup \{b\}$ is independent.

Can anyone prove this claim without using matrices?

  • 0
    The basic result here is the (Steinitz) *Exchange Lemma*. A web search should turn up much, including that it generalizes from *linear* dependence to *abstract dependence relations* (e.g. *algebraic* dependence), cf. *matroid* theory.2012-06-13

3 Answers 3

1

Since $\,|A|<|B|\,\,$ and both are lin. independent set, we get that $\dim \operatorname{Span}(A)<\dim\operatorname{Span}(B)\,\,(**)$

Now, we know that for any vector $\,v\in V\,\,,\,v\in\operatorname{Span}(A)\Longleftrightarrow A\cup\{v\}\,\text{is linearly dependent}$

So if $\forall b\in B\,,\,A\cup\{b\}\,\text{is linearly dependent, then} \forall b\in B\,,\,b\in\operatorname{Span}(A)$ which contradicts (**) above

  • 0
    Perhaps for you, @Shay. I didn't studied and learnt about dimension by means of this question or something like this, though perhaps The Replacement Theorem could be applied to both.2012-06-13
1

Assume not:

Then if $|A| = n$, $|B| \geq n+1$, choose $n+1$ (linearly independent) elements $b_1, b_2, ..., b_{n+1}$ elements of $B$. If all $n+1$ elements are dependent with $A$, then the $n$ elements spanning $A$ span a $(n+1)$-dimensional space. Contradiction.

  • 0
    How do you prove that n elements can not span n+1 independent element? This is the essence of the question... Also note that the fact we need to prove in this question is used to define the concept of dimension...2012-06-13
0

I guess you can reduce to the case in which $|A| = |B|-1$, and then to the case $|A|=1$ and $|B|=2$. You can just add a vector $b$ to $A$ so that $\operatorname{span}\{A,b\}$ is a base for $B$.