Intuitive interpretation of the alternative definition of sub modular functions

Question

I know that the the following definition is the "usual" definition of sub modularity:

$$ \forall A \subseteq B , s \notin B, F(A \cup \{s\}) - F(A) \geq F(B \cup \{ s \}) -F(B)$$

Which for me has a very clear intuitive interpretation. Adding an additional element to the larger set in question, does not provide as much marginal returns as it does adding it to the smaller set. i.e. "there are diminishing returns when making a set bigger and bigger". Thats, kind of what it means intuitively.

However, there is an alternative definition:

$$\forall A,B \subseteq V : F(A) + F(B) \geq F(A \cup B) + F(A \cap B)$$

however, I was not sure what to make of that definition. Why is that alternative definition "obviously" the same as the original? Is there an intuitive way to express the second definition such that its obvious that its equivalent to the first? How would some one interpret this second definition (and if you can, how would you link it with the interpretation of "diminishing returns")?

---

Notice that this question is not asking for a rigorous proof of equivalence for the two definitions. There is already a question about that.

Proving equivalence of different definitions of sub modular functions

Answer 1

Let $C\subseteq B$ and $ s \notin B$. then plugging in $A=C \cup \{s\}$ reduces your second definition to your first. To get this reduction I just tried to equate the four terms in some way (which didn't give me too much intuition). I think the best way to view the second definition is to see it as a sort of triangle inequality for sets. When you partition a set, the sum of the parts is greater than that of the whole. For example,

$$\begin{align} F(\{a,b,c\}) & \leq F(\{a,b\}) + F(\{c\}) \\ & \leq F(\{a\}) + F(\{b\}) + F(\{c\}) \end{align}$$

If you play around with it, you'll see that multiplicities (induced by intersections) come right out. For example,

$$ \begin{align} F(\{a,b,c\} + F(\{c\}) &\leq F(\{a,c\}) + F(\{b,c\}) \\ &\leq F(\{a\}) + F(\{b\}) + 2F(\{c\}) \end{align} $$

which is logically equivalent to the first statement.

Answer 2

In the alternative definition, let $A':=A\cap B$, $B':=A$ and $\Delta:=B\setminus A = B\setminus A'$. The definition amounts to $$F(B')+F(A'\cup\Delta)\geq F(B'\cup\Delta)+F(A'),$$ that is $$F(A'\cup\Delta) - F(A')\geq F(B'\cup\Delta)-F(B').$$ Note that $A'$ is always a subset of $B'$. So the above is saying the return is diminishing when making a set bigger.

Intuitively speaking, $$F(A\cup B) - F(A) \leq F(B) - F(A\cap B)$$ means by making both $A$ and $A\cap B$ bigger by the amount of $B\setminus A$, one gets less return on $A$ than $A\cap B$.