Equivalence of Definitions of Matroid Rank Axioms/Condition 1 Implies Condition 3/Proof 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 : \powerset S \to \Z$ be a mapping from the power set of $S$ to the integers.

Let $\rho$ satisfy formulation 1 of the rank axioms:

\((\text R 1)\)   $:$   \(\ds \map \rho \O = 0 \)      
\((\text R 2)\)   $:$     \(\ds \forall X \in \powerset S \land y \in S:\) \(\ds \map \rho X \le \map \rho {X \cup \set y} \le \map \rho X + 1 \)      
\((\text R 3)\)   $:$     \(\ds \forall X \in \powerset S \land y, z \in S:\) \(\ds \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 $\rho$ is the rank function of a matroid on $S$.


Proof

Lemma 1
$\forall A, B \subseteq S: A \subseteq B \implies \map \rho A \le \map \rho B$

$\Box$


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

$\Box$


Let:

$\mathscr I = \set{X \subseteq S : \map \rho X = \card X}$

It is to be shown that:

and


Matroid Axioms

Matroid Axiom $(\text I 1)$

We have:

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

Hence $\O \in \mathscr I$, and $\mathscr I$ satisfies matroid Axiom $(\text I 1)$.

$\Box$


Matroid Axiom $(\text I 2)$

We prove the contrapositive statement:

$\forall X, Y \subseteq S: Y \notin \mathscr I \land Y \subseteq X \implies X \notin \mathscr I$


Let $X, Y \subseteq S : Y \notin \mathscr I$ and $Y \subseteq X$.

Case 1: $Y = X$

Let $Y = X$.

Then $X \notin \mathscr I$.

$\Box$

Case 2: $Y \subset X$

Let $Y \subset X$.


By definition of $\mathscr I$:

$\map \rho Y \neq \size Y$

From Lemma 2:

$\map \rho Y < \size Y$


Let:

$X \setminus Y = \set{z_1, z_2, \ldots , z_k}$

We have:

\(\ds \map \rho {Y \cup \set{c_1} }\) \(=\) \(\ds \map \rho Y + 1\) Rank axiom $(\text R 2)$
\(\ds \) \(<\) \(\ds \size Y + 1\) Lemma 2


By repeated application of rank axiom $(\text R 2)$, we have:

\(\ds \map \rho X\) \(=\) \(\ds \map \rho {Y \cup \set{c_1, c_2, \ldots, c_k} }\)
\(\ds \) \(<\) \(\ds \size Y + k\) Repeated application of Lemma 2
\(\ds \) \(=\) \(\ds \size Y + \size {\set {c_1, c_2, \ldots, c_k} }\) Definition of Cardinality of Finite Set
\(\ds \) \(=\) \(\ds \size {Y \cup \set {c_1, c_2, \ldots, c_k} }\) Corollary of Cardinality of Set Union
\(\ds \) \(=\) \(\ds \size X\)

It follows that $X \notin \mathscr I$.

$\Box$


In either case we have:

$X \notin \mathscr I$


This proves the contrapositive statement:

$\forall X, Y \subseteq S: Y \notin \mathscr I \land Y \subseteq X \implies X \notin \mathscr I$

It follows that $\mathscr I$ satisfies matroid Axiom $(\text I 2)$.

$\Box$


Matroid Axiom $(\text I 3)$

It is now proved that $\mathscr I$ satisifes the matroid Axiom $(\text I 3')$:

\((\text I 3')\)   $:$     \(\ds \forall U, V \in \mathscr I:\) \(\ds \size U = \size V + 1 \implies \exists x \in U \setminus V : V \cup \set x \in \mathscr I \)      


Let $X, Y \in \mathscr I$ such that $\size Y = \size X + 1$.


Let:

$X = \set {x_1, x_2, \ldots, x_q, z_{q + 1}, \ldots, z_k}$

and

$Y = \set {x_1, x_2, \ldots, x_q, y_{q + 1}, \ldots, y_k, y_{k + 1}}$

where $\forall i \in \set {q + 1, \ldots, k}$ and $\forall j \in \set {q + 1, \ldots, k + 1}$

$z_i \neq y_j$


Aiming for a contradiction, suppose:

$\forall j \in \set {q + 1, \ldots, k + 1}: X \cup \set{y_j} \notin \mathscr I$


We have:

\(\ds \size X\) \(=\) \(\ds \map \rho X\) As $X \in \mathscr I$
\(\ds \) \(\le\) \(\ds \map \rho {X \cup \set{y_j} }\) Rank axiom $(\text R 2)$
\(\ds \) \(\le\) \(\ds \map \rho X + 1\) Rank axiom $(\text R 2)$
\(\ds \) \(\le\) \(\ds \size X + 1\) As $X \in \mathscr I$
\(\ds \) \(=\) \(\ds \size X + \size {\set {y_j} }\) Cardinality of Singleton
\(\ds \) \(=\) \(\ds \size {X \cup \set{y_j} }\) Corollary of Cardinality of Set Union

Hence:

$\size X \le \map \rho {X \cup \set{y_j} } < \size {X \cup \set{y_j} } = \size X + 1$

It follows that:

$\size X = \map \rho {X \cup \set{y_j} }$

Hence:

$\forall j \in \set {q + 1, \ldots, k + 1}: \map \rho X = \map \rho {X \cup \set{y_j} } = \size X$

By rank axiom $(\text R 3)$:

$\forall i, j \in \set {q + 1, \ldots, k + 1}: \map \rho {X \cup \set{y_i, y_j} } = \map \rho X = \size X$


Applying rank axiom $(\text R 3)$ repeatedly, we get:

$\map \rho {X \cup \set{y_{q + 1}, \ldots, y_{k + 1} } = \map \rho X = \size X < \size Y$


Now:

$Y \subseteq X \cup \set{y_{q + 1}, \ldots, y_{k + 1} }$

From Lemma 1:

$\map \rho Y \le \map \rho {X \cup \set{y_{q + 1}, \ldots, y_{k + 1} } < \size Y$

This contrdict the assumption that $Y \in \mathscr I$.


Hence:

$\exists j \in \set {q + 1, \ldots, k + 1}: X \cup \set{y_j} \in \mathscr I$

It follows that $\mathscr I$ satisfies matroid Axiom $(\text I 3')$.

$\Box$


We have proven that $\mathscr I$ satisifies the matroid axioms.

It follows that $M = \struct{S, \mathscr I}$ is a matroid by definition.


$\rho$ is Rank Function

Let $\rho_M$ be the rank function of the matroid $M = \struct{S, \mathscr I}$.


Let $X \subseteq S$.


By definition of the rank function:

$\map {\rho_M} X = \max \set{\card Y : Y \subseteq X, Y \in \mathscr I}$

Let $Y_0 \subseteq X$:

$\card {Y_0} = \max \set{\card Y : Y \subseteq X, Y \in \mathscr I}$

We have:

\(\ds \map {\rho_M} X\) \(=\) \(\ds \card {Y_0}\) By choice of $Y_0$
\(\ds \) \(=\) \(\ds \map \rho {Y_0}\) As $Y_0 \in \mathscr I$

So it remains to show:

$\map \rho {Y_0} = \map \rho X$


Case 1 : $Y_0 = X$

Let $Y_0 = X$.

Then:

$\map \rho {Y_0} = \map \rho X$

$\Box$


Case 2 : $Y_0 \ne X$

Let $Y_0 \ne X$.

Then:

$Y_0 \subsetneq X$

From Set Difference with Proper Subset:

$X \setminus Y_0 \ne \O$

By choice of $Y_0$:

$\forall y \in X \setminus Y_0 : Y_0 \cup \set y \notin \mathscr I$

That is:

$\forall y \in X \setminus Y_0 : \map \rho {Y_0 \cup \set y} \ne \card {Y_0 \cup \set y}$

From Lemma 3:

$\map \rho {Y_0} = \map \rho {Y_0 \cup X} = \map \rho X$

$\Box$


In either case:

$\map \rho {Y_0} = \map \rho X$

It follows that:

$\forall X \subseteq S : \map {\rho_M} X = \map \rho X$

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


$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Equivalence_of_Definitions_of_Matroid_Rank_Axioms/Condition_1_Implies_Condition_3/Proof_2&oldid=607365"