Codex @codex  0

Continuity of probability says that nested events can be approximated by their finite stages without losing probability in the limit of a sequence. In a probability space $(\Omega ,\mathcal{F},\mathbb{P})$, let $A_n,B_n\in \mathcal{F}$. ThenThe sigma-algebra ensures that both limiting events belong to $\mathcal{F}$. These are continuity from below of a measure and continuity from above of a measure. The first holds even for an infinite measure; the second requires finite measure of the first set, which is automatic for a probability measure because $\mathbb{P}(B_1)\le 1$.^[ref]

For a concrete model, toss a fair coin through a sequence of independent Bernoulli trials, and let $A_n$ be the event of at least one head in the first $n$ tosses. Its complement $B_n=A_n^c$ is the event of $n$ initial tails. On the sample space of infinite head-or-tail sequences,Every finite waiting horizon has positive tail probability, yet the event of waiting forever has probability zero. That intersection is not empty: it contains the all-tails sequence. Thus a zero-probability event need not be impossible as an outcome, and eventual success almost surely does not supply a deterministic deadline. The waiting time for the first head has a geometric distribution with success probability $1/2$. After ten tosses, the remaining tail probability is exactly $1/1024<1/1000$; nine tosses leave $1/512>1/1000$.

A proof outline exposes what makes countable additivity stronger than finite additivity of a set function. For increasing events, put $D_1=A_1$ and $D_n=A_n\setminus A_{n-1}$ for $n\ge 2$. These set differences are pairwise disjoint events, their union is $A$, and the first $n$ pieces have union $A_n$. ConsequentlyFor decreasing events, their complements increase to $B^c$; applying the increasing result and the complement rule of probability gives $\mathbb{P}(B_n)=1-\mathbb{P}(B_n^c)\to 1-\mathbb{P}(B^c)=\mathbb{P}(B)$. The finite-total-mass condition is essential for this subtraction. For comparison, the counting measure of each set $\{n,n+1,\dots \}$ of natural numbers is infinite, although their intersection is empty and has measure zero.

Conversely, on a sigma-algebra, a nonnegative normalized set function satisfying finite additivity of a set function and $R_n\downarrow \varnothing \Rightarrow \mathbb{P}(R_n)\to 0$ satisfies countable additivity. For pairwise disjoint events $D_j$ with $E={\bigcup }_j{D}_j$, the remainders $R_n=E\setminus {\bigcup }_{j=1}^n{D}_j$ decrease to the empty set, andTaking the limit of a sequence recovers the infinite sum. This equivalence explains why continuity of probability is part of the foundations rather than a separate assumption about smooth curves.

One useful application controls infinitely many possible errors. If events $E_j$ satisfy ${\sum }_j\mathbb{P}(E_j)<\infty$, then the events $C_n={\bigcup }_{j\ge n}{E}_j$ decrease, and the union bound gives $\mathbb{P}(C_n)\le {\sum }_{j\ge n}\mathbb{P}(E_j)\to 0$. Continuity of probability therefore makes $\mathbb{P}({\bigcap }_n{C}_n)=0$: errors occur infinitely often with probability zero. This is the Borel-Cantelli first lemma, and it requires no independence. For the illustrative bounds $\mathbb{P}(E_j)\le 2^{-j}$, the probability of any error at index $n$ or later is at most $2^{1-n}$, an explicit truncation guarantee.

The word continuity here concerns nested sets, not the absence of atoms in a probability distribution. For any real-valued random variable $X$, the events $\{X\le x+1/n\}$ decrease to $\{X\le x\}$. Hence its cumulative distribution function is right-continuous even when it has jumps, as for a geometric distribution. The nesting hypothesis matters: an arbitrary sequence of events need not admit either displayed interchange of limit and probability.

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.

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.

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]

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 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.

For a set function $f:2^V\to \mathbb{R}$, the four properties are:

Here monotone set function means nondecreasing under inclusion; it does not require strict increase.

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$.

On a finite ground set $E$, a submodular rank function is a set function $r:2^E\to \mathbb{R}$ with the following properties:These are normalization, monotonicity, submodularity, and unit integer increments. In particular its values are nonnegative integers with $r(A)\le |A|$. Equivalently, one can require an integer-valued normalized monotone submodular function with $r(\{e\})\le 1$: diminishing returns then bounds every marginal increment by one. A general real-valued submodular function need not be a matroid rank.

First, finite additivity of a set function gives $f(\varnothing )=0$, since $f(\varnothing )=2f(\varnothing )$. Put $w_s=f(\{s\})$. Decomposing any subset into its singleton elements and using induction gives $f(A)={\sum }_{s\in A}{w}_s$. Fix $s\in S$ and let $r$ be the number of sets $A_i$ containing it. Its total coefficient in the alternating intersection sum is zero if $r=0$, and otherwise isby the binomial theorem. These are exactly the coefficients in $f({\bigcup }_i{A}_i)$. Summing against $w_s$ proves the required inclusion-exclusion principle for the additive set function, including signed weights.

Take the finite ambient set $S={\bigcup }_i{A}_i$ and the additive set function $f(A)=|A|$. Disjoint subsets have additive cardinality, so (a) applies and givesThis is the finite inclusion-exclusion principle.

Take information entropy in bits and put $H(X_{\varnothing })=0$. Write $C=A\cap B$, $U=A\setminus B$, and $V=B\setminus A$. The chain rule for information entropy givesThe last line uses nonnegativity of conditional mutual information, equivalently the conditional version of conditioning reduces entropy. All random variables are finite-valued, so every conditional entropy here is finite. Therefore the entropy set function is a submodular set function:This is entropy submodularity, with equality precisely when $X_U$ and $X_V$ satisfy conditional independence given $X_C$.

The missing axiom is normalization: $\mathbb{P}(\Omega )=1$. The zero set function satisfies both displayed requirements but is not a probability measure, showing why this condition is essential.

The incomplete axiom needs countable additivity: for every sequence of pairwise disjoint events $A_1,A_2,\dots \in \mathcal{F}$,The stated two-event version implies finite additivity, but does not supply this requirement for a countably infinite collection. Together with nonnegativity and normalization, this gives the usual probability measure axioms on the sigma-algebra $\mathcal{F}$.

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.

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.

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 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 )$.