Set function ($f:\mathcal{P}(V)\to \mathbb{R}$)

A set function assigns a value to each set in a specified family of sets. In finite optimization the usual form is $f:\mathcal{P}(V)\to \mathbb{R}$, a real-valued function on the power set of a ground set $V$.

For a finite set $V$, the rule $f(S)=|S|$ is a set function counting selected elements; $f(S)={\sum }_{v\in S}w(v)$ instead totals their weights. A measure is also a set function, but its domain of a function is a specified collection of measurable sets, and its values can include infinity. The intended family and codomain are therefore part of the definition.

Let $V$ be a nonempty finite set with real weights $w(v)$. For nonempty subsets put $f(S)={\max }_{v\in S}w(v)$ and choose $f(\varnothing )=c\le {\min }_{v\in V}w(v)$. This defines a monotone set function and a submodular set function on the full power set.

To check diminishing returns, for $x\notin S$ the marginal increment is ${\Delta }_{x}f(S)=\max \{0,w(x)-f(S)\}$. If $A\subseteq B$, then $f(A)\le f(B)$, so ${\Delta }_{x}f(A)\ge {\Delta }_{x}f(B)$. Choosing the value of the empty set no larger than every weight makes this calculation valid even for $A=\varnothing$.

For weights $2,5,9$ and $c=0$, adding the weight-$5$ element to a weight-$2$ selection increases $f$ by $3$; adding it to a selection already containing weight $9$ increases $f$ by zero.

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.

A set function on the power set of a ground set $V$ is symmetric when complementary subsets have equal values. A hypergraph cut function has this property because swapping the two sides changes no crossing hyperedge. If a symmetric set function is also a monotone set function, it is constant: $f(\varnothing )\le f(S)\le f(V)=f(\varnothing )$.

A real-valued set function $f:\mathcal{P}(V)\to \mathbb{R}$ is monotone in the nondecreasing convention whenFor a finite ground set $V$, this is equivalent to every marginal increment being nonnegative. Necessity follows by comparing $S$ and $S\cup \{x\}$. Conversely, enumerate the finitely many elements of $B\setminus A$ and add them one at a time; summing their nonnegative increments gives $f(B)-f(A)\ge 0$. A normalised set function with this property is a nonnegative function.

The finiteness condition in that converse matters. On $V=\mathbb{N}$, define $f(S)=1$ for finite $S$ and $f(S)=0$ for infinite $S$. Adding one element never changes whether $S$ is finite, so all marginal increments are zero. Yet $f(\varnothing )=1>0=f(\mathbb{N})$, so the set function is not monotone. Single-element tests alone cannot compare sets differing in infinitely many elements.

A set function is normalised when its value at the empty set is zero. Subtracting the constant $f(\varnothing )$ normalises any real-valued set function and preserves submodularity and the monotone set function property.

A real-valued set function $F$ on an algebra of sets is finitely additive whenfor disjoint members of the algebra. Taking both sets empty gives $F(\varnothing )=0$, and induction extends the identity to every finite disjoint union.

On the full power set of a finite set $V$, every subset is a disjoint union of singletons, soThus arbitrary signed weights on the points describe exactly these finitely additive set functions. Summing the pointwise indicator function identity for the inclusion-exclusion principle against those weights gives the corresponding identity for $F$.

The full-power-set qualification matters: on the smaller algebra $\{\varnothing ,\{a,b\}\}$, the value $F(\{a,b\})$ does not specify $F(\{a\})$ or $F(\{b\})$, because the singletons are outside the domain. One must not apply the singleton formula to undefined values.

A set function is supermodular whenEquivalently, $-f$ is a submodular set function. On a finite ground set, this means increasing marginal increments: if $A\subseteq B$ and $x\notin B$, then ${\Delta }_{x}f(A)\le {\Delta }_{x}f(B)$.

For example, $f(S)=|S{|}^2$ has increment $2|S|+1$, which increases with the cardinality of $S$. In a convex cooperative game, supermodularity expresses increasing gains from joining larger coalitions; the corresponding marginal allocations lie in the core of a cooperative game.

A set function $f:\mathcal{P}(V)\to \mathbb{R}$ is submodular whenfor every $A,B\subseteq V$. For finite $V$, this is equivalent to diminishing returns:The marginal increment of an element can only decrease as the surrounding set grows.^[ref]

For necessity, apply the defining inequality to $A\cup \{x\}$ and $B$. Conversely, enumerate $A\setminus B$ and compare adding its elements to $A\cap B$ with adding them to $B$. Summing the marginal inequalities gives $f(A)-f(A\cap B)\ge f(A\cup B)-f(B)$.

A coverage function is an example: $f(S)=|{\bigcup }_{v\in S}{C}_v|$ counts the covered objects in a finite universe. An added $C_x$ contributes only objects not already covered, so its gain decreases with $S$. Entropy submodularity is another fundamental example.

For a set function $F:2^{\{1,\dots ,n\}}\to \mathbb{R}$ with $F(\varnothing )=0$, sort the coordinates of $x\in {\mathbb{R}}^n$ as $x_{{\pi }_1}\ge \cdots \ge x_{{\pi }_n}$, and put $S_k=\{{\pi }_1,\dots ,{\pi }_k\}$. The Lovász extension isTies do not affect the result, because equal-coordinate terms telescope. At an indicator vector $1_S$ it gives $f(1_S)=F(S)$, so it extends a discrete objective to a piecewise linear function on a vector space.

For $F(S)=1$ when $S\ne \varnothing$ and zero otherwise, $f(x)={\max }_i{x}_i$. More generally, the extension is a convex function exactly when $F$ is a submodular set function. This equivalence is what makes the construction useful: a diminishing-returns condition on subsets becomes a geometric property on real vectors.^[ref]

A coverage function assigns a value to the union of objects covered by a selection. Let $V$ index sets $C_v$ in a finite universe $U$. The unweighted version isA weighted coverage function gives each $u\in U$ a nonnegative weight $w_u$ and sums those weights over the same set union. Its value is zero on the empty selection and cannot decrease when more sets are selected.^[ref]

The submodular set function property follows from an explicit marginal calculation:If $S\subseteq T$, the objects still uncovered after $T$ form a subset of those uncovered after $S$. Nonnegative weights therefore make the gain no larger after $T$: precisely the diminishing returns property.

For an original example, take $C_1=\{a,b\}$, $C_2=\{b,c\}$ and weights $(w_a,w_b,w_c)=(2,1,3)$. Then $F(\{1\})=3$, $F(\{2\})=4$ and $F(\{1,2\})=6$. The second set adds only three after the first, because their shared object $b$ is counted once. This models the value of distinct coverage, rather than the sum of overlapping collection sizes.

A weighted coverage function assigns nonnegative weights $w_u$ to members of a finite universe $U$, lets each choice $i$ cover a subset $A_i\subseteq U$, and values a selection $S$ byAn item covered twice is counted only once. If $A_1=\{a,b\}$, $A_2=\{b,c\}$ and the weights are $2,3,5$, then $f(\{1\})=5$, $f(\{2\})=8$ and $f(\{1,2\})=10$.

Its marginal gain of a set function is the total weight of newly covered items. As the selected set grows, fewer uncovered items remain, so the marginal gain of a set function can only decrease. This proves that a weighted coverage function is a monotone submodular set function. Nonnegative weights are essential to this argument. The construction models selecting sensors or experiments whose observations overlap.^[ref]

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.