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

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 $\mathscr B$ satisfy the base axiom: User:Leigh.Samphier/Matroids/Axiom:Base Axioms (Matroid)/Axiom 1

Let $B_1, B_2 \in \mathscr B$.

Let $U \subseteq B_1$ and $V \subseteq B_2$ such that:

$\card V < \card U$

Let $B_2 \cap \paren{U \setminus V} = \O$.

Then:

$\exists B_3 \in \mathscr B$:

$V \subseteq B_3$

$\card{B_1 \cap B_3} > \card{B_1 \cap B_2}$

Proof

Lemma 2

$\forall B_1, B_2 \in \mathscr B : \card{B_1} = \card{B_2}$

where $\card{B_1}$ and $\card{B_2}$ denote the cardinality of the sets $B_1$ and $B_2$ respectively.

$\Box$

Let $U, V \in \mathscr I$ such that:

$\card V < \card U$

Lemma 3

$\card{V \setminus U} < \card{U \setminus V}$

$\Box$

Lemma 4

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

$\Box$

From Subset of Set Difference iff Disjoint Set:

$U \setminus V \subseteq B_1 \setminus B_2$

We have:

\(\ds \card{B_2}\)

\(=\)

\(\ds \card{B_1}\)

Lemma 2

\(\ds \leadsto \ \ \)

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

\(=\)

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

\(\ds \leadsto \ \ \)

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

\(=\)

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

Subtract $\card{B_1 \cap B_2}$ from both sides of equation

\(\ds \)

\(\ge\)

\(\ds \card{U \setminus V}\)

Cardinality of Subset of Finite Set

\(\ds \)

\(>\)

\(\ds \card{V \setminus U}\)

\(\ds \)

\(\ge\)

\(\ds \card{V \setminus B_1}\)

As $U \subseteq B_1$

\(\ds \leadsto \ \ \)

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

\(>\)

\(\ds 0\)

Subtract $\card{V \setminus B_1}$ from both sides of equation

From the contrapositive statement of Cardinality of Empty Set:

$\paren{B_2 \setminus B_1} \setminus V \ne \O$

Hence: $\exists y \in \paren{B_2 \setminus B_1} \setminus V$

From $(\text B 1)$:

$\exists z \in B_1 \setminus B_2 : \paren{B_2 \setminus \set y} \cup \set z \in \mathscr B$

Let:

$B_3 = \paren{B_2 \setminus \set y} \cup \set z$

We have:

\(\ds V\)

\(\subseteq\)

\(\ds B_2 \setminus \set y\)

As $y \notin V$ and $V \subseteq B_2$

\(\ds \)

\(\subseteq\)

\(\ds \paren{B_2 \setminus \set y} \cup \set z\)

Set is Subset of Union

\(\ds \)

\(=\)

\(\ds B_3\)

Lemma 5

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

$\Box$

Hence:

$\card{B_1 \cap B_3} > \card{B_1 \cap B_2}$

$\blacksquare$