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

From ProofWiki
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$