# Equivalence of Definitions of Matroid/Definition 1 implies Definition 4

## Theorem

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

Let $M$ also satisfy:

 $(\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$

Then $M$ 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

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}$

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

$\blacksquare$