Equivalence of Definitions of Matroid/Definition 1 implies Definition 2
Jump to navigation
Jump to search
Theorem
Let $M = \struct {S, \mathscr I}$ be an independence system.
Let $M$ also satisfy:
\((\text I 3)\) | $:$ | \(\ds \forall U, V \in \mathscr I:\) | \(\ds \size V < \size U \implies \exists x \in U \setminus V : V \cup \set x \in \mathscr I \) |
Then $M$ satisfies:
\((\text I 3')\) | $:$ | \(\ds \forall U, V \in \mathscr I:\) | \(\ds \size U = \size V + 1 \implies \exists x \in U \setminus V : V \cup \set x \in \mathscr I \) |
Proof
Since:
- $\forall U, V \in \mathscr I : \size U = \size V + 1 \implies \size V < \size U$
If follows that if $M$ satisfies condition $(\text I 3)$ then $M$ satisfies condition $(\text I 3')$.
$\blacksquare$