User:Leigh.Samphier/Matroids/Dual Matroid is Matroid

From ProofWiki
Jump to navigation Jump to search


This page needs proofreading.
Please check it for mathematical errors.
If you believe there are none, please remove {{Proofread}} from the code.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Proofread}} from the code.


Theorem

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


Then the dual $M^*$ of $M$ is a matroid.


Proof

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


By definition of dual matroid:

$M^*$ is the matroid whose bases is the set:
$\mathscr B^* = \set{S \setminus B : B \in \mathscr B}$

It is to be proved that there indeed exists a matroid whose set of bases is $\mathscr B^*$.


From Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom, it is sufficient to show that:

$\mathscr B^*$ satisfies formulation 1 base axiom.


Let $B^*_1, B^*_2 \in \mathscr B^*$.

By definition of $\mathscr B^*$:

$\exists B_1, B_2 \in \mathscr B$:
$B^*_1 = S \setminus B_1$
$B^*_2 = S \setminus B_2$


Let $x \in B^*_1 \setminus B^*_2$.

We have:

\(\ds B^*_1 \setminus B^*_2\) \(=\) \(\ds \paren{S \setminus B_1} \setminus \paren{S \setminus B_2}\)
\(\ds \) \(=\) \(\ds B_2 \setminus B_1\) Set Difference of Complements

And similarly:

$B^*_2 \setminus B^*_1 = B_1 \setminus B_2$


Hence:

$x \in B_2 \setminus B_1$

From User:Leigh.Samphier/Matroids/Matroid Bases Satisfy Formulation 4 Base Axiom:

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


Hence:

$y \in B^*_2 \setminus B^*_1$

We have:

\(\ds S \setminus \paren{\paren{B_1 \setminus \set y} \cup \set x}\) \(=\) \(\ds S \setminus \paren{\paren{B_1 \setminus \set y} \cup \paren{S \cap \set x} }\) Intersection with Subset is Subset
\(\ds \) \(=\) \(\ds \paren{S \setminus \paren{B_1 \setminus \set y} } \setminus \set x\) Set Difference with Set Difference is Union of Set Difference with Intersection
\(\ds \) \(=\) \(\ds \paren{\paren{S \setminus B_1}\cup \paren{ S \cap \set y} } \setminus \set x\) Set Difference with Set Difference is Union of Set Difference with Intersection
\(\ds \) \(=\) \(\ds \paren{\paren{S \setminus B_1}\cup \set y} \setminus \set x\) Intersection with Subset is Subset
\(\ds \) \(=\) \(\ds \paren{B^*_1 \cup \set y} \setminus \set x\) Definition of $B^*_1$
\(\ds \) \(=\) \(\ds \paren{B^*_1 \setminus \set x} \cup \set y\) Corollary of Set Difference Then Union Equals Union Then Set Difference

Hence:

$\paren{B^*_1 \setminus \set x} \cup \set y \in \mathscr B^*$


It follows that $\mathscr B^*$ satisfies formulation 1 base axiom.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=User:Leigh.Samphier/Matroids/Dual_Matroid_is_Matroid&oldid=700298"