Independent Subset is Base if Cardinality Equals Rank of Matroid
Jump to navigation
Jump to search
Theorem
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $\rho: \powerset S \to \Z$ be the rank function of $M$.
Let $B \in \mathscr I$ such that:
- $\size B = \map \rho S$
Then:
- $B$ is a base of $M$.
Corollary
Let $B \subseteq S$ be a base of $M$.
Let $X \subseteq S$ be any independent subset of $M$.
Let $\card X = \card B$.
Then:
- $X$ is a base of $M$.
Proof
Let $Z \in \mathscr I$ such that:
- $B \subseteq Z$
From Cardinality of Subset of Finite Set:
- $\size B \le \size Z$
By definition of the rank function:
- $\size Z \le \map \rho S$
Then:
- $\size Z = \size B$
From the contrapositive statement of Cardinality of Proper Subset of Finite Set:
- $B = Z$
It follows that $B$ is a maximal independent subset by definition.
That is, $B$ is a base by definition.
$\blacksquare$