# Element Depends on Independent Set iff Union with Singleton is Dependent/Lemma

## Theorem

Let $M = \struct{S, \mathscr I}$ be a matroid.

Let $X \in \mathscr I$.

Let $x \in S : x \notin X$.

Let $X \cup \set x$ be dependent.

Let $A \in \mathscr I$ such that $A \subseteq X \cup \set x$.

Then:

$\size A \le \size X$

## Proof

#### Case 1: $x \in A$

Let $x \in A$.

We have:

 $\displaystyle A \setminus \set x$ $\subseteq$ $\displaystyle \paren {X \cup \set x} \setminus \set x$ Set Difference over Subset $\displaystyle$ $=$ $\displaystyle \paren {X \setminus \set x} \cup \paren {\set x \setminus \set x}$ Set Difference is Right Distributive over Union $\displaystyle$ $=$ $\displaystyle X \cup \paren {\set x \setminus \set x}$ Set Difference with Disjoint Set $\displaystyle$ $=$ $\displaystyle X \cup \O$ Set Difference with Superset is Empty Set $\displaystyle$ $=$ $\displaystyle X$ Union with Empty Set

$A \setminus \set x = X$

Then:

 $\displaystyle X \cup \set x$ $=$ $\displaystyle \paren {A \setminus \set x} \cup \set x$ $\displaystyle$ $=$ $\displaystyle A$ Set Difference Union Second Set is Union

So:

$X \cup \set x$ is independent.

$X \cup \set x$ is dependent.

So:

$A \setminus \set x \subsetneq X$

Then:

 $\displaystyle \size X$ $>$ $\displaystyle \size {A \setminus \set x}$ Cardinality of Proper Subset of Finite Set $\displaystyle$ $=$ $\displaystyle \size A - \size {\set x}$ Cardinality of Set Difference with Subset $\displaystyle$ $=$ $\displaystyle \size A - 1$ Cardinality of Singleton

So:

$\size A \le \size X$

$\Box$

#### Case 2: $x \notin A$

Let $x \notin A$.

Then:

 $\displaystyle A$ $=$ $\displaystyle \paren {X \cup \set x} \cap A$ Intersection with Subset is Subset $\displaystyle$ $=$ $\displaystyle \paren {X \cap A} \cup \paren {\set x \cap A}$ Intersection Distributes over Union $\displaystyle$ $=$ $\displaystyle \paren {X \cap A} \cup \O$ Intersection With Singleton is Disjoint if Not Element $\displaystyle$ $=$ $\displaystyle X \cap A$ Union with Empty Set
$A \subseteq X$
$\size A \le \size X$

$\Box$

In either case:

$\size A \le \size X$

$\blacksquare$