# Union with Disjoint Singleton is Dependent if Element Depends on Subset

## Theorem

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

Let $A \subseteq S$.

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

If $x$ depends on $A$ then $A \cup \set x$ is dependent

## Proof

We proceed by Proof by Contraposition.

Let $A \cup \set x$ be independent.

$A$ is independent

We have:

 $\ds \map \rho {A \cup \set x}$ $=$ $\ds \size {A \cup \set x}$ Rank of Independent Subset Equals Cardinality $\ds$ $=$ $\ds \size A + \size{\set x}$ Corollary to Cardinality of Set Union $\ds$ $=$ $\ds \size A + 1$ Cardinality of Singleton $\ds$ $>$ $\ds \size A$ $\ds$ $=$ $\ds \map \rho A$ Rank of Independent Subset Equals Cardinality

Then $x$ does not depend on $A$ by definition.

The theorem holds by the Rule of Transposition.

$\blacksquare$