User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 5

This page needs proofreading. Please check it for mathematical errors. If you believe there are none, please remove {{Proofread}} from the code. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Proofread}} from the code.

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:

\(\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

$\blacksquare$