Equivalence of Definitions of Matroid Rank Axioms/Condition 3 Implies Condition 2

From ProofWiki
Jump to navigation Jump to search


This article needs proofreading.
Please check it for mathematical errors.
If you believe there are none, please remove {{Proofread}} from the code.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Proofread}} from the code.


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')\)   $:$     \(\ds \forall X \in \powerset S:\) \(\ds 0 \le \map \rho X \le \size X \)      
\((\text R 2')\)   $:$     \(\ds \forall X, Y \in \powerset S:\) \(\ds X \subseteq Y \implies \map \rho X \le \map \rho Y \)      
\((\text R 3')\)   $:$     \(\ds \forall X, Y \in \powerset S:\) \(\ds \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 Cardinality of Maximal Independent Subset Equals Rank of Set:

$\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} + \paren{\card A + \card C }\) Cardinality of Set Union: Corollary
\(\ds \) \(=\) \(\ds \paren{\card{A \cup B} + \card A } + \card C\) Sum of Cardinals is Associative
\(\ds \) \(=\) \(\ds \card{A \cup B \cup C} + \card A\) Cardinality of Set Union: Corollary
\(\ds \) \(=\) \(\ds \map \rho {X \cup Y} + \map \rho {X \cap Y}\) Definition of rank function $\rho$

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Equivalence_of_Definitions_of_Matroid_Rank_Axioms/Condition_3_Implies_Condition_2&oldid=629041"