Singleton is Dependent implies Rank is Zero

From ProofWiki
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$