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

From ProofWiki
Jump to navigation Jump to search


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$


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


We have:

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