Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom/Necessary Condition

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\mathscr B$ be the set of bases of the matroid on $M$.


Then $\mathscr B$ satisfies the base axiom:

\((\text B 1)\)   $:$     \(\displaystyle \forall B_1, B_2 \in \mathscr B:\) \(\displaystyle x \in B_1 \setminus B_2 \implies \exists y \in B_2 \setminus B_1 : \paren {B_1 \setminus \set x} \cup \set y \in \mathscr B \)             


Proof

Let $B_1, B_2 \in \mathscr B$.

Let $x \in B_1 \setminus B_2$.


We have:

\(\displaystyle \size {B_1 \setminus \set x}\) \(=\) \(\displaystyle \size {B_1} - \size {\set x}\) Cardinality of Set Difference with Subset
\(\displaystyle \) \(=\) \(\displaystyle \size {B_2} - \size {\set x}\) All Bases of Matroid have same Cardinality
\(\displaystyle \) \(=\) \(\displaystyle \size {B_2} - 1\) Cardinality of Singleton
\(\displaystyle \) \(<\) \(\displaystyle \size {B_2}\)

By matroid axiom $(\text I 3)$:

$\exists y \in B_2 \setminus \paren{B_1 \setminus \set x} : \paren{ B_1 \setminus \set x} \cup \set y \in \mathscr I$


We have:

\(\displaystyle B_2 \setminus \paren{B_1 \setminus \set x}\) \(=\) \(\displaystyle \paren{B_2 \setminus B_1} \cup \paren{B_2 \cap \set x}\) Set Difference with Set Difference is Union of Set Difference with Intersection
\(\displaystyle \) \(=\) \(\displaystyle \paren{B_2 \setminus B_1} \cup \O\) Intersection With Singleton is Disjoint if Not Element
\(\displaystyle \) \(=\) \(\displaystyle B_2 \setminus B_1\) Union with Empty Set

Then:

$\exists y \in B_2 \setminus B_1 : \paren{ B_1 \setminus \set x} \cup \set y \in \mathscr I$


We have:

\(\displaystyle \size{\paren { B_1 \setminus \set x} \cup \set y}\) \(=\) \(\displaystyle \size{B_1 \setminus \set x} + \size{\set y}\) Corollary to Cardinality of Set Union
\(\displaystyle \) \(=\) \(\displaystyle \size{B_1} - \size{\set x} + \size{\set y}\) Cardinality of Set Difference with Subset
\(\displaystyle \) \(=\) \(\displaystyle \size{B_1} - 1 + 1\) Cardinality of Singleton
\(\displaystyle \) \(=\) \(\displaystyle \size{B_1}\)

From Independent Subset is Base if Cardinality Equals Cardinality of Base:

$\paren { B_1 \setminus \set x} \cup \set y \in \mathscr B$


Since $x$, $B_1$ and $B_2$ were arbitrary then the result follows.

$\blacksquare$