Equivalence of Definitions of Matroid Rank Axioms/Condition 1 Implies Condition 3/Proof 2
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:
- $\quad \mathscr I$ satisfies the matroid axioms
and
- $\quad \rho$ is the rank function of the matroid $M = \struct{S, \mathscr I}$
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$
- $\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
- 1976: Dominic Welsh: Matroid Theory ... (previous) ... (next) Chapter $1.$ $\S 6.$ Properties of the rank function, Proof of Theorem $2.2$