Leigh.Samphier/Sandbox/Independent Superset of Dependent Set Minus Singleton Doesn't Contain Singleton
Jump to navigation
Jump to search
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:
\(\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
$\blacksquare$