# Bounds for Rank of Subset

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 $A \subseteq S$ be subset of $S$.

Then:

$0 \le \map \rho A \le \size A$

## Proof

By definition of the rank function:

 $\ds \map \rho A$ $=$ $\ds \max \set {\size X : X \subseteq A \land X \in \mathscr I}$
$\forall X \subseteq A : \size X \le \size A$

In particular:

$\forall X \subseteq A : X \in \mathscr I$ then $\size X \le \size A$
$\max \set {\size X : X \subseteq A \land X \in \mathscr I} \le \size A$
$\O \subseteq A$
$\size \O = 0$
$\O \in \mathscr I$
$0 \le \max \set {\size X : X \subseteq A \land X \in \mathscr I}$

It follows that:

$0 \le \map \rho A \le \size A$

$\blacksquare$