Union of Matroid Base with Element of Complement is Dependent

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 $B \subseteq S$ be a base of $M$.

Let $x \in S \setminus B$.

Then:

$B \cup \set x$ is a dependent superset of $B$

Proof

From Set is Subset of Union:

$B \subseteq B \cup \set x$

Because $x \in B \cup \set x$ and $x \notin B$:

$B \ne B \cup \set x$

Hence:

$B \subsetneq B \cup \set x$

By definition of base:

$B$ is a maximal independent subset

Hence:

$B \cup \set x \notin \mathscr I$

$\blacksquare$