Element Depends on Independent Set iff Union with Singleton is Dependent/Lemma

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $X \in \mathscr I$.

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

Let $X \cup \set x$ be dependent.


Let $A \in \mathscr I$ such that $A \subseteq X \cup \set x$.


Then:

$\size A \le \size X$


Proof

Case 1: $x \in A$

Let $x \in A$.

We have:

\(\displaystyle A \setminus \set x\) \(\subseteq\) \(\displaystyle \paren {X \cup \set x} \setminus \set x\) Set Difference over Subset
\(\displaystyle \) \(=\) \(\displaystyle \paren {X \setminus \set x} \cup \paren {\set x \setminus \set x}\) Set Difference is Right Distributive over Union
\(\displaystyle \) \(=\) \(\displaystyle X \cup \paren {\set x \setminus \set x}\) Set Difference with Disjoint Set
\(\displaystyle \) \(=\) \(\displaystyle X \cup \O\) Set Difference with Superset is Empty Set
\(\displaystyle \) \(=\) \(\displaystyle X\) Union with Empty Set


Aiming for a contradiction, suppose:

$A \setminus \set x = X$

Then:

\(\displaystyle X \cup \set x\) \(=\) \(\displaystyle \paren {A \setminus \set x} \cup \set x\)
\(\displaystyle \) \(=\) \(\displaystyle A\) Set Difference Union Second Set is Union

So:

$X \cup \set x$ is independent.

This contradicts:

$X \cup \set x$ is dependent.


So:

$A \setminus \set x \subsetneq X$

Then:

\(\displaystyle \size X\) \(>\) \(\displaystyle \size {A \setminus \set x}\) Cardinality of Proper Subset of Finite Set
\(\displaystyle \) \(=\) \(\displaystyle \size A - \size {\set x}\) Cardinality of Set Difference with Subset
\(\displaystyle \) \(=\) \(\displaystyle \size A - 1\) Cardinality of Singleton

So:

$\size A \le \size X$

$\Box$


Case 2: $x \notin A$

Let $x \notin A$.

Then:

\(\displaystyle A\) \(=\) \(\displaystyle \paren {X \cup \set x} \cap A\) Intersection with Subset is Subset
\(\displaystyle \) \(=\) \(\displaystyle \paren {X \cap A} \cup \paren {\set x \cap A}\) Intersection Distributes over Union
\(\displaystyle \) \(=\) \(\displaystyle \paren {X \cap A} \cup \O\) Intersection With Singleton is Disjoint if Not Element
\(\displaystyle \) \(=\) \(\displaystyle X \cap A\) Union with Empty Set

From Intersection with Subset is Subset:

$A \subseteq X$

From Cardinality of Subset of Finite Set:

$\size A \le \size X$

$\Box$


In either case:

$\size A \le \size X$

$\blacksquare$