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

## 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.

Let $\rho$ satisfy 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 \cup \set z} = \map \rho X$

Then:

$\forall A \subseteq S: \map \rho A \le \card A$

## Proof

$\exists A \subseteq S : \map \rho A > \card A$

Let:

$A_0 \subseteq S : \card{A_0} = \min \set{\card A : \map \rho A > \card A}$

We have:

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

Hence:

$A_0 \neq \O$

Let $y \in A_0$.

$\card {A_0 \setminus \set y} = \card{A_0} - 1 < \card {A_0}$

We have:

 $\ds \map \rho {A_0}$ $=$ $\ds \map \rho {\paren {A_0 \setminus \set y} \cup \set y}$ $\ds$ $\le$ $\ds \map \rho {A_0 \setminus \set y} + 1$ Rank axiom $(\text R 2)$ $\ds$ $\le$ $\ds \card {A_0 \setminus \set y} + 1$ By choice of $A_0$ $\ds$ $=$ $\ds \card {A_0} - \card{\set y} + 1$ Cardinality of Set Difference with Subset $\ds$ $=$ $\ds \card {A_0} - 1 + 1$ Cardinality of Singleton $\ds$ $=$ $\ds \card {A_0}$

This contradicts the choice of $A_0$:

$\card{A_0} = \min \set{\card A : \map \rho A > \card A}$

It follows that:

$\forall A \subseteq S: \map \rho A \le \card A$

$\blacksquare$