User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms

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 $S$ be a finite set.

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

The following statements are equivalent:

Condition 1

$\mathscr B$ satisfies any one of the base axioms:

\((\text B 1)\)	$:$			\(\ds \forall B_1, B_2 \in \mathscr B:\)				\(\ds 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 \)
\((\text B 2)\)	$:$			\(\ds \forall B_1, B_2 \in \mathscr B:\)				\(\ds 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 \)
\((\text B 3)\)	$:$			\(\ds \forall B_1, B_2 \in \mathscr B:\)				\(\ds \exists \text{ a bijection } \pi : B_1 \setminus B_2 \to B_2 \setminus B_1 : \forall x \in B_1 \setminus B_2 : \paren {B_1 \setminus \set x } \cup \set {\map \pi x} \in \mathscr B \)
\((\text B 4)\)	$:$			\(\ds \forall B_1, B_2 \in \mathscr B:\)				\(\ds 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, \paren {B_2 \setminus \set y} \cup \set x \in \mathscr B \)
\((\text B 5)\)	$:$			\(\ds \forall B_1, B_2 \in \mathscr B:\)				\(\ds x \in B_1 \setminus B_2 \implies \exists y \in B_2 \setminus B_1 : \paren {B_2 \setminus \set y} \cup \set x \in \mathscr B \)
\((\text B 6)\)	$:$			\(\ds \forall B_1, B_2 \in \mathscr B:\)				\(\ds x \in B_1 \setminus B_2 \implies \exists y \in B_2 \setminus B_1 : \paren {B_2 \cup \set x} \setminus \set y \in \mathscr B \)
\((\text B 7)\)	$:$			\(\ds \forall B_1, B_2 \in \mathscr B:\)				\(\ds \exists \text{ a bijection } \pi : B_1 \setminus B_2 \to B_2 \setminus B_1 : \forall x \in B_1 \setminus B_2 : \paren {B_2 \setminus \set {\map \pi x} } \cup \set x \in \mathscr B \)

Condition 2

$\mathscr B$ satisfies all of the base axioms.

Condition 3

$\mathscr B$ is the set of bases for some matroid on $S$.

Proof

Condition 3 iff Axiom $(\text B 1)$

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:

\(\ds \size {B_1 \setminus \set x}\)

\(=\)

\(\ds \size {B_1} - \size {\set x}\)

Cardinality of Set Difference with Subset

\(\ds \)

\(=\)

\(\ds \size {B_2} - \size {\set x}\)

All Bases of Matroid have same Cardinality

\(\ds \)

\(=\)

\(\ds \size {B_2} - 1\)

Cardinality of Singleton

\(\ds \)

\(<\)

\(\ds \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:

\(\ds B_2 \setminus \paren{B_1 \setminus \set x}\)

\(=\)

\(\ds \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

\(\ds \)

\(=\)

\(\ds \paren{B_2 \setminus B_1} \cup \O\)

Intersection With Singleton is Disjoint if Not Element

\(\ds \)

\(=\)

\(\ds 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:

\(\ds \size{\paren { B_1 \setminus \set x} \cup \set y}\)

\(=\)

\(\ds \size{B_1 \setminus \set x} + \size{\set y}\)

Corollary to Cardinality of Set Union

\(\ds \)

\(=\)

\(\ds \size{B_1} - \size{\set x} + \size{\set y}\)

Cardinality of Set Difference with Subset

\(\ds \)

\(=\)

\(\ds \size{B_1} - 1 + 1\)

Cardinality of Singleton

\(\ds \)

\(=\)

\(\ds \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)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds 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:

• $\quad \mathscr I$ satisfies the matroid axioms

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 Operation 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 1

$\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'$

Lemma 2

$\forall B_1, B_2 \in \mathscr B : \card{B_1} = \card{B_2}$

where $\card{B_1}$ and $\card{B_2}$ denote the cardinality of the sets $B_1$ and $B_2$ respectively.

$\Box$

From Lemma 2:

$\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.

$\Box$

Lemma 6

Let $B_1, B_2 \subseteq S$.

Let $x \in B_1 \setminus B_2$.

Let $y \in B_2 \setminus B_1$.

Then:

$\paren{B_1 \setminus \set x} \cup \set y = \paren{B_1 \cup \set y} \setminus \set x$

$\Box$

Axiom $(\text B 1)$ iff Axiom $(\text B 2)$

Axiom $(\text B 1)$ holds if and only if Axiom $(\text B 2)$ holds follows immediately from the lemma 6.

$\Box$

Axiom $(\text B 1)$ iff Axiom $(\text B 3)$

Necessary Condition

Let $\mathscr B$ satisfy the base axiom:

\((\text B 1)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds 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 \)

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. 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 {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

It follows that $\mathscr B$ satisfies the base axiom:

\((\text B 3)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds \exists \text{ a bijection } \pi : B_1 \setminus B_2 \to B_2 \setminus B_1 : \forall x \in B_1 \setminus B_2 : \paren {B_1 \setminus \set x } \cup \set {\map \pi x} \in \mathscr B \)

Sufficient Condition

By choosing $y = \map \pi x$ in Axiom $(\text B 3)$, Axiom $(\text B 1)$ follows immediately.

$\Box$

Axiom $(\text B 3)$ iff Axiom $(\text B 7)$

Necessary Condition

Let $\mathscr B$ satisfy the base axiom:

\((\text B 3)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds \exists \text{ a bijection } \pi : B_1 \setminus B_2 \to B_2 \setminus B_1 : \forall x \in B_1 \setminus B_2 : \paren {B_1 \setminus \set x } \cup \set {\map \pi x} \in \mathscr B \)

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

From $(\text B 3)$:

$\exists \text{ a bijection } \pi : B_2 \setminus B_1 \to B_1 \setminus B_2 : \forall y \in B_2 \setminus B_1 : \paren {B_2 \setminus \set y } \cup \set {\map \pi y} \in \mathscr B$

Let $\pi^{-1} : B_1 \setminus B_2 \to B_2 \setminus B_1$ denote the inverse mapping of $\pi$.

From Inverse of Bijection is Bijection, $\pi^{-1}$ is a bijection.

From Inverse Element of Bijection:

$\forall x \in B_1 \setminus B_2 : \map {\pi^{-1}} x = y \iff \map \pi y = x$

Hence:

$\forall x \in B_1 \setminus B_2 : \paren {B_1 \setminus \set{\map {\pi^{-1}} x} } \cup \set x = \paren {B_1 \setminus \set y} \cup \set {\map \pi y} \in \mathscr B$

It follows that $\mathscr B$ satisfies the base axiom:

\((\text B 7)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds \exists \text{ a bijection } \pi : B_1 \setminus B_2 \to B_2 \setminus B_1 : \forall x \in B_1 \setminus B_2 : \paren {B_2 \setminus \set {\map \pi x} } \cup \set x \in \mathscr B \)

Sufficient Condition

Let $\mathscr B$ satisfy the base axiom:

\((\text B 7)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds \exists \text{ a bijection } \pi : B_1 \setminus B_2 \to B_2 \setminus B_1 : \forall x \in B_1 \setminus B_2 : \paren {B_2 \setminus \set {\map \pi x} } \cup \set x \in \mathscr B \)

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

From $(\text B 7)$:

$\exists \text{ a bijection } \pi : B_2 \setminus B_1 \to B_1 \setminus B_2 : \forall y \in B_2 \setminus B_1 : \paren {B_1 \setminus \set {\map \pi y} } \cup \set y \in \mathscr B$

Let $\pi^{-1} : B_1 \setminus B_2 \to B_2 \setminus B_1$ denote the inyverse mapping of $\pi$.

From Inverse of Bijection is Bijection, $\pi^{-1}$ is a bijection.

From Inverse Element of Bijection:

$\forall x \in B_1 \setminus B_2 : \map {\pi^{-1}} x = y \iff \map \pi y = x$

Hence:

$\forall x \in B_1 \setminus B_2 : \paren {B_1 \setminus \set x } \cup \set{\map {\pi^{-1}} x} = \paren {B_1 \setminus \set {\map \pi y} } \cup \set y \in \mathscr B$

It follows that $\mathscr B$ satisfies the base axiom:

\((\text B 3)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds \exists \text{ a bijection } \pi : B_1 \setminus B_2 \to B_2 \setminus B_1 : \forall x \in B_1 \setminus B_2 : \paren {B_1 \setminus \set x } \cup \set {\map \pi x} \in \mathscr B \)

$\blacksquare$

Axiom $(\text B 1)$ iff Axiom $(\text B 4)$

Necessary Condition

Let $\mathscr B$ satisfy the base axiom:

\((\text B 1)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds 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 \)

From Set of Matroid Bases iff Axiom $( \text B 1)$:

there exists a matroid $M = \struct{S, \mathscr I}$ such that $\mathscr B$ is the set of bases of $M$.

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

Let $x \in B_1 \setminus B_2$.

From Matroid Base Union External Element has Fundamental Circuit:

there exists a fundamental circuit $\map C {x, B_2}$ of $M$ such that $x \in \map C {x, B_2} \subseteq B_2 \cup \set x$

By definition of set intersection:

$x \in B_1 \cap \map C {x, B_2}$

From Element of Matroid Base and Circuit has Substitute:

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

We have:

\(\ds y\)

\(\in\)

\(\ds \map C {x, B_2} \setminus B_1\)

\(\ds \)

\(\subseteq\)

\(\ds \map C {x, B_2} \setminus \set x\)

Set Difference with Subset is Superset of Set Difference

\(\ds \)

\(\subseteq\)

\(\ds \paren{B_2 \cup \set x} \setminus \set x\)

Set Difference over Subset

\(\ds \)

\(\subseteq\)

\(\ds B_2 \setminus \set x\)

Set Difference with Union is Set Difference

\(\ds \)

\(\subseteq\)

\(\ds B_2\)

Set Difference is Subset

From Matroid Base Substitution From Fundamental Circuit:

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

It follows that $\mathscr B$ satisfies the base axiom:

\((\text B 4)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds 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, \paren {B_2 \setminus \set y} \cup \set x \in \mathscr B \)

Sufficient Condition

Follows immediately from Axiom $(\text B 4)$ and Axiom $(\text B 1)$.

$\Box$

Axiom $(\text B 4)$ iff Axiom $(\text B 5)$

Necessary Condition

Follows immediately from Axiom $(\text B 4)$ and Axiom $(\text B 5)$.

$\Box$

Sufficient Condition

Let $\mathscr B$ satisfy the base axiom:

\((\text B 4)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds 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, \paren {B_2 \setminus \set y} \cup \set x \in \mathscr B \)

This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. 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 {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

It follows that $\mathscr B$ satisfies the base axiom:

\((\text B 5)\)

$:$

\(\ds \forall B_1, B_2 \in \mathscr B:\)

\(\ds x \in B_1 \setminus B_2 \implies \exists y \in B_2 \setminus B_1 : \paren {B_2 \setminus \set y} \cup \set x \in \mathscr B \)

$\Box$

Axiom $(\text B 5)$ iff Axiom $(\text B 6)$

Axiom $(\text B 5)$ holds if and only if Axiom $(\text B 6)$ holds follows immediately from the lemma 6.

$\Box$