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

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

Let $B_1, B_2, V \subseteq S$.

Let $V \subseteq B_2$.

Then:

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


Proof

We have:

\(\displaystyle \card {B_1}\) \(=\) \(\displaystyle \card{ \paren{B_1 \cap B_2} \cup \paren{B_1 \setminus B_2} }\) Set Difference Union Intersection
\(\displaystyle \) \(=\) \(\displaystyle \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

\(\displaystyle \card {B_2}\) \(=\) \(\displaystyle \card{ \paren{B_2 \cap B_1} \cup \paren{B_2 \setminus B_1} }\) Set Difference Union Intersection
\(\displaystyle \) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \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$