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

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

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

## Proof

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

We have:

 $\ds 0$ $\le$ $\ds \map \rho \O$ Rank axiom $(\text R 1')$ $\ds$ $\le$ $\ds \card \O$ Rank axiom $(\text R 1')$ $\ds$ $=$ $\ds 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:

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

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

$\Box$

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

Let $X \subseteq S$.

Let $x, y \in S$.

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

We have:

 $\ds \map \rho X$ $\le$ $\ds \map \rho {X \cup \set x \cup \set y }$ Rank axiom $(\text R 2')$ $\ds$ $=$ $\ds \map \rho {\paren{X \cup \set x} \cup \paren{X \cup \set y} }$ $\ds$ $\le$ $\ds \map \rho {X \cup \set x} + \map \rho {X \cup \set x} - \map \rho {\paren{X \cup \set x} \cap \paren{X \cup \set y} }$ Rank axiom $(\text R 3')$ $\ds$ $\le$ $\ds \map \rho {X \cup \set x} + \map \rho {X \cup \set x} - \map \rho X$ $\ds$ $=$ $\ds \map \rho X + \map \rho X - \map \rho X$ $\ds$ $=$ $\ds \map \rho X$

Hence:

$\map \rho {X \cup \set x \cup \set y} = \map \rho X$

This proves Rank axiom $(\text R 3)$

$\blacksquare$