Independent Subset is Base if Cardinality Equals Rank of Matroid

From ProofWiki
Jump to navigation Jump to search


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$


$B$ is a base of $M$.


Let $B \subseteq S$ be a base of $M$.

Let $X \subseteq S$ be any independent subset of $M$.

Let $\card X = \card B$.


$X$ is a base of $M$.


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$


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