Equivalence of Definitions of Matroid

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 $M$ also satisfies:

 $(\text I 3)$ $:$ $\displaystyle \forall U, V \in \mathscr I:$ $\displaystyle \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 $M$ also satisfies:

 $(\text I 3')$ $:$ $\displaystyle \forall U, V \in \mathscr I:$ $\displaystyle \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 $M$ also satisfies:

 $(\text I 3'')$ $:$ $\displaystyle \forall U, V \in \mathscr I:$ $\displaystyle \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 $M$ also satisfies:

 $(\text I 3''')$ $:$ $\displaystyle \forall A \subseteq S:$ $\displaystyle \text{ all maximal subsets } Y \subseteq A \text{ with } Y \in \mathscr I \text{ 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$
$\set x \subseteq Z$
$V \cup \set x \subseteq V \cup Z$
$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$.

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

$\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$
$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$
$\exists x \in U \setminus V$ such that $V \cup \set x \in \mathscr I$

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

$\blacksquare$