In the Wikipedia entry for Dual matroid, an early section states
An alternative definition of the dual matroid is that its basis sets are the complements of the basis sets of $M$. The basis exchange axiom, used to define matroids from their bases, is self-complementary, so the dual of a matroid is necessarily a matroid.
There is also a survey paper by James Oxley, a well-known expert on matroids. In particular, on p. 11 of the paper, Oxley states that the dual of a matroid is itself a matroid, but points us to his book for the proof.
I do not have access to the book, and I'm having a hard time seeing why the dual of a matroid satisfies the exchange property in one particular case.
Suppose we have a matroid $M=(S, I)$. Suppose we define $I^\prime$ as the set of all $C^\prime \subseteq S$ such that $S-C^\prime$ contains some maximal subset $C \in I$. Now suppose further that we have $A^\prime \in I^\prime$ and $B^\prime \in I^\prime$, with $|A^\prime| < |B^\prime|$, and $S-A^\prime$ contains some maximal subset $A \in I$, and $S-B^\prime$ contains some maximal subset $B \in I$.
Now if $B^\prime – A^\prime – A \neq \emptyset$, then it is easy to show that for any $x^\prime \in B^\prime – A^\prime – A$, we have
$$
S – (A^\prime \cup \{x^\prime\} ) \supseteq A,
$$
resulting in $A^\prime \cup \{x^\prime\} \in I^\prime$, and hence the exchange property is satisfied.
Next, if $B^\prime – A^\prime – A = \emptyset$, and $B\cap H=\emptyset$, where $H \equiv (S – B^\prime) – (S – A^\prime – A)$, then it is easy to show that for any $x^\prime \in B^\prime – A^\prime$, we have
$$
S – (A^\prime \cup \{x^\prime\} ) \supseteq B,
$$
and hence the exchange property is again satisfied.
I am stumped regarding the remaining case: if $B^\prime – A^\prime – A = \emptyset$, but $B\cap H \neq \emptyset$. In this case, it seems that for any $x^\prime \in B^\prime – A^\prime$, we are certain that $S – (A^\prime \cup \{x^\prime\} )$ does not contain fully either $A$ or $B$. Hence, we must prove that in this situation, there exists some $x^\prime \in B^\prime – A^\prime$ such that $S – (A^\prime \cup \{x^\prime\} )$ contains some other maximal subset $C \in I$. I have no clue how to do this.
Best Answer
I will alter your notation a bit. Let $M = (S, \mathcal I)$ be a matroid with a set of bases $\mathcal B$, and consider its dual $M^* = (S,\mathcal I^*)$ with $\mathcal I^* = \{C\subseteq S: \exists B_C \in \mathcal B \text{ s.t. }C\cap B_C=\emptyset\}$. We wish to prove that the independent set exchange property holds for $M^*$.
Consider any two sets $X,Y \in \mathcal I^*$ with $|X| > |Y|$. Then $\exists B_X, B_Y \in \mathcal B$ such that $B_X \cap X = \emptyset$ $B_Y \cap Y = \emptyset$. Furthermore, observe that $B_X \cap Y\subseteq Y\setminus X$ and that $(B_X\setminus Y) \cap (X\setminus Y) = \emptyset$. We know that $\exists B\in \mathcal B$ such that $B_X\setminus Y\subseteq B\subseteq S\setminus Y$ because the Steinitz exchange lemma (see below) guarantees its existence. Now, suppose for contradiction that $X\setminus Y\subseteq B$. Then we would have: \begin{align} |B_X| &= |B_X\setminus Y| + |B_X\cap Y| \\ &\leq |B_X\setminus Y| + |Y\setminus X| \\ &<|B_X\setminus Y| + |X\setminus Y| \qquad \left(\text{because }|X|>|Y|\right)\\ &\leq |B| \qquad \left(\text{because }(B_X\setminus Y) \cap (X\setminus Y) = \emptyset\right) \end{align} This is clearly absurd: $B,B_X \in \mathcal B$, yet $|B_X| < |B|$! It follows that $X\setminus Y\nsubseteq B$. As a result, there must be some $x\in X\setminus Y$ such that $x\notin B$. For such an $x$, we find that $Y\cup\{x\} \in \mathcal I^*$! Hence, the exchange property holds for $M^*$. It does not take much more work to prove that $M^*$ is a matroid.
Proof: Because $A$ is a basis of $M$, $A\setminus \{a\} \in \mathcal I$. By the augmentation property of matroids, $\exists b \in B\setminus (A\setminus \{a\})$ such that $(A\setminus \{a\})\cup \{b\} \in \mathcal I$. Since $a \in A\setminus B$, we know that $b \in B\setminus A$. In addition, $|(A\setminus \{a\})\cup \{b\}| = |A| = |B|$, so we have $(A\setminus \{a\})\cup \{b\} \in \mathcal B$. $\square$