# Proving equivalence of different definitions of sub modular functions

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.