Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms/Condition 3 Implies Condition 2

Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

Let $\rho$ is the rank function of a matroid $M = \struct{S, \mathscr I}$.

Then $\rho$ satisfies definition 2 of the rank axioms:

 $(\text R 1')$ $:$ $\ds \forall X \in \powerset S:$ $\ds 0 \le \map \rho X \le \size X$ $(\text R 2')$ $:$ $\ds \forall X, Y \in \powerset S:$ $\ds X \subseteq Y \implies \map \rho X \le \map \rho Y$ $(\text R 3')$ $:$ $\ds \forall X, Y \in \powerset S:$ $\ds \map \rho {X \cup Y} + \map \rho {X \cap Y} \le \map \rho X + \map \rho Y$

Proof

$\rho$ satisfies $(\text R 1')$

This follows immediately from Bounds for Rank of Subset.

$\Box$

$\rho$ satisfies $(\text R 2')$

This follows immediately from Rank Function is Increasing.

$\Box$

$\rho$ satisfies $(\text R 3')$

Let $X, Y \subseteq S$.

Let $A$ be a maximal independent subset of $X \cap Y$.

$\card A = \map \rho {X \cap Y}$
$\exists B \subseteq X \setminus Y : A \cup B$ is a maximal independent subset of $X$
$\exists C \subseteq Y \setminus X : \paren{A \cup B} \cup C$ is a maximal independent subset of $X \cup Y$

and

$\card{A \cup B \cup C} = \map \rho {X \cup Y}$
$A \cup C$ is an independent subset of $Y$.

We have:

 $\ds \map \rho X + \map \rho Y$ $\ge$ $\ds \card{A \cup B} + \card{A \cup C}$ Definition of Rank function $\rho$ $\ds$ $=$ $\ds \card{A \cup B} + \card A + \card C$ Corollary to Cardinality of Set $\ds$ $=$ $\ds \card{A \cup B \cup C} + \card A$ Corollary to Cardinality of Set $\ds$ $=$ $\ds \map \rho {X \cup Y} + \map \rho {X \cap Y}$ Definition of Rank function $\rho$

$\blacksquare$