Leigh.Samphier/Sandbox/Matroid with No Circuits Has Single Base

From ProofWiki
Jump to navigation Jump to search


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


$S$ is the only base on $M$.


From Dependent Subset Contains a Circuit:

$M$ has no dependent subsets

By definition of dependent subsets:

Every subset of $S$ is independent

In particular:

$S \in \mathscr I$

By definition of independent subsets:

$X \in \mathscr I \implies X \subseteq S$

Hence $S$ is a base on $M$ by definition.

Let $X$ be a base on $M$.

Then $X \subseteq S$.

By definition of a base on $M$:

$X$ is a maximal independent subset of $M$

As $S \in \mathscr I$, by definition of a maximal set:

$X = S$


$S$ is the only base on $M$.