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

From ProofWiki
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:

\(\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$