Leigh.Samphier/Sandbox/Set Difference of Matroid Circuit with Element is Independent

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $C \subseteq S$ be a circuit of $M$.

Let $x \in C$.


Then:

$C \setminus \set x$ is an independent subset of $C$


Proof

From Set Difference is Subset:

$C \setminus \set x \subseteq C$

Because $x \in C$ and $x \notin C \setminus \set x$:

$C \setminus \set x \ne C$

Hence:

$C \setminus \set x \subsetneq C$

By definition of circuit:

$C$ is a minimal dependent subset

Hence:

$C \setminus \set x \in \mathscr I$

$\blacksquare$