Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms/Condition 1 Implies Condition 3/Lemma 1
< Leigh.Samphier/Sandbox | Equivalence of Definitions of Matroid Rank Axioms | Condition 1 Implies Condition 3
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 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 \) |
Then:
- $\forall A, B \subseteq S: A \subseteq B \implies \map \rho A \le \map \rho B$
Proof
Aiming for a contradiction, suppose:
- $\exists A, B \subseteq S : A \subseteq B$ and $\map \rho A > \map \rho B$
Let $B \subseteq S$:
- $\exists A \subseteq B : \map rho A > \map \rho B$
Let $A_0 \subseteq B$:
- $\card {A_0} = \max \set{\card A : A \subseteq B \land \map \rho A > \map \rho B}$
As $\map \rho {A_0} > \map \rho B$:
- $A_0 \ne B$
From Set Difference with Proper Subset:
- $\exists y \in B \setminus A_0$
We have:
\(\ds \map \rho B\) | \(<\) | \(\ds \map \rho {A_0}\) | By Choice of $A_0$ | |||||||||||
\(\ds \) | \(\le\) | \(\ds \map \rho {A_0 \cup \set y}\) | Rank axiom $(\text R 2)$ | |||||||||||
\(\ds \) | \(\le\) | \(\ds \map \rho B\) | By Choice of $A_0$ |
This is a contradiction.
Hence:
- $\forall A, B \subseteq S: A \subseteq B \implies \map \rho A \le \map \rho B$
$\blacksquare$