Leigh.Samphier/Sandbox/Matroid satisfies Rank Axioms/Necessary Condition

Theorem

Let $S$ be a finite set.

Let $\rho : \powerset S \to \Z$ be the rank function of a matroid on $S$.

Then $\rho$ satisfies the rank axioms:

 $(\text R 1)$ $:$ $\displaystyle \map \rho \O = 0$ $(\text R 2)$ $:$ $\displaystyle \forall X \in \powerset S \land y \in S:$ $\displaystyle \map \rho X \le \map \rho {X \cup \set y} \le \map \rho X + 1$ $(\text R 3)$ $:$ $\displaystyle \forall X \in \powerset S \land y, z \in S:$ $\displaystyle \map \rho {X \cup \set y} = \map \rho {X \cup \set z} = \map \rho X \implies \map \rho {X \cup \set{y,z} } = \map \rho X$

Proof

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

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

$\rho$ satisfies $(\text R 1)$ follows immediately from Rank of Empty Set is Zero.

$\Box$

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

Let:

$X \subseteq S$
$y \in S$
$\map \rho X \le \map \rho {X \cup \set y}$

Let $Y$ be a maximal independent subset of $X \cup \set y$.

$\card Y = \map \rho {X \cup \set y}$
$Y \setminus \set y \in \mathscr I$

We now consider two cases.

Case 1: $y \in Y$

We have:

 $\displaystyle \map \rho X$ $\ge$ $\displaystyle \card{Y \setminus \set y}$ Definition of Rank Function $\displaystyle$ $=$ $\displaystyle \card Y - \card{Y \cap \set y}$ Cardinality of Set Difference $\displaystyle$ $=$ $\displaystyle \card Y - \card{\set y}$ Singleton of Element is Subset $\displaystyle$ $=$ $\displaystyle \card Y - 1$ Cardinality of Singleton $\displaystyle \leadsto \ \$ $\displaystyle \map \rho X + 1$ $\ge$ $\displaystyle \card Y$ Add one to both sides

$\Box$

Case 2: $y \notin Y$

We have:

 $\displaystyle \map \rho X + 1$ $>$ $\displaystyle \map \rho X$ $\displaystyle$ $\ge$ $\displaystyle \card{Y \setminus \set y}$ Definition of Rank Function $\displaystyle$ $=$ $\displaystyle \card Y - \card{Y \cap \set y}$ Cardinality of Set Difference $\displaystyle$ $=$ $\displaystyle \card Y - \O$ Intersection With Singleton is Disjoint if Not Element $\displaystyle$ $=$ $\displaystyle \card Y - 0$ Cardinality of Empty Set $\displaystyle$ $=$ $\displaystyle \card Y$

$\Box$

In either case:

$\map \rho X + 1 \ge \card Y = \map \rho {X \cup \set y}$

$\Box$

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

Let:

$X \subseteq S$
$y, z \in S$
Case 1: $y, z \notin X$

Let $A = X \cup \set{y, z}$.

$\map \rho A \ge \map \rho X$

We now prove the contrapositive statement:

$\map \rho A > \map \rho X \implies$ either $\map \rho {X \cup \set y} > \map \rho X$ or $\map \rho {X \cup \set z} > \map \rho X$

Let $\map \rho A > \map \rho X$.

Let $Y$ be a maximal independent subset of $X$.

Let $Z$ be a maximal independent subset of $A$.

$\card Y = \map \rho X < \map \rho A = \card Z$

From Independent Set can be Augmented by Larger Independent Set there exists non-empty set $Z' \subseteq Z \setminus Y$:

$Y \cup Z' \in \mathscr I$
$\card{Y \cup Z'} = \card Z$

$y, z \notin Z'$

We have:

 $\displaystyle Z'$ $=$ $\displaystyle Z' \cap Z$ $\displaystyle$ $\subseteq$ $\displaystyle Z' \cap A$ $\displaystyle$ $=$ $\displaystyle Z' \cap \paren{X \cup \set {y, z} }$ $\displaystyle$ $=$ $\displaystyle \paren{Z' \cap X} \cup \paren{Z' \cap \set {y, z} }$ $\displaystyle$ $=$ $\displaystyle \paren{Z' \cap X} \cup \O$ $\displaystyle$ $=$ $\displaystyle \paren{Z' \cap X}$ $\displaystyle$ $\subseteq$ $\displaystyle X$ $\displaystyle \leadsto \ \$ $\displaystyle Y \cup Z'$ $\subseteq$ $\displaystyle X$

Hence:

 $\displaystyle \card{Y \cup Z'}$ $=$ $\displaystyle \card Z$ $\displaystyle$ $=$ $\displaystyle \map \rho A$ $\displaystyle$ $>$ $\displaystyle \map \rho X$ $\displaystyle$ $\ge$ $\displaystyle \card{Y \cup Z'}$

Hence:

either $y \in Z'$ or $z \in Z'$

Without loss of generality, assume $y \in Z'$.

$Y \cup \set y \in \mathscr I$

We have:

 $\displaystyle \map \rho {X \cup \set y}$ $\ge$ $\displaystyle \card{Y \cup \set y}$ Definition of Rank Function (Matroid) $\displaystyle$ $=$ $\displaystyle \card Y + \card{\set y}$ Corollary of Cardinality of Set Union $\displaystyle$ $=$ $\displaystyle \card Y + 1$ Cardinality of Singleton $\displaystyle$ $>$ $\displaystyle \card Y$ $\displaystyle$ $=$ $\displaystyle \map \rho X$ Definition of Rank Function (Matroid)

This proves the contrapositive statement.

$\Box$

Case 2: Either $y \in X$ or $z \in X$

Without loss of generality, assume $y \in X$.

Let:

$\map \rho {X \cup \set y} = \map \rho {X \cup \set z} = \map \rho X$.

We have:

$X \cup \set{y, z} = X \cup \set z$

Hence:

$\map \rho {X \cup \set{y, z}} = \map \rho {X \cup \set z} = \map \rho X$

$\Box$

In either case:

$\map \rho {X \cup \set y} = \map \rho {X \cup \set z} = \map \rho X \implies \map \rho {X \cup \set{y, z}} = \map \rho X$

$\blacksquare$