Singleton is Independent implies Rank is One/Corollary

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $M = \struct{S, \mathscr I}$ be a matroid.

Let $x \in S$.


Then:

$\set x$ is an independent subset if and only if $\map \rho {\set x} = 1$

where $\rho$ denotes the rank function of $M$.


Proof

By definition of an independent subset:

$x$ is an independent subset if and only if $\set x \notin \mathscr I$

From Singleton is Independent implies Rank is One:

if $\set x \in \mathscr I$ then $\map \rho {\set x} = 1$

From Singleton is Dependent implies Rank is Zero:

if $\set x \notin \mathscr I$ then $\map \rho {\set x} = 0$

It follows that:

$\set x \in \mathscr I$ if and only if $\map \rho {\set x} = 1$

$\blacksquare$