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

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

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


Then $\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 \)             


Proof

$\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$.

From Leigh.Samphier/Sandbox/Independent Subset is Contained in Maximal Independent Subset/Corollary:

$\card A = \map \rho {X \cap Y}$


From Independent Subset is Contained in Maximal Independent Subset:

$\exists B \subseteq X \setminus Y : A \cup B$ is a maximal independent subset of $X$

Simiarly from Independent Subset is Contained in Maximal Independent Subset:

$\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}$


By matroid axiom $(\text I 2)$:

$A \cup C$ is an independent subset of $Y$.


We have:

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

$\blacksquare$


Sources