Submodular set function ($f(A)+f(B)\ge f(A\cup B)+f(A\cap B)$)

A set function is submodular if $f(A)+f(B)\ge f(A\cup B)+f(A\cap B)$ for every pair of subsets. Entropy submodularity is a fundamental example.

Every real-valued submodular set function on a finite ground set $V$ is the sum of a normalised set function $g$ that is nonnegative, monotone and submodular, and a modular set function $h$. A useful explicit choice isProof. The formula makes $h$ a modular set function, so $g$ is a submodular set function. It is a normalised set function because $h(\varnothing )=f(\varnothing )$. For $x\notin S$, diminishing returns gives ${\Delta }_{x}f(S)\ge {\Delta }_{x}f(V\setminus \{x\})=d_x$, hence ${\Delta }_{x}g(S)\ge 0$. Thus $g$ is a monotone set function, and starting at zero makes it a nonnegative function. The decomposition separates all potentially negative terminal marginal increments into the simple additive term. A constant term in $h$ is necessary unless $f$ is already a normalised set function.

Suppose $f$ is a normalised set function and a submodular set function, and $T_1,\dots ,T_t\subseteq T$ cover every element of $T$ exactly $k$ times, counting repetitions in the indexed collection. Then the displayed inequality holds. Neither the monotone set function property nor the nonnegative function property is required.

Proof. Fix an ordering of $T$ and write $a_j=f(P_j)-f(P_{j-1})$ for its successive marginal increments. The chain lower bound for a submodular set function gives $f(T_i)\ge {\sum }_{x_j\in T_i}{a}_j$. Summing counts each $a_j$ exactly $k$ times, and ${\sum }_j{a}_j=f(T)$. Exact coverage matters because the $a_j$ may be negative. For a monotone set function, the same argument also allows each element to occur at least $k$ times.

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.

For a real-valued set function on a finite ground set, the displayed marginal increment comparison is equivalent to submodularity. The interpretation is that an additional item contributes no more after more items have already been chosen. This concerns relative increments, which may be negative; it does not assert the monotone set function property.

Proof. Applying the defining inequality for a submodular set function to $A+x$ and $B$ gives the comparison immediately. Conversely, list $A\setminus B=\{x_1,\dots ,x_m\}$ and compare adding these elements, in the same order, first to $A\cap B$ and then to $B$. At every step the first conditioning set is contained in the second, so the first marginal increment is at least the second. The telescoping sums givewhich rearranges to submodularity.