intersection and union of two independent sets is independent in matroid

Question

As we know that, a matroid $M$ is a pair $(U,\mathcal{I})$ where $U$ is a finite set and $\mathcal{I}\subseteq \mathcal{P}(U)$ satisfying

• $\varnothing \in \mathcal{I}$,
• if $Y \in \mathcal{I}$ and $X\subseteq Y$, then $X\in \mathcal{I}$,
• $X,Y\in \mathcal{I}$ with $|X|<|Y|$, there exists $y\in Y-X$ such that $X\cup \{y\} \in \mathcal{I}$.

The set $U=U(M)$ is called ground set of $M$ and $\mathcal{I}=\mathcal{I}(M)$ is called the collection of independent sets of $M$.

How to show that intersection and union of two independent set is independent or not? Anybody can help?

Answer 1

Recall the definition of matroid:

• The first axiom shows that any matroid is non-empty.
• The second axiom is called hereditary, it means that all the subsets of an independent set is also independent.
• The third axiom is called independence augmention axiom. Note that there is a important condition that $|X| < |Y|$.

The intersection of two independent sets is independent.

Let $A, B$ are independent set, and $A \cap B$ is the subset of $A$ (or $B$). According the hereditaty axiom, $A \cap B$ is also independent.

The union of two independent sets is not independent in general.

Suppose $(U, \mathcal{I})$ is a maroid. Let $$U' = \bigcup_{A \in I}A$$ Thus, every element in $U'$ is at least in one independent set. And $(U', \mathcal{I})$ is also a maroid.

If the union of two independent sets is independent, then the union of all independent sets is independent, too. It means that $U'$ is an independent set. Also, we can conclude a strange result:

For $(U', \mathcal{I})$, we have $\mathcal{I} = \mathcal{P}(U')$.

For $(U, \mathcal{I})$, $$X \in \mathcal{I} \Leftrightarrow X \subseteq U'$$ which leads that $(U, \mathcal{I})$ and $(U', \mathcal{I})$ become trivial.

One can easily to construct a countexample, such as $U = \{a, b\}$, $\mathcal{I} = \{ \varnothing, \{a\}, \{b\} \}$ and $U \not\in \mathcal{I}$. Note that since $|\{a\}| = |\{b\}|$, the independence augmention axiom is also holds in this case.