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

Jump to navigation Jump to search

## Theorem

Let $S$ be a finite set.

Let $B_1, B_2 \subseteq S$.

Let $z \in B_1 \setminus B_2$.

Let $y \in B_2 \setminus B_1$.

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

Then:

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

## Proof

We have:

 $\displaystyle B_3 \cap B_1$ $=$ $\displaystyle \paren{\paren{B_2 \setminus \set y} \cup \set z} \cap B_1$ $\displaystyle$ $=$ $\displaystyle \paren{\paren{B_2 \setminus \set y} \cap B_1 } \cup \paren{ \set z \cap B_1}$ Intersection Distributes over Union $\displaystyle$ $=$ $\displaystyle \paren{\paren{B_2 \setminus \set y} \cap B_1 } \cup \set z$ As $z \in B_1$ $\displaystyle$ $=$ $\displaystyle \paren{\paren{B_2 \cap B_1} \setminus \paren{\set y \cap B_1} } \cup \set z$ Set Intersection Distributes over Set Difference $\displaystyle$ $=$ $\displaystyle \paren{\paren{B_2 \cap B_1} \setminus \O } \cup \set z$ As $y \notin B_1$ $\displaystyle$ $=$ $\displaystyle \paren{B_2 \cap B_1} \cup \set z$ Set Difference with Empty Set is Self $\displaystyle \leadsto \ \$ $\displaystyle \card{B_3 \cap B_1}$ $=$ $\displaystyle \card{\paren{B_2 \cap B_1} \cup \set z}$ $\displaystyle$ $=$ $\displaystyle \card{\paren{B_2 \cap B_1} } + \card {\set z}$ As $z \notin B_2$ $\displaystyle$ $=$ $\displaystyle \card{\paren{B_2 \cap B_1} } + 1$ Cardinality of Singleton

$\blacksquare$