Leigh.Samphier/Sandbox/Matroid with No Circuits Has Single Base
Jump to navigation
Jump to search
Theorem
Let $M = \struct {S, \mathscr I}$ be a matroid with no circuits.
Then:
- $S$ is the only base on $M$.
Proof
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$
Hence:
- $S$ is the only base on $M$.
$\blacksquare$
Sources
- 1976: Dominic Welsh: Matroid Theory ... (previous) ... (next) Chapter $1.$ $\S 9.$ Circuits