Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

Let $\mathscr B$ be a non-empty set of subsets of $S$.


Then $\mathscr B$ is the set of bases of a matroid on $S$ if and only if $\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

Necessary Condition

Let $\mathscr B$ be the set of bases of the matroid on $M = \struct{S, \mathscr I}$


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.

$\Box$

Sufficient Condition

Let $\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 \cup \set y} \setminus \set x \in \mathscr B \)             


Let $\mathscr I = \set{X \subseteq S : \exists B \in \mathscr B : X \subseteq B}$

It is to be shown that:

and

  • $\quad \mathscr B$ is the set of bases of the matroid $M = \struct{S, \mathscr I}$


Matroid Axioms

Matroid Axiom $(\text I 1)$

We have $\mathscr B$ is non-empty.

Let $B \in \mathscr B$.

From Empty Set is Subset of All Sets:

$\O \subseteq B$

By definition of $\mathscr I$:

$\O \in \mathscr I$

It follows that $\mathscr I$ satisfies the matroid axiom $(\text I 1)$ by definition.

$\Box$

Matroid Axiom $(\text I 2)$

Let $X \in \mathscr I$.

Let $Y \subseteq X$.

By definition of $\mathscr I$:

$\exists B \in \mathscr B : X \subseteq B$

From Subset Relation is Transitive:

$Y \subseteq B$

By definition of $\mathscr I$:

$Y \in \mathscr I$

It follows that $\mathscr I$ satisfies the matroid axiom $(\text I 2)$ by definition.

$\Box$

Matroid Axiom $(\text I 3)$

Let $U, V \in \mathscr I$ such that:

$\card V < \card U$

By definition of $\mathscr I$:

$\exists B_1, B_2 \in \mathscr B : U \subseteq B_1, V \subseteq B_2$

From Max Equals an Operand:

$\exists B_1, B_2 \in \mathscr B : U \subseteq B_1, V \subseteq B_2 : \card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : U \subseteq C_1, V \subseteq C_2 \text{ and } C_1, C_2 \in \mathscr B}$


Aiming for a contradiction, suppose:

$B_2 \cap \paren{U \setminus V} = \O$
Lemma
$\exists B_3 \in \mathscr B$:
$V \subseteq B_3$
$\card{B_1 \cap B_3} > \card{B_1 \cap B_2}$

$\Box$


This contradicts the choice of $B_1, B_2$ such that:

$\card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : U \subseteq C_1, V \subseteq C_2 \text{ and } C_1, C_2 \in \mathscr B}$

Hence:

$B_2 \cap \paren{U \setminus V} \ne \O$


Let $x \in B_2 \cap \paren{U \setminus V}$.

From Union of Subsets is Subset:

$V \cup \set x \subseteq B_2$

By definition of $\mathscr I$:

$V \cup \set x \in \mathscr I$

It follows that $\mathscr I$ satisfies the matroid axiom $(\text I 3)$ by definition.

$\Box$

This completes the proof that $M = \struct{S, I}$ forms a matroid.

$\Box$

$\mathscr B$ is Set of Bases

Let $B \in \mathscr B$.

From Set is Subset of Itself:

$B \in \mathscr I$

Let $U \in \mathscr I$ such that:

$B \subseteq U$

By definition of $\mathscr I$:

$\exists B' \in \mathscr B : I \subseteq B'$

From Subset Relation is Transitive:

$B \subseteq B'$

From Leigh.Samphier/Sandbox/Matroid Base Axiom Implies Sets Have Same Cardinality:

$\card B = \card {B'}$

From Cardinality of Proper Subset of Finite Set:

$B = B'$

By definition of set equality:

$U = B$

It has been shown that $B$ is a maximal subset of the ordered set $\struct{\mathscr I, \subseteq}$.

It follows that $\mathscr B$ is the set of bases of the matroid $M = \struct{S, I}$ by definition.

$\blacksquare$


Sources