Leigh.Samphier/Sandbox/Independent Superset of Dependent Set Minus Singleton Doesn't Contain Singleton

Theorem

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

Let $C$ be a dependent subset of $M$.

Let $x \in S$.

Let $X$ be an independent subset of $M$ such that:

$C \setminus \set x \subseteq X$.

Then:

$x \notin X$

Proof

We prove the contrapositive statement:

$x \in X \implies X$ is a dependent subset.

Let $x \in X$.

We have:

\(\displaystyle \paren{C \setminus \set x} \cup \set x\)

\(\subseteq\)

\(\displaystyle X\)

Union of Subsets is Subset

\(\displaystyle \leadsto \ \ \)

\(\displaystyle C \cup \set x\)

\(\subseteq\)

\(\displaystyle X\)

Set Difference Union Second Set is Union

\(\displaystyle \leadsto \ \ \)

\(\displaystyle C\)

\(\subseteq\)

\(\displaystyle X\)

Set is Subset of Union

From Superset of Dependent Set is Dependent:

$X$ is a dependent subset

$\blacksquare$