# Leigh.Samphier/Sandbox/Matroid Base Axiom Implies Sets Have Same Cardinality

## Theorem

Let $S$ be a finite set.

Let $\mathscr B$ be a non-empty set of subsets of $S$.

Let $\mathscr B$ satisfy the base axiom:

 $(\text B 1)$ $:$ $\displaystyle \forall B_1, B_2 \in \mathscr B:$ $\displaystyle x \in B_1 \setminus B_2 \implies \exists y \in B_2 \setminus B_1 : \paren {B_1 \setminus \set x} \cup \set y \in \mathscr B$

Then:

$\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.

## Proof

$\exists B_1, B_2 \in \mathscr B : \card{B_1} \ne \card{B_2}$
$\card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : C_1, C_2 \in \mathscr B : \card{C_1} \ne \card{C_2}}$
$\card{B_1} > \card{B_2}$
$\exists x \in B_1 \setminus B_2$
$\exists y \in B_2 \setminus B_1 : \paren {B_1 \setminus \set x} \cup \set y \in \mathscr B$

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

We have:

 $\ds \card{B_3 \cap B_2}$ $=$ $\ds \card{\paren{\paren {B_1 \setminus \set x} \cup \set y} \cap B_2}$ $\ds$ $=$ $\ds \card{\paren{\paren {B_1 \setminus \set x} \cap B_2} \cup \paren {\set y \cap B_2} }$ Intersection Distributes over Union $\ds$ $=$ $\ds \card{\paren{\paren {B_1 \setminus \set x} \cap B_2} \cup \set y }$ Intersection with Subset is Subset $\ds$ $=$ $\ds \card{\paren{\paren {B_1 \cap B_2 } \setminus \set x } \cup \set y }$ Intersection with Set Difference is Set Difference with Intersection $\ds$ $=$ $\ds \card{\paren {B_1 \cap B_2 } \cup \set y }$ Set Difference with Disjoint Set $\ds$ $>$ $\ds \card{B_1 \cap B_2 }$ Cardinality of Proper Subset of Finite Set

This contradicts the choice of $B_1$ and $B_2$ as:

$\card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : C_1, C_2 \in \mathscr B : \card{C_1} \ne \card{C_2}}$

It follows that:

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

$\blacksquare$