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

## 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

 $\ds \card {B_1}$ $=$ $\ds \card{B_1 \cap B_2} + \card{B_1 \setminus B_2}$ $\ds \card {B_2}$ $=$ $\ds \card{B_2 \cap B_1} + \card{V \setminus B_1} + \card{\paren{B_2 \setminus B_1} \setminus V}$

$\Box$

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

We have:

 $\ds \card{B_2}$ $=$ $\ds \card{B_1}$ Leigh.Samphier/Sandbox/Matroid Base Axiom Implies Sets Have Same Cardinality $\ds \leadsto \ \$ $\ds \card{B_2 \cap B_1} + \card{V \setminus B_1} + \card{\paren{B_2 \setminus B_1} \setminus V}$ $=$ $\ds \card{B_1 \cap B_2} + \card{B_1 \setminus B_2}$ $\ds \leadsto \ \$ $\ds \card{V \setminus B_1} + \card{\paren{B_2 \setminus B_1} \setminus V}$ $=$ $\ds \card{B_1 \setminus B_2}$ Subtract $\card{B_1 \cap B_2}$ from both sides of equation $\ds$ $\ge$ $\ds \card{U \setminus V}$ Cardinality of Subset of Finite Set $\ds$ $>$ $\ds \card{V \setminus U}$ $\ds$ $\ge$ $\ds \card{V \setminus B_1}$ As $U \subseteq B_1$ $\ds \leadsto \ \$ $\ds \card{\paren{B_2 \setminus B_1} \setminus V}$ $>$ $\ds 0$ Subtract $\card{V \setminus B_1}$ from both sides of equation
$\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:

 $\ds V$ $\subseteq$ $\ds B_2 \setminus \set y$ As $y \notin V$ and $V \subseteq B_2$ $\ds$ $\subseteq$ $\ds \paren{B_2 \setminus \set y} \cup \set z$ Set is Subset of Union $\ds$ $=$ $\ds 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$