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

From ProofWiki
Jump to navigation Jump to search

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$


Sources