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

From ProofWiki
Jump to navigation Jump to search


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$.


$x \notin X$


We prove the contrapositive statement:

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

Let $x \in X$.

We have:

\(\ds \paren{C \setminus \set x} \cup \set x\) \(\subseteq\) \(\ds X\) Union of Subsets is Subset
\(\ds \leadsto \ \ \) \(\ds C \cup \set x\) \(\subseteq\) \(\ds X\) Set Difference Union Second Set is Union
\(\ds \leadsto \ \ \) \(\ds C\) \(\subseteq\) \(\ds X\) Set is Subset of Union

From Superset of Dependent Set is Dependent:

$X$ is a dependent subset