Leigh.Samphier/Sandbox/Independent Subset is Contained in Maximal Independent Subset/Corollary

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $M = \struct{S, \mathscr I}$ be a matroid.

Let $A \subseteq S$.

Let $X$ be a maximal independent subset of $A$.


Then:

$\card X = \map \rho A$

where $\rho$ is the rank function on $M$.


Proof

From Independent Subset is Contained in Maximal Independent Subset:

$\exists Y \in \mathscr I : X \subseteq Y \subseteq A : \card Y = \map \rho A$

By definition of a maximal independent Subset of $A$:

$X = Y$

The result follows.

$\blacksquare$