Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Base Axiom/Lemma

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

Let $B_1, B_2 \subseteq S$.

Let $x \in B_1 \setminus B_2$.

Let $y \in B_2 \setminus B_1$.


Then:

$\paren{B_1 \setminus \set x} \cup \set y = \paren{B_1 \cup \set y} \setminus \set x$


Proof

From Singleton of Element is Subset:

$\set x \subseteq B_1 \setminus B_2$

and

$\set y \subseteq B_2 \setminus B_1$


From Set Difference Disjoint with Reverse:

$\paren{B_1 \setminus B_2} \cap \paren{B_2 \setminus B_1} = \O$


From Subsets of Disjoint Sets are Disjoint:

$\set x \cap \set y = \O$


We have:

\(\displaystyle \paren{B_1 \cup \set y} \setminus \set x\) \(=\) \(\displaystyle \paren {B_1 \setminus \set x} \cup \paren {\set y \setminus \set x}\) Set Difference is Right Distributive over Union
\(\displaystyle \) \(=\) \(\displaystyle \paren {B_1 \setminus \set x} \cup \set y\) Set Difference with Disjoint Set

$\blacksquare$