Superset of Dependent Set is Dependent/Corollary
< Superset of Dependent Set is Dependent(Redirected from Set is Dependent if Contains Loop)
Jump to navigation
Jump to search
Theorem
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $A \subseteq S$.
Let $x \in A$.
If $x$ is a loop then $A$ is dependent.
Proof
Let $x$ be a loop.
By definition of a loop:
- $\set x \notin \mathscr I$
By definition of a dependent subset:
- $\set x$ is a dependent subset
From Singleton of Element is Subset:
- $\set x \subseteq A$
From Superset of Dependent Set is Dependent:
- $A$ is a dependent subset
$\blacksquare$
Sources
- 1976: Dominic Welsh: Matroid Theory ... (previous) ... (next) Chapter $1.$ $\S 4.$ Loops and parallel elements