Singleton is Dependent implies Rank is Zero
Jump to navigation
Jump to search
Theorem
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $x \in S$.
Let $\set x$ be dependent.
Then:
- $\map \rho {\set x} = 0$
where $\rho$ denotes the rank function of $M$.
Corollary
- $x$ is a loop if and only if $\map \rho {\set x} = 0$
Proof
By definition of a dependent subset:
- $\set x \notin \mathscr I$
Then:
\(\ds \map \rho {\set x}\) | \(=\) | \(\ds \max \set{\size A : A \in \powerset {\set x} \land A \in \mathscr I}\) | Definition of Rank Function | |||||||||||
\(\ds \) | \(=\) | \(\ds \max \set {\size A : A \in \set {\O, \set x} \land A \in \mathscr I}\) | Power Set of Singleton | |||||||||||
\(\ds \) | \(=\) | \(\ds \max \set {\size \O}\) | As $\set x \notin \mathscr I$ and Matroid axiom $(\text I 1)$ : $\O \in \mathscr I$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \max \set 0\) | Cardinality of Empty Set | |||||||||||
\(\ds \) | \(=\) | \(\ds 0\) | Definition of Max Operation |
$\blacksquare$