Submodularity of matroid rank ($r(A)+r(B)\ge r(A\cap B)+r(A\cup B)$)

The rank of a matroid is a normalised set function, a monotone set function, and a submodular set function. Adding one element increases it by at most one.

Proof of submodularity. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, then extend it to one $I_U$ in $A\cup B$. The matroid independence axioms make their sizes $r(A\cap B)$, $r(A)$ and $r(A\cup B)$. Every element of $I_U\setminus I_A$ lies outside $A$, since otherwise it could be added to $I_A$ inside $A$. Hence $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, so its size $r(A\cap B)+r(A\cup B)-r(A)$ is at most $r(B)$.

The remaining assertions follow from the definition of the rank of a matroid. The empty set has maximum independent size zero, increasing the available subset cannot reduce that maximum, and deleting a newly added element from an independent subset decreases its size by at most one.