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

From ProofWiki
Jump to navigation Jump to search

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