# Element of Matroid Base and Circuit has a Substitute/Lemma 2

## Theorem

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

Let $C \subseteq S$ be a dependent subset of $M$.

Let $x \in C$.

Let $X \subseteq S$ such that:

$\paren{ C \setminus \set x} \cup X \in \mathscr I$

Then:

$x \notin \paren{ C \setminus \set x} \cup X$

## Proof

$x \in \paren{ C \setminus \set x} \cup X$

Then:

$\set x, C \setminus \set x \subseteq \paren{ C \setminus \set x} \cup X$
$C \subseteq \paren{ C \setminus \set x} \cup X$
$C \in \mathscr I$

$C \notin \mathscr I$
$x \notin \paren{ C \setminus \set x} \cup X$
$\blacksquare$