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

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

Let $\mathscr B$ satisfy 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 \)

Then:

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

Proof

Aiming for a contradiction, suppose:

$\exists B_1, B_2 \in \mathscr B : \card{B_1} \ne \card{B_2}$

Without loss of generality and from Max Operation Equals an Operand let:

$\card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : C_1, C_2 \in \mathscr B : \card{C_1} \ne \card{C_2}}$

Without loss of generality let:

$\card{B_1} > \card{B_2}$

From Set Difference of Larger Set with Smaller is Not Empty:

$\exists x \in B_1 \setminus B_2$

From base axiom $(\text B 5)$:

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

Let $B_3 = \paren {B_2 \setminus \set y} \cup \set x$.

We have:

\(\ds \card{B_3 \cap B_1}\)

\(=\)

\(\ds \card{\paren{\paren {B_2 \setminus \set y} \cup \set x} \cap B_1}\)

\(\ds \)

\(=\)

\(\ds \card{\paren{\paren {B_2 \setminus \set y} \cap B_1} \cup \paren {\set x \cap B_1} }\)

Intersection Distributes over Union

\(\ds \)

\(=\)

\(\ds \card{\paren{\paren {B_2 \setminus \set y} \cap B_1} \cup \set x }\)

Intersection with Subset is Subset

\(\ds \)

\(=\)

\(\ds \card{\paren{\paren {B_2 \cap B_1 } \setminus \set y } \cup \set x }\)

Intersection with Set Difference is Set Difference with Intersection

\(\ds \)

\(=\)

\(\ds \card{\paren {B_2 \cap B_1 } \cup \set x }\)

Set Difference with Disjoint Set

\(\ds \)

\(>\)

\(\ds \card{B_1 \cap B_2 }\)

Cardinality of Proper Subset of Finite Set

This contradicts the choice of $B_1$ and $B_2$ as:

$\card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : C_1, C_2 \in \mathscr B : \card{C_1} \ne \card{C_2}}$

It follows that:

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

$\blacksquare$