Dependent Subset of Independent Set Union Singleton Contains Singleton
Jump to navigation
Jump to search
Theorem
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $X$ be an independent subset of $M$.
Let $x \in S$.
Let $C$ be a dependent subset of $M$ such that:
- $C \subseteq X \cup \set x$.
Then:
- $x \in C$
Proof
From the contrapositive statement of Superset of Dependent Set is Dependent:
- $C \not \subseteq X$
From the contrapositive statement of Set Difference with Superset is Empty Set:
- $C \setminus X \ne \O$
From Set Difference over Subset:
- $C \setminus X \subseteq \paren{X \cup \set x} \setminus X = \set x$
From Power Set of Singleton:
- $C \setminus X = \set x$
From Set Difference is Subset:
- $\set x \subseteq C$
From Singleton of Element is Subset:
- $x \in C$
$\blacksquare$