# Independent Subset is Contained in Maximal Independent Subset

## Theorem

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

Let $A \subseteq S$.

Let $X \in \mathscr I$ such that $X \subseteq A$.

Then:

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

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

## Proof

By definition of the rank function on $M$:

$\size X \le \map \rho A$

### Case 1 : $\size X = \map \rho A$

Let $\size X = \map \rho A$.

Let $Y = X$ and the result follows.

$\Box$

### Case 2 : $\size X < \map \rho A$

Let $\size X < \map \rho A$.

By definition of the rank function on $M$:

$\map \rho A = \max \set{\size I : I \subseteq A \land I \in \mathscr I}$
$\exists Z \in \mathscr I : Z \subseteq A$ and $\size Z = \map \rho A$
$\exists Y' \subseteq Z \setminus X: \size {X \cup Y'} = \size Z$ and $X \cup Y' \in \mathscr I$

We have:

 $\ds Y'$ $\subseteq$ $\ds Z \setminus X$ $\ds$ $\subseteq$ $\ds Z$ Set Difference is Subset $\ds$ $\subseteq$ $\ds A$ by choice of $Z$
$X \cup Y' \subseteq A$

Let $Y = X \cup Y'$ and the result follows.

$\Box$

In either case, the result follows.

$\blacksquare$