Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom/Sufficient Condition/Lemma

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

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


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

Let $U \subseteq B_1$ and $V \subseteq B_2$ such that:

$\card V < \card U$

Let $B_2 \cap \paren{U \setminus V} = \O$.


Then:

$\exists B_3 \in \mathscr B$:
$V \subseteq B_3$
$\card{B_1 \cap B_3} > \card{B_1 \cap B_2}$


Proof

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

$\card V < \card U$

Lemma 1

$\card{V \setminus U} < \card{U \setminus V}$

$\Box$

Lemma 2

\(\displaystyle \card {B_1}\) \(=\) \(\displaystyle \card{B_1 \cap B_2} + \card{B_1 \setminus B_2}\)
\(\displaystyle \card {B_2}\) \(=\) \(\displaystyle \card{B_2 \cap B_1} + \card{V \setminus B_1} + \card{\paren{B_2 \setminus B_1} \setminus V}\)

$\Box$


From Subset of Set Difference iff Disjoint Set:

$U \setminus V \subseteq B_1 \setminus B_2$


We have:

\(\displaystyle \card{B_2}\) \(=\) \(\displaystyle \card{B_1}\) Leigh.Samphier/Sandbox/Matroid Base Axiom Implies Sets Have Same Cardinality
\(\displaystyle \leadsto \ \ \) \(\displaystyle \card{B_2 \cap B_1} + \card{V \setminus B_1} + \card{\paren{B_2 \setminus B_1} \setminus V}\) \(=\) \(\displaystyle \card{B_1 \cap B_2} + \card{B_1 \setminus B_2}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \card{V \setminus B_1} + \card{\paren{B_2 \setminus B_1} \setminus V}\) \(=\) \(\displaystyle \card{B_1 \setminus B_2}\) Subtract $\card{B_1 \cap B_2}$ from both sides of equation
\(\displaystyle \) \(\ge\) \(\displaystyle \card{U \setminus V}\) Cardinality of Subset of Finite Set
\(\displaystyle \) \(>\) \(\displaystyle \card{V \setminus U}\)
\(\displaystyle \) \(\ge\) \(\displaystyle \card{V \setminus B_1}\) As $U \subseteq B_1$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \card{\paren{B_2 \setminus B_1} \setminus V}\) \(>\) \(\displaystyle 0\) Subtract $\card{V \setminus B_1}$ from both sides of equation


From the contrapositive statement of Cardinality of Empty Set:

$\paren{B_2 \setminus B_1} \setminus V \ne \O$

Hence: $\exists y \in \paren{B_2 \setminus B_1} \setminus V$

From $(\text B 1)$:

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


Let:

$B_3 = \paren{B_2 \setminus \set y} \cup \set z$


We have:

\(\displaystyle V\) \(\subseteq\) \(\displaystyle B_2 \setminus \set y\) As $y \notin V$ and $V \subseteq B_2$
\(\displaystyle \) \(\subseteq\) \(\displaystyle \paren{B_2 \setminus \set y} \cup \set z\) Set is Subset of Union
\(\displaystyle \) \(=\) \(\displaystyle B_3\)


Lemma 3

$\card{B_1 \cap B_3} = \card{B_1 \cap B_2} + 1$

$\Box$


Hence:

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

$\blacksquare$