First, some definitions. Given a finite set $E$, a function $f: E \to \mathbb{R}$ is submodular if, for any $A,B \subseteq E$, we have $$f(A) + f(B) \geq f(A \cup B) + f(A \cap B).$$
The function $f$ is monotone if $f(A) \leq f(B)$ whenever $A \subseteq B$.
Given a submodular function $f$, I want to make it monotone as follows: define the monotone function $g(A) := \min\limits_{T \supseteq A} f(T)$. In other words, I (potentially) reduce the value of each set to the minimum value of any set containing it.
Clearly the new function $g$ is monotone. I also read that it should be submodular, but I am having trouble showing that. Why is $g$ also submodular?
Thanks
Among all sets containing $A$, let $S$ be a set containing $A$ that minimises $f(S)$, so $g(A) = f(S)$. Likewise choose $T$ containing $B$ such that $g(B) = f(T)$.
Then by submodularity of $f$: $$g(A) + g(B) = f(S) + f(T) \geq f(S\cup T) + f(S \cap T)$$
By definition of $G$:
$$f(S\cup T) + f(S \cap T) \geq g(S\cup T) + g(S \cap T)$$
Finally, since $g$ is monotone and $A\subseteq S$, $B\subseteq T$, we get:
$$g(S\cup T) + g(S \cap T) \geq g(A\cup B) + g(A \cap B)$$
Which completes the proof.