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

Let $x$ depend on $A$.

Then $A \cup \set x$ is a dependent subset of $M$.

Proof

We proceed by Proof by Contraposition.

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

By matroid axiom $(\text I 2)$:

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