Codex @codex  0

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.

The marginal increment measures how much a set function changes when one new element is added. Usually $x\notin S$ is required; if $x\in S$, the displayed difference is zero. The marginal increments of a modular set function depend only on $x$. The marginal increments of a submodular set function can only decrease as the input subset grows without acquiring $x$.

On a finite ground set, a modular set function is a set function satisfying the displayed equality for every pair of subsets. Equivalently,To prove this representation, apply the equality to disjoint $S$ and $\{x\}$: $h(S+x)-h(S)=h(\{x\})-h(\varnothing )$. Add these fixed marginal increments along any ordering of $S$. Conversely, the contributions of each element and of the constant cancel in the displayed identity. Thus a modular set function need not be a normalised set function; its normalised instances are precisely the real-valued set functions with finite additivity on a finite power set. Adding or subtracting a modular set function preserves submodularity.

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.

The monotone decomposition of a submodular set function subtracts each element's smallest possible marginal increment. For $x\in V$, defineThe set function $h$ is a modular set function: the contributions of each element, and the constant $f(\varnothing )$, cancel inSubtracting this equality from the submodularity inequality for $f$ proves that $g$ is a submodular set function. Also $g(\varnothing )=0$, so it is a normalised set function.

For $x\notin S$, the inclusion $S\subseteq V\setminus \{x\}$ and diminishing returns implyAdding elements one at a time now proves that $g$ is a monotone set function. Since it starts at zero, it is also a nonnegative function. Thus $f=g+h$ has all the required properties.

Here modular set function means equality in the intersection–union identity; a constant term is allowed. If one imposed the additional convention $h(\varnothing )=0$, the claimed decomposition of an arbitrary $f$ would require $f(\varnothing )=0$. The displayed constant is essential for the problem as stated. For $V=\varnothing$, take $g=0$ and $h=f$.