Superset of Dependent Set is Dependent

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