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

Jump to navigation
Jump to search

This article needs proofreading.Please check it for mathematical errors.If you believe there are none, please remove `{{Proofread}}` from the code.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Proofread}}` from the code. |

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