Equivalence of Definitions of Matroid/Definition 3 implies Definition 1
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 Z \subseteq U \setminus V : \paren {V \cup Z \in \mathscr I} \land \paren {\size {V \cup Z} = \size U} \) |
Then $M$ satisfies:
\((\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 \) |
Proof
Let $M$ satisfy condition $(\text I 3)$.
Let $U, V \in \mathscr I$ such that $\size V < \size U$.
By condition $(\text I 3)$:
- $\exists Z : \exists Z \subseteq U \setminus V : \paren {V \cup Z \in \mathscr I} \land \paren {\size {V \cup Z} = \size U}$
Then:
- $V \cup Z \ne V$
From Union with Empty Set:
- $Z \ne \O$
Then:
- $\exists x : x \in Z$
From Singleton of Element is Subset:
- $\set x \subseteq Z$
From Set Union Preserves Subsets:
- $V \cup \set x \subseteq V \cup Z$
From independence system axiom $(\text I 2)$:
- $V \cup \set x \in \mathscr I$
By definition of a subset:
- $x \in U \setminus V$
It follows that $M$ satisfies condition $(\text I 3)$.
$\blacksquare$