[proofplan]
We prove submodularity by comparing carefully chosen independent sets. First choose a basis of $A \cap B$, extend it to a basis of $A$, and then extend that basis further to a basis of $A \cup B$. The elements added in the final extension must lie in $B \setminus A$, so together with the original basis of $A \cap B$ they form an independent subset of $B$. Counting the sizes of these independent sets gives the desired rank inequality.
[/proofplan]
[step:Choose compatible bases for $A \cap B$, $A$, and $A \cup B$]
Let $A, B \subset E$ be arbitrary. Since $E$ is finite, every subset of $E$ has an independent subset of maximum cardinality. Choose an independent set $I_0 \subset A \cap B$ such that
\begin{align*}
|I_0| = r(A \cap B).
\end{align*}
Thus $I_0$ is a basis of $A \cap B$.
By the [matroid extension property](/page/Matroid), every independent subset of a set can be extended to a maximal independent subset of that set; since the matroid is finite, every maximal independent subset of a set has cardinality equal to the rank of that set. Applying this property to the independent set $I_0 \subset A$, choose an independent set $I_1 \subset A$ such that $I_0 \subset I_1$ and
\begin{align*}
|I_1| = r(A).
\end{align*}
Thus $I_1$ is a basis of $A$ and $I_0 \subset I_1$.
Applying the same [matroid extension property](/page/Matroid) inside $A \cup B$ to the independent set $I_1 \subset A \cup B$, choose an independent set $I_2 \subset A \cup B$ such that $I_1 \subset I_2$ and
\begin{align*}
|I_2| = r(A \cup B).
\end{align*}
Thus $I_2$ is a basis of $A \cup B$ and $I_1 \subset I_2$.
[guided]
We want to compare the four ranks appearing in the desired inequality:
\begin{align*}
r(A) + r(B) \geq r(A \cup B) + r(A \cap B).
\end{align*}
The useful choice is to make the relevant bases nested, so that the rank difference $r(A \cup B)-r(A)$ becomes the cardinality of a concrete set of newly added elements.
Start with a basis of the smallest relevant set. Since $E$ is finite, the subset $A \cap B$ has an independent subset of maximum cardinality. Choose such a set $I_0 \subset A \cap B$. By the definition of the rank function,
\begin{align*}
|I_0| = r(A \cap B).
\end{align*}
Thus $I_0$ is a basis of $A \cap B$.
Next apply the [matroid extension property](/page/Matroid): an independent subset of a set can be extended to a maximal independent subset of that set, and in a finite matroid every maximal independent subset of a set has cardinality equal to the rank of that set. Since $I_0$ is independent and $I_0 \subset A$, choose an independent set $I_1 \subset A$ with $I_0 \subset I_1$ and
\begin{align*}
|I_1| = r(A).
\end{align*}
Thus $I_1$ is a basis of $A$.
Now apply the same extension property inside $A \cup B$. Since $I_1$ is independent and $I_1 \subset A \subset A \cup B$, choose an independent set $I_2 \subset A \cup B$ with $I_1 \subset I_2$ and
\begin{align*}
|I_2| = r(A \cup B).
\end{align*}
Thus $I_2$ is a basis of $A \cup B$.
Define the newly added set $J$ by
\begin{align*}
J := I_2 \setminus I_1.
\end{align*}
We claim that $J \subset B \setminus A$. Since $I_2 \subset A \cup B$, every element of $J$ lies in $A \cup B$. Suppose for contradiction that some element $e \in J$ lies in $A$. Then $e \in A$ and $e \notin I_1$. Because $I_1$ is a maximal independent subset of $A$, the set $I_1 \cup \{e\}$ is dependent. But $I_1 \cup \{e\} \subset I_2$, contradicting the independence of $I_2$. Hence $J \cap A = \varnothing$, and therefore $J \subset B \setminus A$.
Now $I_0 \subset A \cap B \subset B$ and $J \subset B \setminus A \subset B$, so
\begin{align*}
I_0 \cup J \subset B.
\end{align*}
Also $I_0 \cup J \subset I_2$, and every subset of an independent set is independent, so $I_0 \cup J \in \mathcal I$. Therefore $I_0 \cup J$ is an independent subset of $B$. By the definition of $r(B)$,
\begin{align*}
|I_0 \cup J| \leq r(B).
\end{align*}
Because $I_0 \subset I_1$ and $J = I_2 \setminus I_1$, the sets $I_0$ and $J$ are disjoint. Hence
\begin{align*}
r(A \cap B) + |J| = |I_0| + |J| = |I_0 \cup J| \leq r(B).
\end{align*}
Finally, since $I_1 \subset I_2$ and $J = I_2 \setminus I_1$, we have the disjoint union
\begin{align*}
I_2 = I_1 \cup J.
\end{align*}
Therefore
\begin{align*}
r(A \cup B) = |I_2| = |I_1| + |J| = r(A) + |J|,
\end{align*}
so
\begin{align*}
|J| = r(A \cup B) - r(A).
\end{align*}
Substituting this identity into the preceding inequality gives
\begin{align*}
r(A \cap B) + r(A \cup B) - r(A) \leq r(B).
\end{align*}
Rearranging terms yields
\begin{align*}
r(A) + r(B) \geq r(A \cup B) + r(A \cap B).
\end{align*}
Since $A, B \subset E$ were arbitrary, the rank function $r$ is submodular.
[/guided]
[/step]
[step:Show that the newly added elements lie in $B \setminus A$]
Define
\begin{align*}
J := I_2 \setminus I_1.
\end{align*}
Since $I_2 \subset A \cup B$ and $I_1$ is a basis of $A$, every element of $J$ lies in $B \setminus A$.
Indeed, if $e \in J \cap A$, then $e \in A$ and $e \notin I_1$. Since $I_1$ is a maximal independent subset of $A$, the set $I_1 \cup \{e\}$ is dependent. But $I_1 \cup \{e\} \subset I_2$, contradicting the independence of $I_2$. Hence $J \cap A = \varnothing$, and therefore $J \subset B \setminus A$.
[/step]
[step:Build an independent subset of $B$ whose size gives the inequality]
Since $I_0 \subset I_1 \subset I_2$ and $J = I_2 \setminus I_1$, the set $I_0 \cup J$ is a subset of $I_2$. Because every subset of an independent set is independent, $I_0 \cup J \in \mathcal I$.
Also $I_0 \subset A \cap B \subset B$ and $J \subset B \setminus A \subset B$, so
\begin{align*}
I_0 \cup J \subset B.
\end{align*}
Therefore $I_0 \cup J$ is an independent subset of $B$, and by the definition of $r(B)$,
\begin{align*}
|I_0 \cup J| \leq r(B).
\end{align*}
Because $I_0 \subset I_1$ and $J = I_2 \setminus I_1$, the sets $I_0$ and $J$ are disjoint. Hence
\begin{align*}
r(A \cap B) + |J| = |I_0| + |J| = |I_0 \cup J| \leq r(B).
\end{align*}
[/step]
[step:Convert the count into the submodular inequality]
Since $I_1 \subset I_2$ and $J = I_2 \setminus I_1$, we have the disjoint union
\begin{align*}
I_2 = I_1 \cup J.
\end{align*}
Thus
\begin{align*}
r(A \cup B) = |I_2| = |I_1| + |J| = r(A) + |J|.
\end{align*}
Equivalently,
\begin{align*}
|J| = r(A \cup B) - r(A).
\end{align*}
Substituting this into the inequality from the previous step gives
\begin{align*}
r(A \cap B) + r(A \cup B) - r(A) \leq r(B).
\end{align*}
Rearranging terms yields
\begin{align*}
r(A) + r(B) \geq r(A \cup B) + r(A \cap B).
\end{align*}
Since $A, B \subset E$ were arbitrary, the rank function $r$ is submodular.
[/step]
