Uniform Matroid is Matroid
Theorem
Let $S$ be a finite set of cardinality $n$.
Let $0 \le k \le n$.
Let $U_{k, n} = \struct{S, \mathscr I}$ be the uniform matroid of rank $k$.
Then $U_{k, n}$ is a matroid.
Proof
It needs to be shown that $\mathscr I$ satisfies the matroid axioms $(I1)$, $(I2)$ and $(I3)$.
Matroid Axiom $(I1)$
Now:
| \(\ds \size \O\) | \(=\) | \(\ds 0\) | Cardinality of Empty Set | |||||||||||
| \(\ds \) | \(\le\) | \(\ds k\) | Assumption |
By definition of the uniform matroid of rank $k$:
- $\O \in \mathscr I$
It follows that $\mathscr I$ satisfies matroid axiom $(I1)$.
$\Box$
Matroid Axiom $(I2)$
Let $X \in \mathscr I$.
Let $Y \subseteq X$.
Then:
| \(\ds \size Y\) | \(\le\) | \(\ds \size X\) | Cardinality of Subset of Finite Set | |||||||||||
| \(\ds \) | \(\le\) | \(\ds k\) | Definition of uniform matroid of rank $k$ |
By definition of the uniform matroid of rank $k$:
- $Y \in \mathscr I$
It follows that $\mathscr I$ satisfies matroid axiom $(I2)$.
$\Box$
Matroid Axiom $(I3)$
Let $U, V \in \mathscr I$.
Let $\size V < \size U$.
From Intersection is Subset:
- $U \cap V \subseteq V$
- $U \cap V \subseteq U$
Then:
| \(\ds \size {U \cap V}\) | \(\le\) | \(\ds \size V\) | Cardinality of Subset of Finite Set | |||||||||||
| \(\ds \) | \(<\) | \(\ds \size U\) | Assumption |
Then:
- $U \cap V \ne U$
It follows that:
- $U \cap V \subsetneqq U$
Then:
| \(\ds \exists x\) | \(\in\) | \(\ds U \setminus {U \cap V}\) | Set Difference with Proper Subset | |||||||||||
| \(\ds \) | \(=\) | \(\ds U \setminus V\) | Set Difference with Intersection is Difference |
Then:
| \(\ds \size {V \cup \set x}\) | \(=\) | \(\ds \size V + \size {\set x}\) | Corollary to Cardinality of Set Union | |||||||||||
| \(\ds \) | \(=\) | \(\ds \size V + 1\) | Cardinality of Singleton | |||||||||||
| \(\ds \) | \(\le\) | \(\ds \size U\) | Assumption | |||||||||||
| \(\ds \) | \(\le\) | \(\ds k\) | Definition of uniform matroid of rank $k$ |
By definition of the uniform matroid of rank $k$:
- $V \cup \set x \in \mathscr I$
It follows that $\mathscr I$ satisfies matroid axiom $(I3)$.
$\blacksquare$
Sources
- 1976: Dominic Welsh: Matroid Theory ... (previous) ... (next) Chapter $1.$ $\S 3.$ Examples of Matroids