User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 2
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 $S$ be a finite set.
Let $\mathscr B$ be a non-empty set of subsets of $S$.
Let $\mathscr B$ satisfy the base axiom:
User:Leigh.Samphier/Matroids/Axiom:Base Axioms (Matroid)/Axiom 1
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 1)$:
- $\exists y \in B_2 \setminus B_1 : \paren {B_1 \setminus \set x} \cup \set y \in \mathscr B$
Let $B_3 = \paren {B_1 \setminus \set x} \cup \set y$.
We have:
\(\ds \card{B_3 \cap B_2}\) | \(=\) | \(\ds \card{\paren{\paren {B_1 \setminus \set x} \cup \set y} \cap B_2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \card{\paren{\paren {B_1 \setminus \set x} \cap B_2} \cup \paren {\set y \cap B_2} }\) | Intersection Distributes over Union | |||||||||||
\(\ds \) | \(=\) | \(\ds \card{\paren{\paren {B_1 \setminus \set x} \cap B_2} \cup \set y }\) | Intersection with Subset is Subset | |||||||||||
\(\ds \) | \(=\) | \(\ds \card{\paren{\paren {B_1 \cap B_2 } \setminus \set x } \cup \set y }\) | Intersection with Set Difference is Set Difference with Intersection | |||||||||||
\(\ds \) | \(=\) | \(\ds \card{\paren {B_1 \cap B_2 } \cup \set y }\) | 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$