# Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms

## Theorem

Let $S$ be a finite set.

Let $\rho : \powerset S \to \Z$ be a mapping from the power set of $S$ to the integers.

The following are equivalent:

### Condition 1

$\rho$ satisfies definition 1 of 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$

### Condition 2

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

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

### Condition 3

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

## Proof

### Condition 1 implies Condition 3

Let $\rho$ satisfy definition 1 of 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$

##### Lemma 1
$\forall A, B \subseteq S: A \subseteq B \implies \map \rho A \le \map \rho B$

$\Box$

##### Lemma 2
$\forall A \subseteq S: \map \rho A \le \card A$

$\Box$

##### Lemma 3

Let:

$A \subseteq S : \map \rho A = \card A$

Let:

$B \subseteq S : \forall b \in B \setminus A : \map \rho {A \cup \set b} \ne \card{A \cup \set b}$

Then:

$\map \rho {A \cup B} = \map \rho A$

$\Box$

Let:

$\mathscr I = \set{X \subseteq S : \map \rho X = \card X}$

It is to be shown that:

and

#### Matroid Axioms

##### Matroid Axiom $(\text I 1)$

We have:

 $\displaystyle \map \rho \O$ $=$ $\displaystyle 0$ Rank axiom $(\text R 1)$ $\displaystyle$ $=$ $\displaystyle \card \O$ Cardinality of Empty Set

So:

$\O \in \mathscr I$

Hence:

$M$ satisfies matroid axiom $(\text I 1)$.

$\Box$

##### Matroid Axiom $(\text I 2)$

Let

$X \in \mathscr I$

$\exists Y \subseteq X : Y \notin \mathscr I$

Let:

$Y_0 \subseteq X : \card {Y_0} = \max \set{\card Z : Z \subseteq X \land Z \notin \mathscr I}$

By definition of $\mathscr I$:

$Y_0 \notin \mathscr I \leadsto \map \rho {Y_0} \ne \card {Y_0}$

From Lemma 2:

$\map \rho {Y_0} < \card {Y_0}$

As $X \in \mathscr I$ then:

$Y_0 \ne X$
$X \setminus Y_0 \neq \O$

Let $y \in X \setminus Y_0$.

We have:

 $\displaystyle \card {Y_0} + 1$ $=$ $\displaystyle \card {Y_0 \cup \set y}$ Corollary of Cardinality of Set Union $\displaystyle$ $=$ $\displaystyle \map \rho {Y_0 \cup \set y}$ As $\card {Y_0} = \max \set{\card Z : Z \subseteq X \land Z \notin \mathscr I}$ $\displaystyle$ $\le$ $\displaystyle \map \rho {Y_0} + 1$ Rank axiom $(\text R 2)$ $\displaystyle$ $<$ $\displaystyle \card {Y_0} + 1$ As $\map \rho {Y_0} < \card {Y_0}$

So:

$\forall Y \subseteq X : Y \in \mathscr I$

Hence:

$M$ satisfies matroid axiom $(\text I 2)$.

$\Box$

##### Matroid Axiom $(\text I 3)$

Let

$U \in \mathscr I$
$V \subseteq S$
$\card U < \card V$

We prove the contrapositive statement:

$\paren{\forall x \in V \setminus U : U \cup \set x \notin \mathscr I} \implies V \notin \mathscr I$

Let for all $x \in V \setminus U$: $U \cup \set x \notin \mathscr I$

That is:

$\forall x \in V \setminus U : \map \rho {U \cup \set x} \ne \card {U \cup \set x}$

We have:

 $\displaystyle \card V$ $>$ $\displaystyle \card U$ $\displaystyle$ $=$ $\displaystyle \map \rho U$ As $U \in \mathscr I$ $\displaystyle$ $=$ $\displaystyle \map \rho {U \cup V}$ Lemma 3 $\displaystyle$ $\ge$ $\displaystyle \map \rho V$ Lemma 1

Hence:

$V \notin \mathscr I$

$\Box$

#### $\rho$ is Rank Function

Let $\rho_M$ be the rank function of the matroid $M = \struct{S, \mathscr I}$.

Let $X \subseteq S$.

By definition of the rank function:

$\map {\rho_M} X = \max \set{\card Y : Y \subseteq X, Y \in \mathscr I}$

Let $Y_0 \subseteq X$:

$\card {Y_0} = \max \set{\card Y : Y \subseteq X, Y \in \mathscr I}$

We have:

 $\displaystyle \map {\rho_M} X$ $=$ $\displaystyle \card {Y_0}$ By choice of $Y_0$ $\displaystyle$ $=$ $\displaystyle \map \rho {Y_0}$ As $Y_0 \in \mathscr I$

So it remains to show:

$\map \rho {Y_0} = \map \rho X$

##### Case 1 : $Y_0 = X$

Let $Y_0 = X$.

Then:

$\map \rho {Y_0} = \map \rho X$

$\Box$

##### Case 2 : $Y_0 \ne X$

Let $Y_0 \ne X$.

Then:

$Y_0 \subsetneq X$
$X \setminus Y_0 \ne \O$

By choice of $Y_0$:

$\forall y \in X \setminus Y_0 : Y_0 \cup \set y \notin \mathscr I$

That is:

$\forall y \in X \setminus Y_0 : \map \rho {Y_0 \cup \set y} \ne \card {Y_0 \cup \set y}$

From Lemma 3:

$\map \rho {Y_0} = \map \rho {Y_0 \cup X} = \map \rho X$

$\Box$

In either case:

$\map \rho {Y_0} = \map \rho X$

It follows that:

$\forall X \subseteq S : \map {\rho_M} X = \map \rho X$

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

$\Box$

### Condition 3 implies Condition 2

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

#### $\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:

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

$\Box$

### Condition 2 implies Condition 1

Let $\rho$ satisfy definition 2 of the rank axioms:

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

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

We have:

 $\displaystyle 0$ $\le$ $\displaystyle \map \rho \O$ rank axiom $(\text R 1')$ $\displaystyle$ $\le$ $\displaystyle \card \O$ rank axiom $(\text R 1')$ $\displaystyle$ $=$ $\displaystyle 0$ Cardinality of Empty Set

Hence:

$\map \rho \O = 0$

$\Box$

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

Let $X \subseteq S$.

Let $y \in S$.

We have:

 $\displaystyle \map \rho X$ $\le$ $\displaystyle \map \rho {X \cup y}$ rank axiom $(\text R 2')$ $\displaystyle$ $\le$ $\displaystyle \map \rho X + \map \rho {\set y} - \map \rho {X \cup \set y}$ rank axiom $(\text R 3')$ $\displaystyle$ $\le$ $\displaystyle \map \rho X + \map \rho {\set y}$ $\displaystyle$ $\le$ $\displaystyle \map \rho X + \card {\set y}$ rank axiom $(\text R 1')$ $\displaystyle$ $\le$ $\displaystyle \map \rho X + 1$ Cardinality of Singleton

This proves rank axiom $(\text R 2)$

$\Box$

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

$\blacksquare$