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

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, V \subseteq S$.

Let $V \subseteq B_2$.

Then:

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

Proof

We have:

\(\ds \card {B_1}\)

\(=\)

\(\ds \card{ \paren{B_1 \cap B_2} \cup \paren{B_1 \setminus B_2} }\)

Set Difference Union Intersection

\(\ds \)

\(=\)

\(\ds \card{B_1 \cap B_2} + \card{B_1 \setminus B_2}\)

Set Difference and Intersection are Disjoint and Corollary to Cardinality of Set Union

and

\(\ds \card {B_2}\)

\(=\)

\(\ds \card{ \paren{B_2 \cap B_1} \cup \paren{B_2 \setminus B_1} }\)

Set Difference Union Intersection

\(\ds \)

\(=\)

\(\ds \card{B_2 \cap B_1} + \card{B_2 \setminus B_1}\)

Set Difference and Intersection are Disjoint and Corollary to Cardinality of Set Union

\(\ds \)

\(=\)

\(\ds \card{B_2 \cap B_1} + \card{\paren{\paren{B_2 \setminus B_1} \cap V} \cup \paren{\paren{B_2 \setminus B_1} \setminus V} }\)

Set Difference Union Intersection

\(\ds \)

\(=\)

\(\ds \card{B_2 \cap B_1} + \card{\paren{B_2 \setminus B_1} \cap V} + \card{\paren{B_2 \setminus B_1} \setminus V}\)

Set Difference and Intersection are Disjoint and Corollary to Cardinality of Set Union

\(\ds \)

\(=\)

\(\ds \card{B_2 \cap B_1} + \card{V \setminus B_1} + \card{\paren{B_2 \setminus B_1} \setminus V}\)

Intersection with Set Difference is Set Difference with Intersection

$\blacksquare$