# Size of Linearly Independent Subset is at Most Size of Finite Generator

## 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 1

We first consider the case where $L$ is finite.

Let $S \subseteq \N$ be the set of all $n \in \N$ such that:

where:

- $L \setminus F$ denotes the set difference between $L$ and $F$
- $\card L$ and $\card F$ denote the cardinality of $L$ and $F$ respectively.

We use the Principle of Finite Induction to prove that $S = \N$.

### Basis of the Induction

Let $\card {L \setminus F} \le 0$.

Then from Cardinality of Empty Set:

- $L \setminus F = \O$

By Set Difference with Superset is Empty Set:

- $L \subseteq F$

By Cardinality of Subset of Finite Set:

- $\card L \le \card F$

Hence:

- $0 \in S$

This is the basis for the induction.

### Induction Hypothesis

It is to be shown that if $k \in S$ where $k \ge 1$, then it follows that $k + 1 \in S$.

This is the induction hypothesis:

It is to be demonstrated that it follows that:

- For every finite generator $F$ of $V$, if $\card {L \setminus F} \le k + 1$, then $\card L \le \card F$

### Induction Step

This is the induction step:

Assume the induction hypothesis that $n \in S$.

Let $F$ be a finite generator of $V$ such that:

- $\card {L \setminus F} = n + 1$

Let $v \in L \setminus F$.

Let $L' = L \cap \paren {F \cup \set v}$.

- $L' \subseteq L$

By Subset of Linearly Independent Set is Linearly Independent, it follows that $L'$ is linearly independent over $R$.

Also by Intersection is Subset:

- $L' \subseteq F \cup \set v$

Therefore, by Vector Space has Basis Between Linearly Independent Set and Finite Spanning Set:

- there exists a basis $B$ of $V$ such that:
- $L' \subseteq B \subseteq F \cup \set v$

Since $v \notin F$ is a linear combination of $F$, it follows that $F \cup \set v$ is linearly dependent over $R$.

Therefore:

- $B \subsetneq F \cup \set v$

By Cardinality of Subset of Finite Set:

- $\card B < \card {F \cup \set v} = \card F + 1$

Hence:

- $\card B \le \card F$

We have that:

\(\ds \card {L \setminus B}\) | \(\le\) | \(\ds \card {L \setminus L'}\) | Relative Complement inverts Subsets and Cardinality of Subset of Finite Set | |||||||||||

\(\ds \) | \(=\) | \(\ds \card {L \setminus \paren {F \cup \set v} }\) | Set Difference with Intersection is Difference | |||||||||||

\(\ds \) | \(=\) | \(\ds \card {\paren {L \setminus F} \setminus \set v}\) | Set Difference with Union | |||||||||||

\(\ds \) | \(=\) | \(\ds n + 1 - 1\) | Cardinality of Set Difference with Subset | |||||||||||

\(\ds \) | \(=\) | \(\ds n\) |

Since $n \in S$:

- $\card L \le \card B \le \card F$

Hence:

- $n + 1 \in S$

and so the induction step has been completed.

- $L \setminus F \subseteq L$

From Subset of Finite Set is Finite:

- $L \setminus F$ is finite.

Therefore, we can apply the fact that $S = \N$ to conclude that:

- $\card L \le \card F$

Let $L$ be infinite.

Then by Set is Infinite iff exist Subsets of all Finite Cardinalities, there exists a finite subset $L' \subseteq L$ such that:

- $\card {L'} = \card F + 1$

By Subset of Linearly Independent Set is Linearly Independent, it follows that $L'$ is linearly independent over $R$.

It is proven above that this is impossible.

Hence the result.

$\blacksquare$

## Proof 2

Let $S \subseteq \N$ be the set of all natural numbers $n \in \N$ such that:

- For any finite generator $F$ of $V$ over $R$, if $\card {F \cap L} \ge n$, then $\card L \le \card F$.

It is to be demonstrated that $S = \N$.

That is, that $\card {F \cap L} \ge n \implies \card L \le \card F$ for all $n \in \N$.

By Intersection is Subset and Cardinality of Subset of Finite Set, we have $\card {F \cap L} \le \card F$.

Hence, it is vacuously true that $\card F + 1 \in S$.

Therefore, $S$ is non-empty.

From the well-ordering principle, $S$ has a smallest element $N$.

If $N = 0$, the theorem immediately follows.

Aiming for a contradiction, suppose $N \ge 1$.

Let $\card {F \cap L} \ge N - 1$.

If $L \subseteq F$, the theorem follows from Cardinality of Subset of Finite Set.

Otherwise, there exists a $v \in L$ such that $v \notin F$.

Let $F' = F \cup \set v$.

By Intersection is Subset, we have $F' \cap L \subseteq L$, so it follows by Subset of Linearly Independent Set is Linearly Independent that $F' \cap L$ is linearly independent over $R$.

Also, by Intersection is Subset:

- $F' \cap L \subseteq F'$

We have that $F'$ is a generator of $V$ over $R$.

By Vector Space has Basis Between Linearly Independent Set and Finite Spanning Set, there exists a basis $B$ for $V$ such that:

- $F' \cap L \subseteq B \subseteq F'$

Since $v \notin F$ is a linear combination of $F$, it follows that $F'$ is linearly dependent over $R$.

By the definition of a basis:

- $B \subsetneq F'$

By Cardinality of Subset of Finite Set and Cardinality is Additive Function:

- $\card B < \card {F'} = \card F + 1$

Hence:

- $\card B \le \card F$

We have that:

\(\ds \card {B \cap L}\) | \(\ge\) | \(\ds \card {\paren {F' \cap L} \cap L}\) | Set Intersection Preserves Subsets and Cardinality of Subset of Finite Set | |||||||||||

\(\ds \) | \(=\) | \(\ds \card {F' \cap L}\) | Intersection is Associative and Set Intersection is Idempotent | |||||||||||

\(\ds \) | \(=\) | \(\ds \card {\paren {F \cap L} \cup \paren {\set v \cap L} }\) | Intersection Distributes over Union | |||||||||||

\(\ds \) | \(=\) | \(\ds \card {\paren {F \cap L} \cup \set v}\) | Intersection with Subset is Subset | |||||||||||

\(\ds \) | \(\ge\) | \(\ds N\) | Cardinality is Additive Function |

Since $N \in S$, it follows by the definition of a basis that:

- $\card L \le \card B \le \card F$

Hence:

- $N - 1 \in S$

But this contradicts the assumption that $N$ is the smallest element of $S$.

Therefore:

- $N = 0$

Hence the result.

$\blacksquare$

## Proof 3

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$