What is the proof that the rank of a matroid is sub-modular? Recall the definition of the rank of a matroid $(V, \mathcal{I})$:
$$ r(A) = \operatorname{rank}(A) = \max_{I \in \mathcal{I}}\{ | A \cap I | \} = \max\{ |I| : I \subseteq A, I \in \mathcal{I} \}$$
I was trying to prove that the rank of a matroid is a sub-modular function, i.e. that the following inequality holds for all subsets of the ground set (i.e. $\forall A, B \subseteq V$):
$$ r(A) + r(B) \geq r(A \cup B) + r(A \cap B)$$
I tried a "picture proof" by drawing a couple of sets and seeing how their intersection with independent elements behaved and I can only conclude that its in fact an equality. I am sure there is something wrong with that method and its not a real proof but wasn't sure how else to approach it. Does someone have a proof or a suggestion on good direction I might try to actually prove this result?
Also, is this suppose to be "intuitively obvious"? Because its not completely obvious for me.
 A: Start with $I_1$ maximal independent in $A\cap B$.  We have $r(A\cap B)=|I_1|$.  By the property of independent sets, we may extend $I_1$ to $I$, maximal independent in $A\cup B$.  We have $r(A\cup B)=|I|$.  Now, partition $I=I_2\cup I_3\cup I_4$, where $I_2\in A\setminus B$, $I_3\in B\setminus A$, $I_4\in A\cap B$.  By construction, $I_1\subseteq I_4$; however by the maximality of $I_1$, in fact $I_1=I_4$.  Hence $r(A\cup B)=|I_1|+|I_2|+|I_3|$.  This takes care of the RHS.
Now, $I_1\cup I_2$ is a subset of $I$, hence independent, and contained entirely in $A$.  It might not be maximal independent in $A$, so all we can say is $r(A)\ge |I_1|+|I_2|$.  By a similar argument $r(B)\ge |I_1|+|I_3|$.
Putting it all together, we get $$r(A)+r(B)\ge 2|I_1|+|I_2|+|I_3|=r(A\cup B)+r(A\cap B)$$

A bit more about the strictness.  Suppose our ground set is the edges of a triangle graph (three vertices, three edges called $a,b,c$), with all cycle-free sets independent.   That is, all subsets are independent, except all three edges together.  
Set $A=\{a,b\}$, $B=\{a,c\}$.  $r(A)=r(B)=2$, so LHS=$2+2=4$.  $r(A\cap B)=1$, since $A\cap B=\{a\}$.  However, $r(A\cup B)=2$, since $A\cup B=\{a,b,c\}$ yet all independent sets are of size 2 or less.  Hence RHS=$2+1=3$.
A: I am writing an answer to make sure I understand vadim's answer.
proof:
let $I_1 = \max_{I \in \mathcal{I}}\{|(A \cap B) \cap I|\}$, i.e., the maximal independent set of $A \cap B$. Recall the property of independent sets in matroids; if $|I| > |J|$ then there exists a sequence of elements $x_i \in I \setminus J$ such that at some point $|I| = |J \cup \{ x_1\} \cup ... \cup \{ x_k \}|$.
Now lets consider $I$, the maximal independent set of $A \cup B$. Obviously the size of $I$ cannot be less that $I_1$. i.e. $|I_1| \leq |I|$ (if the opposite where true, then clearly $I$ wouldn't be a maximally independent set of $A \cup B$!). Anyway, in the case where the inequality is strict $|I_1| < |I|$, then there exists one or more elements in $I$ not in $I_1$ that we can add to $I_1$ until $I_1$ matches in size to $I$. i.e. $|I| = |I_1 \cup \{ x_1\} ... \{ x_k \}|$. 
Once that last equality is true then we can reason about where the elements $x_i$ came from.
Clearly, none of the $x_i$'s came from the intersection $A \cap B$, since if that were true, then $I_1$ wouldn't be maximal. Hence, they came from $A \setminus B$ or  $B \setminus A$. Hence we have:
$$ I_1 \cup \{ x_1\} ... \{ x_k \} = I_1 \cup I_2 \cup I_3 $$
where $I_2 \subseteq A \setminus B$ and $I_3 \subseteq B \setminus A$. 
Now $I_1 \cup I_2 \subseteq A$, however it might not be maximal. Hence $r(A) \geq |I_1| + |I_2|$. Similarly for $I_1 \cup I_3 \subseteq B$ we have $r(B) \geq |I_1| + |I_3|$.
Hence we get:
$r(A) + r(B) \geq |I_1| + |I_2| + |I_1| + |I_3|$
However, notice that $r(A \cup B) = |I| = |I_1 \cup I_2 \cup I_3| = |I_1| + |I_2| + |I_3|$ and $r(A \cap B) = |I_1|$. Hence:
$$r(A \cup B) + r(A \cap B) = |I_2| + 2|I_1| + |I_3|$$
Which Concludes the proof:
$r(A) + r(B) \geq |I_1| + |I_2| + |I_1| + |I_3| = r(A \cup B) + r(A \cap B)$
A: For a quick counterexample to equality, let $B$ be a basis and suppose there's an $e$ not in $B$ such that $C(e,B)$ is the the $B$-fundamental circuit of $e$. Then:


*

*$r(B) = r(M)$,

*$r(e) = 1$,

*$r(B \cup e) = r(M)$, and

*$r(B \cap e) = r(\emptyset) = 0$.

