Equivalence of Definitions of Matroid

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $M = \struct {S, \mathscr I}$ be an independence system.


The following definitions of the concept of Matroid are equivalent:

Definition 1

$M$ is called a matroid on $S$ if and only if $M$ also 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 \)      

Definition 2

$M$ is called a matroid on $S$ if and only if $M$ also 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 \)      

Definition 3

$M$ is called a matroid on $S$ if and only if $M$ also satisfies:

\((\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} \)      

Definition 4

$M$ is called a matroid on $S$ if and only if $M$ also satisfies:

\((\text I 3''')\)   $:$     \(\ds \forall A \subseteq S:\) \(\ds \text {all maximal subsets $Y \subseteq A$ with $Y \in \mathscr I$ have the same cardinality} \)      


Proof

Definition 1 implies Definition 2

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')$.

$\Box$


Definition 2 implies Definition 3

From Independent Set can be Augmented by Larger Independent Set it follows that if $M$ satisfies condition $(\text I 3')$ then $M$ satisfies condition $(\text I 3'')$.

$\Box$


Definition 3 implies Definition 1

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)$.

$\Box$


Definition 1 implies Definition 4

Let $M$ satisfy condition $(\text I 3)$.

Let $A \subseteq S$.

Let $Y_1, Y_2$ be maximal independent subsets of $A$.

Without loss of generality, let:

$\size {Y_2} \le \size {Y_1}$


Aiming for a contradiction, suppose:

$\size {Y_2} < \size {Y_1}$

By condition $(\text I 3)$:

$\exists y \in Y_1 \setminus Y_2 : Y_2 \cup \set y \in \mathscr I$

From Union of Subsets is Subset:

$Y_2 \cup \set y \subseteq A$

This contradicts the maximality of $Y_2$.

Then:

$\size {Y_2} = \size {Y_1}$


It follows that $M$ satisifies $(\text I 3''')$.

$\Box$


Definition 4 implies Definition 1

Let $M$ satisfy condition $(\text I 3''')$.

Let $U, V \in \mathscr I$ such that $\size V < \size U$.

Let $W$ be a maximal independent subset of $U \cup V$ containing $U$.

Then:

$\size U \le \size W$

By condition $(\text I 3''')$:

$V$ is not a maximal independent subset of $U \cup V$

Then:

$\exists x \in \paren {U \cup V} \setminus V$ such that $V \cup \set x \in \mathscr I$

From Set Difference with Union is Set Difference:

$\exists x \in U \setminus V$ such that $V \cup \set x \in \mathscr I$

It follows that $M$ satisifies $(\text I 3)$

$\blacksquare$


Sources