Union with Disjoint Singleton is Dependent if Element Depends on Subset

From ProofWiki
Jump to navigation Jump to search



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.

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$