Chain lower bound for a submodular set function ($f(U)\ge {\sum }_{x_j\in U}(f(P_j)-f(P_{j-1}))$)

Let $f$ be a normalised set function that is a submodular set function, and order a finite subset $T=\{x_1,\dots ,x_n\}$. Set $P_j=\{x_1,\dots ,x_j\}$ and $P_0=\varnothing$. Then the displayed inequality holds for every $U\subseteq T$, with equality for $U=T$. The right side is a modular set function lying below $f$ on the power set of $T$ and touching it at the top.

Proof. Reveal the elements of $U$ in the chosen order. Immediately before adding $x_j\in U$, the conditioning set is $U\cap P_{j-1}\subseteq P_{j-1}$. By diminishing returns, its marginal increment is at least $f(P_j)-f(P_{j-1})$. Sum and use $f(\varnothing )=0$. The same telescoping sum gives equality at $T$. The individual increments need not be nonnegative.