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 on an algebra of sets is finitely additive if it has the displayed property for disjoint pairs. It follows that $F(\varnothing )=0$. On a finite ambient set, induction gives $F(A)={\sum }_{x\in A}F(\{x\})$, so arbitrary signed singleton weights describe all such functions. Summing the pointwise indicator function identity for the inclusion-exclusion principle against these weights proves the same formula for $F$.

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 is monotone, in the nondecreasing convention, when enlarging its input subset cannot decrease its value. Equivalently, each marginal increment ${\Delta }_{x}f(S)$ is nonnegative. This follows by adding elements individually; the converse follows by considering $S\subseteq S\cup \{x\}$. A normalised set function with this property is a nonnegative function.

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

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

A real-valued set function is supermodular if it satisfies the displayed inequality. Its negative is a submodular set function. Equivalently, the gain from adding an element cannot decrease as the set grows. This is the defining property of a convex cooperative game, and makes coalition 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 )$.