I was studying sub modular functions and was trying to prove the equivalence of different definitions of sub modular functions.
Consider this first definition:
$$ \forall A \subseteq B , s \notin B, F(A \cup \{s\}) - F(A) \geq F(B \cup \{ s \}) -F(B)$$
I was trying to show that the following was equivalent:
$$\forall A,B \subseteq V : F(A) + F(B) \geq F(A \cup B) + F(A \cap B)$$
I've been told that its suppose to be a simple exercise but I've had a hard time starting such a proof. Intuitively, I feel that the correct thing might be to use exclusion-inclusion rule for sets, but wasn't sure how to. Also, are sub modular functions suppose to be linear? Because without a property like that I cannot think of how to a expand such an expression like:
$$F(A \cup \{s\})$$
or
$$ F(A \cup B) $$
Maybe someone can start off the proof so that I can try finishing it off? Or maybe provide the first direction of the implication so that I can do the other? I feel I might not know enough of the properties of sub modular function so to start this. Or maybe provide a list of properties I should be considering using?
I usually provide more of my thoughts but I am a little stuck because I don't know what rules I am allowed to use to expand any of the terms in the equations.
I think I got one direction of the equivalence. The goal is to show:
$$ \forall A \subseteq B , s \notin B, F(A \cup \{s\}) - F(A) \geq F(B \cup \{ s \}) -F(B) $$
$$\iff \forall A,B \subseteq V : F(A) + F(B) \geq F(A \cup B) + F(A \cap B)$$
I think I got the following implication ($\Leftarrow$).
The key step is the following definition:
Let $C \subseteq B$ and $s \notin B$ and define $A = C \cup \{s\}$. Then:
$$F(A) + F(B) \geq F(A \cup B) + F(A \cap B)$$
becomes:
$$ F(C \cup \{s\}) + F(B) \geq F(C \cup \{s\} \cup B) + F((C \cup \{s\}) \cap B) $$
After some algebra and some re-arranging we get:
$$ F(C \cup \{s\}) + F(B) \geq F(C \cup B \cup \{s\}) + F((C \cap B) \cup (\{s\} \cap B)) $$
Notice that since $C \subseteq B$ then $C \cup B = C$ and similarly, $C \cap B = C$ is true. Also notice that since $s$ is defined to not be in B, then the intersection of $s$ and $B$ is the empty set i.e. $B \cap \{ s \} = \emptyset$. Hence:
$$ F(C \cup \{s\}) + F(B) \geq F(B \cup \{s\}) + F((C \cap B) \cup (\{s\} \cap B)) $$
$$ F(C \cup \{s\}) + F(B) \geq F(B \cup \{s\}) + F(C \cup (\emptyset)) $$
$$ F(C \cup \{s\}) + F(B) \geq F(B \cup \{s\}) + F(C) $$
Now, after re-arranging some more terms we get the desired implication:
$$ F(C \cup \{s\}) - F(C) \geq F(B \cup \{s\}) - F(B) $$
where $C \subseteq B$ and $s \notin B$.
However, I am still missing the other direction to complete the if and only if.