Superset of Dependent Set is Dependent
Jump to navigation
Jump to search
Theorem
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $A, B \subseteq S$ such that $A \subseteq B$
If $A$ is a dependent subset then $B$ is a dependent subset.
Corollary
Let $A \subseteq S$.
Let $x \in A$.
If $x$ is a loop then $A$ is dependent.
Proof
From the contrapositive statement of matroid axiom $(\text I 2)$:
- $A \notin \mathscr I \implies B \notin \mathscr I$
By the definition of a dependent subset:
- If $A$ is not an dependent subset then $B$ is not an dependent subset.
$\blacksquare$