= Modular set function
{title2=$h(A)+h(B)=h(A\cup B)+h(A\cap B)$}
On a finite <ground set>, a <modular set function> is a <set function> satisfying the displayed equality for every pair of <subsets>. Equivalently,
$$
h(S)=c+\sum_{x\in S}a_x,
\qquad c=h(\varnothing),\quad a_x=h(\{x\})-h(\varnothing).
$$
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>.
Back to article page
