# Size of Linearly Independent Subset is at Most Size of Finite Generator/Proof 3

## Theorem

Let $R$ be a division ring.

Let $V$ be an $R$-vector space.

Let $F \subseteq V$ be a finite generator of $V$ over $R$.

Let $L \subseteq V$ be linearly independent over $R$.

Then:

$\size L \le \size F$

## Proof

Let $\alpha_1, \alpha_2, \ldots, \alpha_n$ be a generator of $V$.

Let $\xi_1, \xi_2, \ldots, \xi_r$ be a linearly independent set of elements of $V$.

Hence the sequence $\sequence {\xi_1, \alpha_1, \alpha_2, \ldots, \alpha_n}$ is a linearly dependent sequence of elements of $V$.

One of these elements, which cannot be $\xi_1$, is a linear combination of the preceding elements.

Let this elements be $\alpha_i$.

So we can omit $\alpha_i$ from that sequence, and the remaining set is still a generator of $V$.

Therefore $\xi_2$ is a linear combination of these.

Thus $\sequence {\xi_2, \xi_1, \alpha_1, \alpha_2, \ldots, \alpha_{i - 1}, \alpha_{i + 1}, \ldots, \alpha_n}$ is a linearly dependent sequence of elements of $V$.

Again, one of them is a linear combination of the preceding elements.

This cannot be $\xi_2$, as $\xi_2$ has no preceding elements.

Neither can it be $\xi_1$, as $\xi_1$ and $\xi_2$ are linearly independent.

Thus we can omit whichever $\alpha_j$ it is, and we have a new set which is a generator of $V$.

This consists of $\xi_1$, $\xi_2$ and whichever $n - 2$ of the remaining elements of $\set {\alpha_1, \alpha_2, \ldots, \alpha_n}$.

After $p$ such steps, we have a set which is a generator of $V$ which consists of:

$\xi_1, \xi_2, \ldots, \xi_p$ and $n - p$ of the elements of $\set {\alpha_1, \alpha_2, \ldots, \alpha_n}$.

Aiming for a contradiction, suppose suppose $n < r$.

Then when $p = n$, the remaining set which is a generator of $V$ consists of:

$\xi_1, \xi_2, \ldots, \xi_n$

and there is at least one more element $\xi_{n + 1}$.

This is a linear combination of $\set {\xi_1, \xi_2, \ldots, \xi_n}$.

But this contradicts the supposition that $\set {\xi_1, \xi_2, \ldots, \xi_n, \xi_{n + 1} }$ is a linearly independent set.

Hence, by Proof by Contradiction, $n \ge r$.

The result follows.

$\blacksquare$