$\varphi(U_{n})+\varphi(W_{n})\leq\varphi(X_{n})+\varphi(Y_{n})\leq\varphi_{\bullet}(X)+\varphi_{\bullet}(Y)+2\varepsilon,$

and letting $n\to\infty$, we get that
$\varphi_{\bullet}(U_{n})+\varphi_{\bullet}(W_{n})\leq\varphi_{\bullet}(X)+\varphi_{\bullet}(Y)+2\varepsilon$.
Again, $\varepsilon$ is arbitrary, so the submodularity of $\varphi_{\bullet}$
follows.

The hardest part is to prove that $\varphi_{\bullet}$ is continuous from
below. We want to prove that for any sequence $X_{1}\subseteq
X_{2}\subseteq\ldots$ of sets on $\mathcal{B}$ with $\cup_{n}X_{n}=X$, we have

$\varphi_{\bullet}(X)\leq\lim_{n\to\infty}\varphi_{\bullet}(X_{n}).$ (43)

Let $\varepsilon>0$ and $\varepsilon_{n}=\varepsilon/3^{n}$. By the definition
of $\varphi_{\bullet}$, for every $n$ there is a sequence $X_{n,1}\subseteq
X_{n,2}\subseteq\ldots$ of sets in $\mathcal{B}$ such that
$\cup_{i}X_{n,i}=X_{n}$ and
$\varphi(X_{n,i})\leq\varphi_{\bullet}(X_{n})+\varepsilon_{n}$.

Define $Y_{n,i}=X_{1,i}\cup\ldots\cup X_{n,i}$ and $Z_{n,i}=Y_{n,i}\cap
X_{n+1,i}$. Clearly $Y_{n,i+1}\supseteq Y_{n,i}$ and $Z_{n,i+1}\supseteq
Z_{n,i}$. Furthermore,

$\bigcup_{i}Y_{n,i}=X_{n}.$ (44)

Indeed, $Y_{n,i}\subseteq X_{1}\cup\ldots\cup X_{n}=X_{n}$, but
$\cup_{i}Y_{n,i}\supseteq\cup_{i}X_{n,i}=X_{n}$. Hence

$\bigcup_{i}Z_{n,i}=X_{n},$ (45)

since every $x\in X_{n}$ is contained in $Y_{n,i}$ as well as in $X_{n+1,i}$
if $i$ is large enough. By the definition of $\varphi_{\bullet}$, it follows
that

$\varphi(Z_{n,i})\geq\varphi_{\bullet}(X_{n})-\varepsilon_{n}$ (46)

if $i$ is large enough, say $i\geq f(n)$. We may assume that $f(n)$ is a
strictly increasing function.

We prove by induction on $n$ that if $i\geq f(n)$, then

$\varphi(Y_{n,i})\leq\varphi_{\bullet}(X_{n})+\varepsilon-2\varepsilon_{n}.$
(47)

For $n=1$, we have
$\varphi(Y_{1,i})=\varphi(X_{1,i})\leq\varphi_{\bullet}(X_{1})+\varepsilon_{1}=\varphi_{\bullet}(X_{1})+\varepsilon-2\varepsilon_{1}$.
For the induction step, we use submodularity. For $i\geq f(n+1)$, we have

$\displaystyle\varphi(Y_{n+1,i})$ $\displaystyle=\varphi(Y_{n,i}\cup
X_{n+1,i})\leq\varphi(Y_{n,i})+\varphi(X_{n+1,i})-\varphi(Z_{n,i})$
$\displaystyle\leq(\varphi_{\bullet}(X_{n})+\varepsilon-2\varepsilon_{n})+(\varphi_{\bullet}(X_{n+1})+\varepsilon_{n+1})-(\varphi_{\bullet}(X_{n})-\varepsilon_{n})$
$\displaystyle=\varphi_{\bullet}(X_{n+1})+\varepsilon-\varepsilon_{n}+\varepsilon_{n+1}=\varphi_{\bullet}(X_{n+1})+\varepsilon-2\varepsilon_{n+1}.$

This proves (47).

Consider that sequence of sets $(Y_{n,f(n)}:~{}n=1,2,\ldots)$. Clearly it is
increasing. We claim that

$\bigcup_{n}Y_{n,f(n)}=X.$ (48)

Indeed, $Y_{n,f(n)}\subseteq X$, so the $\subseteq$ containment is trivial. To
prove equality, let $x\in X$. Then $x\in X_{k}$ for some $k$, and hence $x\in
X_{k,i}$ for some $i$. Let $n$ be large enough such that $i\leq f(n)$, then
$X_{k,i}\subseteq X_{k,f(n)}\subseteq Y_{n,f(n)}$, so $x\in Y_{n,f(n)}$.

To conclude, note that (48) and (47) imply that

$\varphi_{\bullet}(X)\leq\lim_{n\to\infty}\varphi_{\bullet}(Y_{n,f(n)})\leq\lim_{n\to\infty}\varphi_{\bullet}(X_{n})+\varepsilon-2\varepsilon_{n}=\lim_{n\to\infty}\varphi_{\bullet}(X_{n})+\varepsilon.$

This holds for every $\varepsilon>0$, proving (43).

We supplement this lemma with a weaker statement about the difference.

######  Lemma 6.5.

Let $\varphi$ be an increasing submodular setfunction. Then the difference
$\varphi-\varphi_{\bullet}$ is subadditive.

###### Proof.

Let $\varepsilon>0$, $X,Y\in\mathcal{B}$, and let $Z_{1}\subseteq
Z_{2}\ldots\in\mathcal{B}$ be a chain of sets such that $\cup_{n}Z_{n}=X\cup
Y$ and $\varphi(Z_{n})\leq\varphi_{\bullet}(X\cup Y)+\varepsilon$. Let
$U_{n}=X\cap Z_{n}$, $V_{n}=X\cup Z_{n}$, and $W_{n}=Y\cap V_{n}$. Then
$\cup_{n}U_{n}=X$, $\cup_{n}W_{n}=Y$, and $V_{n}\cup Y=X\cup Y$. By
submodularity,

$\varphi(X)+\varphi(Z_{n})\geq\varphi(V_{n})+\varphi(U_{n}),$

and

$\varphi(Y)+\varphi(V_{n})\geq\varphi(Y\cup
V_{n})+\varphi(W_{n})=\varphi(X\cup Y)+\varphi(W_{n}).$

Adding up these inequalities, canceling what we can, and rearranging, we
obtain

$\varphi(X)-\varphi(U_{n})+\varphi(Y)-\varphi(W_{n})\geq\varphi(X\cup
Y)-\varphi(Z_{n})\geq\varphi(X\cup Y)-\varphi_{\bullet}(X\cup Y)-\varepsilon.$

By definition,

$\varphi(X)-\lim_{n}\varphi(U_{n})\leq\varphi(X)-\varphi_{\bullet}(X)\qquad\text{and}\qquad\varphi(Y)-\lim_{n}\varphi(W_{n})\leq\varphi(Y)-\varphi_{\bullet}(Y),$

so letting $n\to\infty$ and $\varepsilon\to 0$, we get

$\varphi(X)-\varphi_{\bullet}(X)+\varphi(Y)-\varphi_{\bullet}(Y)\geq\varphi(X\cup
Y)-\varphi_{\bullet}(X\cup Y),$

proving the lemma.

Let $\varphi$ be an increasing submodular setfunction. If $\psi\leq\varphi$ is
another increasing setfunction, then clearly
$\psi_{\bullet}\leq\varphi_{\bullet}$. If, in particular, $\psi$ is continuous
from below, then $\psi\leq\varphi_{\bullet}$. So by lemma 6.4,
$\varphi_{\bullet}$ is the unique largest increasing setfunction minorizing
$\varphi$ that is continuous from below, and it is also submodular.

###  6.2 Absolute continuity

Let $\pi$ be a measure on a sigma-algebra $(J,\mathcal{B})$. We say that a
setfunction $\varphi$ is absolutely continuous with respect to $\pi$, if for
every $\varepsilon>0$ there is a $\delta>0$ such that $\pi(S)<\delta$ implies
that $|\varphi(S)|<\varepsilon$ for every $S\in\mathcal{B}$. Let us say that
$\varphi$ is weakly absolutely continuous with respect to $\pi$ if
$\varphi(S)=0$ for all $S\in\mathcal{B}$ with $\pi(S)=0$. Absolute continuity
implies weak absolute continuity but (unlike in the case of countably additive
measures), it is not equivalent to it. But we have the following fact.

######  Lemma 6.6.

An increasing submodular setfunction $\varphi$ on a sigma-algebra
$(J,\mathcal{B})$ with $\varphi(\emptyset)=0$ is absolutely continuous with
respect to a measure $\pi$ if and only if it is continuous from above and
weakly absolutely continuous with respect to $\pi$.

###### Proof.

First, suppose that $\varphi$ is absolutely continuous with respect to a
countably additive measure $\pi$. Weak absolute continuity with respect to
$\pi$ is trivial. To prove that $\varphi$ is continuous from above, let
$A_{i}\in\mathcal{B}$, $A_{1}\supseteq A_{2}\supseteq\ldots$, and
$\cap_{i}A_{i}=\emptyset$. Given $\varepsilon>0$, there is a $\delta>0$ such
that $|\varphi(S)|<\varepsilon$ for every $S\in\mathcal{B}$ with
$\pi(S)<\delta$. Then $\pi(A_{n})\to 0$ (since $\pi$ is countably additive),
so $\pi(A_{n})<\delta$ if $n$ is large enough. Hence
$\varphi(A_{n})<\varepsilon$ for every $n$ that is large enough.

Second, suppose that $\varphi$ is continuous from above and weakly absolutely
continuous with respect to $\pi$, and assume, by way of contradiction, that
$\varphi$ is not absolutely continuous with respect to $\pi$. Then there is a
sequence of sets $A_{n}\in\mathcal{B}$ such that $\pi(A_{n})\to 0$ but
$\varphi(A_{n})>c$ for some $c>0$. We may assume that $\pi(A_{n})<2^{-n}$. Let
$B_{n}=\cup_{m\geq n}A_{m}$, then $\pi(B_{n})<2^{1-n}$ and $\varphi(B_{n})>c$.
Then $\pi(\cap_{n}B_{n})=0$ (since $\pi$ is countably additive) but
$\varphi(\cap_{n}B_{n})>c$ (since $\varphi$ is continuous from above). This
contradicts the weak absolute continuity of $\varphi$.

###  6.3 Continuity of the Choquet extension

Lemma 2.7 implies that if $\varphi$ is any setfunction with bounded variation,
$g,f_{n}\in{\sf Bd}$ and $f_{n}\to g$ uniformly, then
$\widehat{\varphi}(f_{n})\to\widehat{\varphi}(g)$. Under submodularity
conditions on $\varphi$, we can relax the uniform convergence condition.
(Under smoothness conditions for $\varphi$, we get further improvements.)

Let $f_{n}$ $(n=1,2,\ldots)$ and $g$ be measurable functions $J\to[0,1]$. We
say that $f_{n}\to g$ in $\varphi$-measure, if
$\varphi\\{x:~{}|f_{n}(x)-g(x)|>\varepsilon\\}\to 0$ as $n\to\infty$ for every
$\varepsilon>0$. We say that $f_{n}\to g$ $\varphi$-almost everywhere, if
$\varphi\\{x:~{}f_{n}(x)\not\to g(x)\\}=0$.

######  Lemma 6.7.

Let $\varphi$ be an increasing submodular setfunction on $\mathcal{B}$ with
$\varphi(\emptyset)=0$, let $f_{n},g\in{\sf Bd}$ with $\|f_{n}\|,\|g\|\leq 1$,
and let $f_{n}\to g$ in $\varphi$-measure. Then
$\widehat{\varphi}(f_{n})\to\widehat{\varphi}(g)$ $(n\to\infty)$.

###### Proof.

Let $h_{n}=|f_{n}-g|$, then $0\leq h_{n}\leq 2$, and $f_{n}\leq g+h_{n}$.
Hence by Theorem 4.8, we have
$\widehat{\varphi}(f_{n})\leq\widehat{\varphi}(g+h_{n})\leq\widehat{\varphi}(g)+\widehat{\varphi}(h_{n})$.
Let $\varepsilon>0$, then

$\displaystyle\widehat{\varphi}(h_{n})$
$\displaystyle=\int\limits_{0}^{2}\varphi\\{h_{n}\geq
t\\}\,dt\leq\int\limits_{0}^{\varepsilon}\varphi\\{h_{n}\geq
t\\}\,dt+\int\limits_{\varepsilon}^{2}\varphi\\{h_{n}\geq t\\}\,dt$
$\displaystyle\leq\varepsilon\|\varphi\|+2\varphi\\{h_{n}\geq\varepsilon\\}.$

The last term is less than $\varepsilon$ if $n$ is sufficiently large, so
$\widehat{\varphi}(h_{n})\leq 3\varepsilon$ and
$\widehat{\varphi}(f_{n})\leq\widehat{\varphi}(g)+3\varepsilon$. The reverse
inequality follows similarly.

######  Lemma 6.8.

Let $\varphi$ be an increasing submodular setfunction on $\mathcal{B}$
continuous from above with $\varphi(\emptyset)=0$. Let $f_{n},g\in{\sf Bd}$
with $\|f_{n}\|,\|g\|\leq 1$, and assume that $f_{n}\to g$ $\varphi$-almost
everywhere. Then $\widehat{\varphi}(f_{n})\to\widehat{\varphi}(g)$
$(n\to\infty)$.

###### Proof.

By Lemma 6.7, it suffices to prove that $f_{n}\to g$ in $\varphi$-measure. Let
$Z=\\{x\in J:~{}f_{n}(x)\not\to g(x)\\}$ and $\varepsilon>0$. Define
$X_{n,\varepsilon}=\\{|f_{n}-g|>\varepsilon\\}$ and
$Y_{n,\varepsilon}=\cup_{m\geq n}X_{m,\varepsilon}$. We claim that
$\cap_{n}Y_{n,\varepsilon}=Z$. Indeed, if $x\in\cap_{n}Y_{n,\varepsilon}$,
then there are infinitely many indices $m$ such that $x\in X_{m,\varepsilon}$,
so $|f_{m}(x)-g(x)|>\varepsilon$ for infinitely many indices $m$, and hence
$f_{m}(x)\not\to g(x)$.

By continuity from above, this implies that
$\varphi(Y_{n,\varepsilon})\to\varphi(Z)=0$ as $n\to\infty$. Since
$X_{n,\varepsilon}\subseteq Y_{n,\varepsilon}$, the monotonicity of $\varphi$
implies that $\varphi(X_{n})\to 0$, and so $f_{n}\to g$ in $\varphi$-measure.

###  6.4 Majorizing measures and strong boundedness

Let $\varphi$ be an increasing subadditive setfunction on a sigma-algebra
$(J,\mathcal{B})$ with $\varphi(\emptyset)=0$. We define
${\varphi}^{\sqcap}:~{}\mathcal{B}\to\mathbb{R}\cup\\{\infty\\}$ by

${\varphi}^{\sqcap}(X)=\sup\sum_{i=1}^{n}\varphi(X_{i}),$ (49)

where $\\{X_{1},\ldots,X_{n}\\}$ ranges over all partitions of $X$ into sets
in $\mathcal{B}$. Clearly ${\varphi}^{\sqcap}$ is increasing (but it may take
infinite values). Let us also note that in the definition of
${\varphi}^{\sqcap}$, we could allow countable partitions. Indeed, for any
countable partition $X=\cup_{i=1}^{\infty}X_{i}$, we have

${\varphi}^{\sqcap}(X)\geq{\varphi}^{\sqcap}(X_{1}\cup\ldots\cup
X_{n})\geq\sum_{i=1}^{n}\varphi(X_{i}),$

and letting $n\to\infty$, we get

${\varphi}^{\sqcap}(X)\geq\sum_{i=1}^{\infty}\varphi(X_{i}).$

This means that including countable partitions does not increase the supremum
in (49).

######  Lemma 6.9.

The setfunction ${\varphi}^{\sqcap}$ is additive. If $\varphi$ is continuous
from below, then ${\varphi}^{\sqcap}$ is countably additive.

###### Proof.

We prove the second assertion. The proof of the first one is almost the same,
except that continuity from below is not needed because of the finiteness of
the partition.

Let $X=\cup_{i=1}^{\infty}X_{i}$ be a partition of $X$
($X,X_{i}\in\mathcal{B}$). Let $\varepsilon>0$, and let
$X_{i}=\cup_{j=1}^{\infty}X_{i,j}$ partition of $X_{i}$ such that
$X_{i,j}\in\mathcal{B}$) and

${\varphi}^{\sqcap}(X_{i})\leq\sum_{j=1}^{\infty}\varphi(X_{i,j})+\frac{\varepsilon}{2^{i}}.$

Then $\\{X_{i,j}:~{}i,j\in\mathbb{N}\\}$ is a partition of $X$ into sets in
$\mathcal{B}$, and hence

${\varphi}^{\sqcap}(X)\geq\sum_{i,j}\varphi(X_{i,j})\geq\sum_{i}\Big{(}{\varphi}^{\sqcap}(X_{i})-\frac{\varepsilon}{2^{i}}\Big{)}=\sum_{i}{\varphi}^{\sqcap}(X_{i})-\varepsilon.$
(50)

To show the reverse inequality, let $\varepsilon>0$, and let
$X=Z_{1}\cup\ldots\mathbb{Z}_{n}$ be a measurable partition of $X$ such that

${\varphi}^{\sqcap}(X)\leq\sum_{i=1}^{n}\varphi(Z_{i})+\varepsilon.$

Continuity from below implies, by (41), that

$\varphi(Z_{i})\leq\sum_{j=1}^{\infty}\varphi(Z_{i}\cap X_{j}).$ (51)

Hence

${\varphi}^{\sqcap}(X)\leq\sum_{i=1}^{n}\varphi(Z_{i})+\varepsilon=\sum_{i=1}^{n}\sum_{j=1}^{\infty}\varphi(Z_{i}\cap
X_{j})+\varepsilon\leq\sum_{i}{\varphi}^{\sqcap}(X_{i})+\varepsilon.$ (52)

Since $\varepsilon>0$ was arbitrary, (50) and (52) prove the countable
additivity of ${\varphi}^{\sqcap}$.

The previous considerations are most relevant when ${\varphi}^{\sqcap}$ is
finite. We call such a setfunction $\varphi$ strongly bounded. This means that
there is a $C\in\mathbb{R}$ such that $\sum_{i}|\varphi(A_{i})|\leq C$ for
every family of disjoint sets $A_{1},\ldots,A_{n}\in\mathcal{B}$. It is clear
that every nonnegative charge has this property. The following lemma
establishes a certain converse.

######  Lemma 6.10.

A nonnegative bounded subadditive setfunction $\varphi$ with
$\varphi(\emptyset)=0$ is strongly bounded if and only if there is a charge
$\alpha\in{\sf ba}_{+}(\mathcal{B})$ such that $\varphi\leq\alpha$.

###### Proof.

The necessity of the condition follows by Lemma 6.9, considering
$\alpha={\varphi}^{\sqcap}$. Sufficiency follows by the following computation:
For for every family of disjoint sets $A_{1},\ldots,A_{n}\in\mathcal{B}$, we
have

$\sum_{i=1}^{n}\varphi(A_{i})\leq\sum_{i=1}^{n}\alpha(A_{i})=\alpha\big{(}\bigcup_{i}A_{i}\big{)}\leq\alpha(J).$

If a nonnegative submodular setfunction $\varphi$ is continuous from below and
strongly bounded, then it bounded from above by a (finite) countably additive
measure $\mu$; this implies that $\varphi$ is also continuous from above. It
also follows that $\varphi$ is absolutely continuous with respect to the
measure ${\varphi}^{\sqcap}$.

##  7 Applications of smoothness properties

In this section we show how previous results can be improved or applied under
smoothness conditions.

###  7.1 Countably additive minorizing measures

In Theorem 5.5 and its corollaries, we have constructed minorizing charges. We
can do better for setfunctions continuous from above, for which minorizing
measures are automatically countably additive:

######  Lemma 7.1.

Let $\varphi$ be a nonnegative setfunction with $\varphi(\emptyset)=0$
continuous from above, and let $\alpha\in{\sf mm}_{+}(\varphi)$. Then $\alpha$
is countably additive.

###### Proof.

Let $B_{i}\in\mathcal{B}$ ($i=1,2,\ldots$) be disjoint sets, and define
$A_{n}=\cup_{i\geq n}B_{i}$. Then by the finite additivity of $\alpha$,

$\alpha(A_{1})=\sum_{i=1}^{n-1}\alpha(B_{i})+\alpha(A_{n}).$

Since $\cap_{n}A_{n}=\emptyset$, continuity of $\varphi$ from above implies
that $\varphi(A_{n})\to 0$ as $n\to\infty$. Since $\alpha\leq\varphi$, it
follows that $\alpha(A_{n})\to 0$. So letting $n\to\infty$, we get that
$\alpha(A_{1})=\sum_{i=1}^{\infty}\alpha(B_{i})$.

######  Corollary 7.2.

Let $\varphi$ be an increasing submodular setfunction continuous from above.
Let $\SS\subseteq\mathcal{B}$ be a chain of sets. Then there is a countably
additive measure $0\leq\alpha\leq\varphi$ on $\mathcal{B}$ such that
$\alpha(S)=\varphi(S)$ for $S\in\SS$. If $\SS$ generates $\mathcal{B}$ as a
sigma-algebra, then $\alpha$ is uniquely determined.

The natural full chain $\\{[0,a):~{}0<a\leq 1\\}\cup\\{[0,a]:~{}0\leq a\leq
1\\}$ of Borel subsets of $[0,1]$ is an example when the last conclusion
applies.

###### Proof.

The charge $\alpha$ constructed in Theorem 5.5 is countably additive by Lemma
7.1. To prove uniqueness of $\alpha$ it suffices to note that $\SS$ is a set-
algebra that generates the Borel sets as a sigma-algebra, and the restriction
of $\varphi$ to $\SS$ is a finite countably additive measure, so its extension
to all Borel sets is unique by Caratheodory’s Theorem.

###  7.2 Lopsided Fubini Theorem

Assuming continuity of $\varphi$, we can prove the following generalization of
Theorem 4.8. The continuity condition cannot be omitted, even if $\varphi$ is
a charge, as shown by Example 11.5 in the Appendix.

######  Theorem 7.3.

Let $(I,\mathcal{A},\lambda)$ and $(J,\mathcal{B},\pi)$ be probability spaces.
Let $\varphi$ be an increasing submodular setfunction on $(J,\mathcal{B})$
absolutely continuous with respect to $\pi$, and let $F:~{}J\times
I\to\mathbb{R}$ be a bounded measurable function. Define $F_{y}(x)=F(x,y)$ and
$g(x)=\int_{I}F(x,y)\,d\lambda(y)$. Then

$\widehat{\varphi}(g)\leq\int\limits_{I}\widehat{\varphi}(F_{y})\,d\lambda(y).$
(53)

Using the integral notation, we can write this inequality as

$\int\limits_{J}\int\limits_{I}F(x,y)\,d\lambda(y)\,d\varphi(x)\leq\int\limits_{I}\int\limits_{J}F(x,y)\,d\varphi(x)\,d\lambda(y).$

So inequality (53) is a “lopsided” version of Fubini’s Theorem.

###### Proof.

We may assume that $0\leq F\leq 1$. Let $\mathcal{X}$ be the set of pairs
$(x,\mathbf{y})$ such that $x\in J$, $\mathbf{y}=(y_{1},y_{2},\ldots)\in
I^{\mathbb{N}}$, and

$\frac{1}{n}\sum_{i=1}^{n}F_{y_{i}}(x)\to g(x).$ (54)

For every $x\in J$, this happens to $\lambda^{\mathbb{N}}$-almost all
sequences $\mathbf{y}$. By Fubini’s Theorem, for almost all sequences
$\mathbf{y}$, (54) holds for $\pi$-almost all $x\in J$.

Let $\mathbf{y}=(y_{1},y_{2},\ldots)$ be an infinite sequence of independent
uniform random points in $I$ from the distribution $\lambda$, and let

$f_{n}=\frac{1}{n}\sum_{i=1}^{n}F_{y_{i}}.$

Then

$\widehat{\varphi}(f_{n})\leq\frac{1}{n}\sum_{i=1}^{n}\widehat{\varphi}(F_{y_{i}})$
(55)

by Theorem 4.8. By the Law of Large Numbers,

$\frac{1}{n}\sum_{i=1}^{n}\widehat{\varphi}(F_{y_{i}})\to\int\limits_{I}\widehat{\varphi}(F_{y})\,d\lambda(y)\qquad(n\to\infty)$
(56)

almost surely. So we have

$\limsup_{n\to\infty}\widehat{\varphi}(f_{n})\leq\int\limits_{I}\widehat{\varphi}(F_{y})\,d\lambda(y)$
(57)

for almost all $\mathbf{y}$. In addition, we have (54) for almost all pairs
$(x,\mathbf{y})$. So we can fix a sequence $\mathbf{y}$ for which $f_{n}\to g$
$\pi$-almost everywhere, and (57) holds. Since $\varphi$ is absolutely
continuous with respect to $\pi$, it follows that $f_{n}\to g$
$\varphi$-almost everywhere. By Lemma 6.6 the setfunction $\varphi$ is
continuous from above, and so Lemma 6.8 implies that
$\widehat{\varphi}(f_{n})\to\widehat{\varphi}(g)$ as $n\to\infty$. Combined
with (57), this proves the theorem.

###  7.3 Matchings and coupling measures

An important area of applications of matroids to graph theory is matching
theory. Let $(J_{i},\mathcal{B}_{i},\pi_{i})$ be probability spaces, and let
$E\in\mathcal{B}_{1}\times\mathcal{B}_{2}$ be a set. We can think of
$(J_{1},J_{2},E)$ as a bigraph $G$ with bipartition $J_{1}\cup J_{2}$ and edge
set $E$. Recall that for $X\in\mathcal{B}_{1}$, we denote by $E(X)\subseteq
J_{2}$ the set of neighbors of $X$ in $G$. We would like to find a measure
$\alpha$ on $\mathcal{A}=2^{E}\cap(\mathcal{B}_{1}\times\mathcal{B}_{2})$
whose marginals are $\pi_{1}$ and $\pi_{2}$.

If $J_{1}$ and $J_{2}$ are finite, $|J_{1}|=|J_{2}|$, and $\pi_{1},\pi_{2}$
are uniform distributions, then this just the Fractional Perfect Matching
Problem. In the general case, let $(J,\mathcal{B},\pi)$ be a probability
space. A nonnegative measure on $\mathcal{B}^{2}$ with marginals $\pi$ will be
called a coupling measure. (If $J=[0,1]$ and $\pi$ is the Lebesgue measure,
then it is also called a doubly stochastic measure, or a permuton; the last
name refers to the fact that these measures represent limits of permutations
of finite sets; see [26, 20].)

We are interested in coupling measures (both countably and finitely additive
ones) supported on a given set. The necessary condition generalizes the
condition in the Frobenius–Kőnig Theorem.

######  Theorem 7.4.

(a) A finitely additive coupling measure supported on
$E\in\mathcal{B}\times\mathcal{B}$ exists if and only if
$\lambda(X)\leq\lambda(E(X))$ for every $X\in\mathcal{B}$.

(b) If, in addition, $(J,\mathcal{B})$ is the sigma-algebra of Borel sets of a
compact Hausdorff space, and $E$ is closed, then even a countably additive
coupling measure supported on $E$ exists.

Before the proof, some remarks. The set $E(X)$ is not necessarily Borel, but
(as remarked in Example 3.5), it is Lebesgue measurable, and so
$\lambda(E(X))$ is well-defined. Part (b) of the Theorem is well known: it
follows by a theorem of Strassen [56]. It is also a rather straightforward
generalization of Theorem 2.5.2 in [42]. Part (a) is closely related to recent
work of Rigo [52]. We give a proof of (a) as an application of the Submodular
Intersection Theorem 5.15, and derive (b) from (a).

Part (b) remains valid under the weaker hypothesis that $[0,1]^{2}\setminus E$
is the union of a countable number of product sets $A_{i}\times B_{i}$
$(A_{i},B_{i}\in\mathcal{B})$ (Proposition 3.8 of Kellerer [32]).

Proof of Theorem 7.4. The necessity of the condition is easy. Let $\alpha$ be
a coupling measure supported on $E$. For every $X\in\mathcal{B}$, the set
$X\times(J\setminus E(X))$ is disjoint from $E$, and hence
$\alpha(X\times(J\setminus E(X)))=0$. Hence

$\lambda(X)=\alpha(X\times J)=\alpha(X\times E(X))\leq\alpha(J\times
E(X))=\lambda(E(X)).$

To prove the “if” part of (a), consider two setfunctions on $\mathcal{A}$: for
$U\in\mathcal{A}$, let $\Pi_{i}(U)$ denote its projection onto the $i$-th
coordinate, and define $\varphi_{i}(U)=\lambda(\Pi_{i}(U))$ ($i=1,2$). The
setfunctions $\varphi_{i}$ are both increasing and submodular, as shown in
Example 3.5. Furthermore, for any $U\in\mathcal{A}$,

$\varphi_{1}(U)+\varphi_{2}(E\setminus
U)=\lambda(\Pi_{1}(U))+\lambda(\Pi_{2}(E\setminus U)).$

Let $X=[0,1]\setminus\Pi_{1}(U)$, then by for any $x\in X$ and $(x,y)\in E$ we
have $(x,y)\notin U$, and hence $y\in\Pi_{2}(E\setminus U)$. So
$E(X)\subseteq\Pi_{2}(E\setminus U)$, and hence by the hypothesis in (a),

$\lambda(\Pi_{2}(E\setminus
U))\geq\lambda(E(X))\geq\lambda(X)=1-\lambda(\Pi_{1}(U)).$

In other words, $\varphi_{1}(U)+\varphi_{2}(E\setminus U)\geq 1$. Taking the
infimum on the left, we get that

$(\varphi_{1}\land\varphi_{2})(E)\geq 1.$

So by Theorem 5.15, there is a charge $\alpha\in{\sf
mm}_{+}(\varphi_{1})\cap{\sf mm}(\varphi_{2})$ such that $\alpha(E)=1$. The
measure $\alpha$ is defined on Borel subsets of $E$, but we can extend it to
all sets $X\in\mathcal{B}\times\mathcal{B}$ by setting $\alpha(X)=\alpha(X\cap
E)$.

By construction, $\alpha$ is supported on $E$. To show that $\alpha$ is a
coupling measure, let $X\in\mathcal{B}$. Then $\alpha(X\times
J)\leq\varphi_{1}(X\times J)=\lambda(X)$, and similarly $\alpha(X^{c}\times
J)\leq\lambda(X^{c})$. But $1=\alpha(J\times J)=\alpha(X\times
J)+\alpha(X^{c}\times J)\leq\lambda(X)+\lambda(X^{c})=\lambda(J)=1$, which
proves that the first marginal of $\alpha$ is $\lambda$. The same conclusion
follows for the second marginal similarly.

To prove the “if” part of (b), consider a charge $\alpha$ constructed above,
and let $\overline{\alpha}$ be the countably additive measure constructed in
Proposition 11.3. Let $f(x)$ denote the distance of $x\in I\times I$ from $E$,
then $f$ is continuous and positive on $E^{c}$. Hence

$\int\limits_{E^{c}}f\,d\overline{\alpha}=\int\limits_{E^{c}}f\,d\alpha=0,$

which implies that $\overline{\alpha}$ is supported on $E$. $\square$

######  Remark 7.5.

The Birkhoff–von Neumann Theorem asserts that in the finite case, the extremal
points of the set of coupling measures are just the perfect matchings. The
question of determining these extremal points in the infinite case (at least
in the Borel case) is open. Complicated extremal points exist (see e.g. Losert
[36]), and an interesting characterization was given by Lindenstrauss [34],
but no direct generalization of the Birkhoff–von Neumann Theorem seems to be
known.

##  8 Björner distance and flats of submodular setfunctions

The results in Section 5.3 represent an attempt to generalize the notions of
independent sets and bases from matroids to submodular setfunctions based on
charges. Here we generalize the notion of flats (closed subsets) of matroid
theory, using a simple but very useful distance of subsets defined by an
increasing submodular setfunction.

###  8.1 Definition

The following definition is motivated by a construction of Björner [4, 5]. Let
$\varphi$ be a increasing submodular setfunction on a set-algebra
$(J,\mathcal{B})$. For two sets $X,Y\in\mathcal{B}$, we define their Björner
distance by

$d(X,Y)=d_{\varphi}(X,Y)=2\varphi(X\cup Y)-\varphi(X)-\varphi(Y).$ (58)

In particular,

$d(X,Y)=\varphi(Y)-\varphi(X)\quad\text{if}\quad X\subseteq Y.$ (59)

Hence for any $X,Y\in\mathcal{B}$, we have

$d(X,Y)=d(X,X\cup Y)+d(Y,X\cup Y).$ (60)

If $\varphi$ is a measure, then $d(X,Y)=\varphi(X\triangle Y)$ is the
$L^{1}$-distance of ${\mathbbm{1}}_{X}$ and ${\mathbbm{1}}_{Y}$. The metric
$d_{\varphi}$ does not change if a constant is added to $\varphi$. So we may
assume that $\varphi(\emptyset)=0$, and we will do so in the rest of this
section. It follows that $\varphi(X)=d(X,\emptyset)$.

######  Lemma 8.1.

The function $d$ is a pseudometric. If $\varphi$ is strictly increasing, then
$d$ is a metric.

###### Proof.

Nonnegativity of $d$ is implied by the monotonicity of $\varphi$. The
equations $d(X,X)=0$ and $d(X,Y)=d(Y,X)$ are trivial. The triangle inequality
follows by an easy computation:

$\displaystyle d(X,Y)$ $\displaystyle+d(Y,Z)-d(X,Z)=2\varphi(X\cup
Y)-\varphi(X)-\varphi(Y)$ $\displaystyle+2\varphi(Y\cup
Z)-\varphi(Y)-\varphi(Z)-(2\varphi(X\cup Z)-\varphi(X)-\varphi(Z))$
$\displaystyle=2\varphi(X\cup Y)+2\varphi(Y\cup Z)-2\varphi(X\cup
Z)-2\varphi(Y).$

Here $X\cup Z\subseteq(X\cup Y)\cup(Y\cup Z)$ and $Y\subseteq(X\cup
Y)\cap(Y\cup Z)$, and so

$\displaystyle d(X,Y)$ $\displaystyle+d(Y,Z)-d(X,Z)\geq 2\varphi(X\cup
Y)+2\varphi(Y\cup Z)$ $\displaystyle-2\varphi((X\cup Y)\cup(Y\cup
Z))-2\varphi((X\cup Y)\cap(Y\cup Z))\geq 0$

by submodularity. The second assertion follows trivially from the first.

It is straightforward to check that if $\varphi$ and $\psi$ are increasing
submodular setfunctions, then $d_{\psi}\leq d_{\varphi}$ if and only if the
pair $(\varphi,\psi)$ is diverging. Since the pair $(\varphi,\varphi(A\cup.))$
is diverging for any $A\in\mathcal{B}$, it follows that the map $X\mapsto
X\cup A$ is contractive:

$\displaystyle d(X\cup A,Y\cup A)\leq d(X,Y).$ (61)

######  Remark 8.2.

The Björner distance is a weighted graph distance, where the underlying graph
is the (undirected) comparability graph of sets in $\mathcal{B}$, and the
weight of an edge $(X,Y)$ is $|\varphi(X)-\varphi(Y)|$. This can be proved
similarly as Lemma 3.18.

###  8.2 Roofs and flats

For the rest of this section, let us assume that $(J,\mathcal{B})$ is a sigma-
algebra and $\varphi$, an increasing submodular setfunction on $\mathcal{B}$.
The distance function $d_{\varphi}$ is not a metric in general, because two
different sets can have distance $0$. Two sets $X,Y\in\mathcal{B}$ have
$d(X,Y)=0$ if and only if $\varphi(X)=\varphi(Y)=\varphi(X\cup Y)$. If
$X\subseteq Y$, then this condition simplifies to $\varphi(X)=\varphi(Y)$. The
condition $d(X,Y)=0$ defines an equivalence relation, which we denote by
$X\equiv_{\varphi}Y$, or simply by $X\equiv Y$. The classes of this
equivalence relation will be called roofs. Contracting the equivalence classes
to single elements, we get a metric space.

If $\varphi=\lambda$ is the Lebesgue measure, then this equivalence is the
standard identification of sets $X$ and $Y$ if $\lambda(X\triangle Y)=0$. In
the case of a matroid $(E,r)$, two sets are equivalent if and only if they
span the same flat, and the roof corresponding to this flat consists of all
sets spanning this flat. The flat consists of all elements of $E$ whose
equivalence class is under this roof.

It is clear that for every roof $\mathcal{R}$, all sets $X\in\mathcal{R}$ have
the same $\varphi(X)$, which we can denote by $\varphi(\mathcal{R})$. It is
also clear that every roof is closed under (finite) union. In the finite case
of matroids, every roof contains a unique largest set, and it is closed under
all unions. This does not remain true in the infinite case, even for countable
unions and under smoothness conditions. If $\varphi$ is the Lebesgue measure
on $[0,1]$, then all null-sets among Borel sets form a roof, but there is no
largest null-set. For the setfunction ${\mathbbm{1}}(X~{}\text{is infinite})$
(cf. Example 3.3) there are two roofs (finite sets and infinite sets), but
finite sets are not closed under countable union. However, the following
smoothness condition helps:

######  Lemma 8.3.

If $\varphi$ is an increasing submodular setfunction continuous from below,
then every roof $\mathcal{R}$ is closed under countable union.

###### Proof.

Let $X_{1},X_{2},\ldots\in\mathcal{R}$ and $X=X_{1}\cup X_{2}\cup\ldots$.
Since $\mathcal{R}$ is closed under finite union, we may replace $X_{n}$ by
$X_{1}\cup\ldots\cup X_{n}$; in other words, we may assume that
$X_{1}\subseteq X_{2}\subseteq\ldots$. Then $\varphi(X_{n})\to\varphi(X)$ by
continuity from below. Since $\varphi(X_{n})=\varphi(\mathcal{R})$, it follows
that $\varphi(X)=\varphi(X_{n})=\varphi(\mathcal{R})$. Since $X_{n}\subseteq
X$, this implies that $X_{n}\equiv X=0$, and so $X\in\mathcal{R}$.

For any increasing submodular setfunction $\varphi$, we can define a partial
order on roofs as follows. Let $\mathcal{R}$ and $\mathcal{Q}$ be two roofs.
Let $\mathcal{R}\leq\mathcal{Q}$ mean that there is an $A\in\mathcal{R}$ and
$B\in\mathcal{Q}$ such that $A\subseteq B$. Let us note right away that if
this holds, then for every $A^{\prime}\in\mathcal{R}$ there is a
$B^{\prime}\in\mathcal{Q}$ such that $A^{\prime}\subseteq B^{\prime}$. Indeed,
let $B^{\prime}=B\cup A^{\prime}$. To prove that $B\equiv B^{\prime}$, it
suffices to show that $\varphi(B^{\prime})=\varphi(B)$. Clearly
$\varphi(B^{\prime})\geq\varphi(B)$. On the other hand,

$\varphi(B^{\prime})=\varphi(B\cup(A\cup
A^{\prime}))\leq\varphi(B)+\varphi(A\cup A^{\prime})-\varphi((A\cup
A^{\prime})\cap B)$

by submodularity. Here $\varphi(A\cup A^{\prime})=\varphi(A)$ since $A\equiv
A^{\prime}$, but also $\varphi((A\cup A^{\prime})\cap B)=\varphi(A)$ since
$A\subseteq(A\cup A^{\prime})\cap B\subseteq A\cup A^{\prime}$. Thus we get
that $\varphi(B^{\prime})\leq\varphi(B)$, and so
$\varphi(B^{\prime})=\varphi(B)$.

This argument also shows that if $\mathcal{R}$ and $\mathcal{Q}$ are two roofs
such that $\mathcal{Q}\leq\mathcal{R}$ and $\mathcal{R}\leq\mathcal{Q}$, then
$\mathcal{R}=\mathcal{Q}$.

Motivated by the case of matroids, we define a flat associated with a roof
$\mathcal{R}$ as the union of all roofs $\mathcal{Q}$ such that
$\mathcal{Q}\leq\mathcal{R}$. Every flat is a set ideal in $\mathcal{B}$, but
not necessarily a principal ideal, by the example above. Nevertheless, the
flat determines its roof: if two roofs $\mathcal{R}$ and $\mathcal{Q}$ define
the same flat, then $\mathcal{R}\leq\mathcal{Q}$ and
$\mathcal{Q}\leq\mathcal{R}$ by the definition of flats,, and hence
$\mathcal{R}=\mathcal{Q}$.

Inequality (61) implies that if $A_{1}\equiv A_{2}$, then $A_{1}\cup B\equiv
A_{2}\cup B$ for every $B$. Applying this twice, we get that if $A_{1}\equiv
A_{2}$ and $B_{1}\equiv B_{2}$, then $A_{1}\cup B_{1}\equiv A_{2}\cup B_{2}$.
In other words, for two roofs $\mathcal{R}$ and $\mathcal{Q}$, if
$A\in\mathcal{R}$ and $B\in\mathcal{Q}$, then the roof containing $A\cup B$
depends only on $\mathcal{R}$ and $\mathcal{Q}$, and we can denote it by
$\mathcal{R}\lor\mathcal{Q}$. It is trivial to check that this operation is
commutative, associative and idempotent.

So we have a join semilattice on the roofs. It is also easy to verify that
$\mathcal{R}\leq\mathcal{Q}$ if and only if
$\mathcal{R}\lor\mathcal{Q}=\mathcal{Q}$, so the semilattice structure
conforms with the partial order. However, this semilattice is not a lattice in
general, only under a smoothness condition:

######  Lemma 8.4.

If $\varphi$ is an increasing submodular setfunction continuous from below,
then the semilattice structure on the roofs is a lattice.

###### Proof.

We want to prove that if $\mathcal{R}$ and $\mathcal{Q}$ are two roofs, then
there is a unique largest roof $\mathcal{H}$ such that
$\mathcal{H}\leq\mathcal{R}$ and $\mathcal{H}\leq\mathcal{Q}$. This will allow
us to define the meet operation by $\mathcal{R}\land\mathcal{Q}=\mathcal{H}$.

Let $c=\sup\\{\varphi(X\cap Y):~{}X\in\mathcal{R},Y\in\mathcal{Q}\\}$. We
claim that this supremum is a maximum, i.e., it is attained. Let
$X_{1},X_{2},\ldots\in\mathcal{R}$ and $Y_{1},Y_{2},\ldots\in\mathcal{Q}$ be
chosen so that $\varphi(X_{n}\cap Y_{n})\to c$ as $n\to\infty$. Let
$X=\cup_{n}X_{n}$ and $Y=\cup_{n}Y_{n}$, then $X\in\mathcal{R}$ and
$Y\in\mathcal{Q}$ by Lemma 8.3. By monotonicity and the definition of $c$,
$\varphi(X_{n}\cap Y_{n})\leq\varphi(X\cap Y)\leq c$. Since $\varphi(X_{n}\cap
Y_{n})\to c$, this implies that $\varphi(X\cap Y)=c$.

Let $\mathcal{H}$ be the roof containing $X\cap Y$. Then by the definition of
the partial order, $\mathcal{H}\leq\mathcal{R}$ and
$\mathcal{H}\leq\mathcal{Q}$. Let $\mathcal{K}$ be any other roof such that
$\mathcal{K}\leq\mathcal{R}$ and $\mathcal{K}\leq\mathcal{Q}$, and let
$Z\in\mathcal{K}$. Then there are sets $U\in\mathcal{R}$ and $W\in\mathcal{Q}$
such that $Z\subseteq U$ and $Z\subseteq W$. Then $Z\subseteq U\cap W$, which
implies that $\varphi(Z)\leq\varphi(U\cap W)\leq c$. Let $X^{\prime}=U\cup X$
and $Y^{\prime}=W\cup Y$, then $X^{\prime}\in\mathcal{R}$,
$Y^{\prime}\in\mathcal{Q}$, and

$c=\varphi(X\cap Y)\leq\varphi(X^{\prime}\cap Y^{\prime})\leq c.$

Thus $\varphi(X^{\prime}\cap Y^{\prime})=c=\varphi(X\cap Y)$. Since $X\cap
Y\subseteq X^{\prime}\cap Y^{\prime}$, this implies that $X^{\prime}\cap
Y^{\prime}\in\mathcal{H}$. Since $Z\subseteq X^{\prime}\cap Y^{\prime}$, it
follows that $\mathcal{K}\leq\mathcal{H}$. So $\mathcal{H}$ is the unique
largest roof below $\mathcal{R}$ and $\mathcal{Q}$.

###  8.3 Completeness

######  Theorem 8.5.

If $\varphi$ is an increasing submodular setfunction continuous from above,
then the pseudometric $d=d_{\varphi}$ is complete.

###### Proof.

Let $X_{1},X_{2},\ldots$ be a Cauchy sequence of sets in $\mathcal{B}$. Set

$a(n)=\sup_{i,j\geq n}d(X_{i},X_{j}),$

then $a(n)\to 0$ as $n\to\infty$.

We claim that for any $1\leq n_{1}\leq\ldots\leq n_{r}$,

$d(X_{n_{1}},X_{n_{1}}\cup\ldots\cup X_{n_{r}})\leq
a(n_{1})+\ldots+a(n_{r-1}).$ (62)

Indeed, by (59) and (61),

$\displaystyle d(X_{n_{1}},\,$ $\displaystyle X_{n_{1}}\cup\ldots\cup
X_{n_{r}})=\sum_{j=0}^{r}d(X_{n_{1}}\cup\ldots\cup
X_{n_{j+1}},X_{n_{1}}\cup\ldots\cup X_{n_{j}})$
$\displaystyle\leq\sum_{j=1}^{r-1}d(X_{n_{j}}\cup
X_{n_{j+1}},X_{n_{j}})\leq\sum_{j=1}^{r-1}d(X_{n_{j+1}},X_{n_{j}})\leq\sum_{j=1}^{r-1}a(n_{j}).$

Let $n_{1}<n_{2}<\ldots$ be chosen so that $a(n_{k})\leq 2^{-k}$. Let
$Y_{k}=\cup_{j\geq k}X_{n_{j}}$ and $Z=\cap_{k}Y_{k}$. By (62),

$d(X_{n_{k}},X_{n_{k}}\cup\ldots\cup X_{n_{k+r}})\leq
2^{-k}+\ldots+2^{-k-r}<2^{1-k},$

and so by continuity from below (implied by continuity from above),

$d(X_{n_{k}},Y_{k})\leq 2^{1-k}.$

Furthermore, continuity from above implies that
$\varphi(Y_{n_{k}})\to\varphi(Z)$ as $k\to\infty$. Thus

$d(X_{n_{k}},Z)\leq d(X_{n_{k}},Y_{k})+d(Y_{k},Z)\leq 2^{1-k}+d(Y_{k},Z)\to
0\qquad(k\to\infty).$

Now let $m\to\infty$, and let $k$ be the largest $j$ for which $n_{j}\leq m$.
Then

$d(X_{m},Z)\leq d(X_{m},X_{n_{k}})+d(X_{n_{k}},Z)\leq 2^{1-k}+d(X_{n,k},Z)\to
0,$

This shows that $X_{m}\to Z$ in the metric $d$, proving the theorem.

##  9 Strong submodularity

###  9.1 Definition and examples

Choquet [9] introduced a sequence of inequalities generalizing submodularity.
Let $\mathcal{F}$ be a lattice family of sets. For
$A_{0},\ldots,A_{n}\in\mathcal{F}$ and $K\subseteq\\{0,\ldots,n\\}$, set
$A_{K}=\cup_{i\in K}A_{i}$. For $n\geq 1$ and
$A_{0},\ldots,A_{n}\in\mathcal{F}$, consider the following property:

$\sum_{K\subseteq\\{1,\ldots,n\\}}(-1)^{|K|}\varphi(A_{0}\cup A_{K})\leq 0.$
(63)

For $n=1$, this means that $\varphi$ is increasing; for $n=2$, this means that
$\varphi$ is increasing and submodular. We call a setfunction strongly
submodular, if it satisfies inequality (63) for every $n\geq 1$ and every
family $A_{0},\ldots,A_{n}\in\mathcal{F}$. The property is not changed when we
scale $\varphi$ by any positive number, and add a constant to it. For example,
we can make $\varphi(\emptyset)=0$ (if this is useful); then $\varphi$ is
nonnegative. (This is why we don’t require (63) to hold for $n=0$.) It is easy
to see that every modular setfunction on a lattice family is strongly
submodular.

Every increasing modular setfunction $\alpha$ is strongly submodular. This can
be seen by shifting it to satisfy $\alpha(\emptyset)=0$, when it becomes a
charge. Let $C_{1},\ldots,C_{r}$ be the atoms of the (finite) set-algebra
generated by the sets $A_{0}$ and $A_{i}$ $(i\in N=\\{1,\ldots,n\\})$, and let
us compute the contribution of an atom $C_{j}$ to the left hand side of (63).
Let $M=\\{i:~{}C_{j}\subseteq A_{i}\\}$. If $0\in M$, then this contribution
is

$\displaystyle\alpha(C_{j})\sum_{K\subseteq N}(-1)^{|K|}=0$

(here we need that $n\geq 1$). If $0\notin M$, then

$\displaystyle\alpha(C_{j})\sum_{K\subseteq N\atop K\cap
M\not=\emptyset}(-1)^{|K|}$ $\displaystyle=-\alpha(C_{j})\sum_{K\subseteq
N\setminus M}(-1)^{|K|}.$

This sum is zero unless $N=M$, in which case it is $-\alpha(C_{J})\leq 0$.

Clearly, for a strongly submodular setfunction, its negative $\psi=-\varphi$
satisfies the opposite inequality:

$\sum_{K\subseteq\\{1,\ldots,n\\}}(-1)^{|K|}\psi(A_{0}\cup A_{K})\geq 0$ (64)

for all $A_{0},\ldots,A_{n}\in\mathcal{F}$. If we add the condition $\psi\geq
0$, then (64) will hold for $n=0$ as well. The case $n=1$ means that $\psi$ is
decreasing; the cases $n=1,2$ together mean that $f$ is decreasing and
supermodular. In this case, we cannot require that $\psi(\emptyset)=0$; the
condition $\psi(J)=0$ can be achieved, but it is not always useful. We call a
setfunction satisfying inequality (64) for every $n\geq 0$ strongly
supermodular222Choquet calls strongly submodular setfunctions alternating of
infinite order; I feel, however, that this expression is overused. He calls
the setfunction $-\varphi^{c}$ monotone of infinite order.

The following lemma gives a very general construction for strongly submodular
functions.

######  Lemma 9.1.

Every pullback of a strongly submodular setfunction is strongly submodular.

###### Proof.

Let $\varphi$ be a strongly submodular setfunction on the set-algebra
$(J,\mathcal{B})$, let $(I,\mathcal{A})$ be another set-algebra, and let
$\Gamma:~{}\mathcal{A}\to\mathcal{B}$ be a monotone increasing union-
preserving map. We claim that $\psi=\varphi\circ\Gamma$ is strongly
submodular. Indeed, let $A_{0},\ldots,A_{n}\in\mathcal{A}$. Then

$\displaystyle\sum_{0\in K\subseteq I}(-1)^{|K|}\psi(\cup_{i\in K}A_{i})$
$\displaystyle=\sum_{0\in K\subseteq I}(-1)^{|K|}\varphi(\Gamma(\cup_{i\in
K}A_{i}))$ $\displaystyle=\sum_{0\in K\subseteq I}(-1)^{|K|}\varphi(\cup_{i\in
K}\Gamma(A_{i}))\leq 0.$

Among our previous examples, 3.1, 3.9, 3.3 and 3.6 are also strongly
submodular; they are all pullbacks of charges. Example 3.2 is strongly
submodular only for special concave functions $f$ (called totally monotone).
Examples 3.7 and 3.4 are not strongly submodular in general. It will be useful
to generalize Example 3.5 as follows.

Consider two set-algebras $(I,\mathcal{A})$ and $(J,\mathcal{B})$ and a
relation $R\subseteq J\times I$ that is measurable in the sense that if
$X\in\mathcal{B}$ then $R(X)\in\mathcal{A}$. Let $\alpha$ be a charge on
$\mathcal{A}$. We say that the setfunction $\psi(X)=\alpha(R(X))$ is induced
by $R$ and $\alpha$. Since the map $X\mapsto R(X)$ is monotone increasing and
union-preserving, the setfunction $\psi$ is a pullback of $\alpha$. This
implies that $\psi$ is strongly submodular.

Examples 3.1 and 3.9 are easy special cases. Let us show that Example 3.6 is a
special case as well.

######  Lemma 9.2.

Let $(J,\mathcal{B})$ be the sigma-algebra of Borel sets of a compact metric
space $(J,d)$, and let $\mu$ be a measure on $(J,\mathcal{B})$. Then there is
a sigma-algebra $(I,\mathcal{A})$, and a charge $\alpha$ on it, and a
measurable relation $R\subseteq J\times I$, so that

$\mu(\overline{X})=\alpha(R(X))$

for every $X\in\mathcal{B}$.

###### Proof.

Let $I=J\times[0,1]$, let $\mathcal{A}$ be the family of Borel subsets of $I$,
and let

$R=\\{(x,(y,z)):~{}x,y\in J,\,z\in[0,1],\,d(x,y)<z\\}.$

Let $\alpha_{n}=\mu\times\pi_{n}$, where $\pi_{n}$ is the uniform probability
measure on $[0,1]\times[0,1/n)$ ($n\in\mathbb{N}$). Fix a nontrivial
ultrafilter $\mathcal{F}$ on $\mathbb{N}$, and for every set
$X\in\mathcal{A}$, define the ultralimit

$\alpha(X)=\lim_{\mathcal{F}}\alpha_{n}(X).$ (65)

Clearly $\alpha$ is a charge on $\mathcal{A}$. We claim that

$\alpha(R(U))=\mu(\overline{U})$ (66)

for $U\in\mathcal{B}$. For $0<z\leq 1$, let $U_{z}$ denote the
$z$-neighborhood of $U$. Then the set $R(U)\cap(J\times\\{z\\})$ is congruent
with $U_{z}$, and hence

$\alpha_{n}(R(U))=n\int\limits_{0}^{1/n}\mu(U_{z})\,dz.$

For $0<z\leq 1/n$, the inclusion $\overline{U}\subseteq U_{z}\subseteq
U_{1/n}$ implies that $\mu(\overline{U})\leq\mu(U_{z})\leq\mu(U_{1/n})$. Hence
$\mu(\overline{U})\leq\alpha_{n}(R(U))\leq\mu(U_{1/n})$. Since
$\lim_{n\to\infty}\mu(U_{1/n})=\mu(\overline{U})$, this inequality implies
that $\lim_{n\to\infty}\alpha_{n}(R(U))=\mu(\overline{U})$. If this limit
exists, then it is also equal to the ultralimit $\alpha(R(U))$.

Two apparent gaps below should be explained. First, due to the simple
transformation between strongly submodular and supermodular setfunctions,
results about one property can easily be translated to results about the
other, and we will not describe these parallel assertions. Second, it is clear
that a setfunction $\varphi$ is strongly submodular if and only if every
finite quotient of it is strongly submodular. So every result giving
equivalent conditions for strong submodularity in the finite case (to be
discussed in the next section) provides a characterization in the infinite
case, by adding “for every finite quotient”; we don’t state these separately.

###  9.2 The finite case

The results below about the finite case would follow from the much more
general results of Choquet about strongly submodular setfunctions on compact
subsets of a compact set, but the treatment here is (naturally) much simpler
and more explicit.

Before turning to strongly submodular setfunctions, we recall some well-known
results about the linear algebra of subsets of a finite set. Let $V$ be a
finite set with $|V|=n$, and consider the spaces $\mathbb{R}^{2^{V}}$ of
setfunctions on $(V,2^{V})$ and $\mathbb{R}^{2^{V}\times 2^{V}}$ of
$2^{n}\times 2^{n}$ matrices whose rows and columns are indexed by the subsets
of $V$. Let $\mathbf{Z}$ and $\mathbf{M}$ be $2^{V}\times 2^{V}$ matrices,
defined by

$\mathbf{Z}_{X,Y}={\mathbbm{1}}(X\subseteq
Y)\qquad\text{and}\qquad\mathbf{M}_{X,Y}={\mathbbm{1}}(X\subseteq
Y)(-1)^{|Y\setminus X|},$ (67)

The matrices $\mathbf{M}$ and $\mathbf{Z}$ are triangular, with $1$’s in the
diagonal. It is easy to check that $\mathbf{M}=\mathbf{Z}^{-1}$.

Consider a setfunction $\varphi:~{}2^{V}\to\mathbb{R}$, which we can view as a
vector in $\mathbb{R}^{2^{V}}$. The setfunctions $\mathbf{Z}\varphi$ and
$\mathbf{Z}^{\sf T}\varphi$ are called its upper and lower summation
functions, and $\mathbf{M}\varphi$ and $\mathbf{M}^{\sf T}\varphi$ are its
upper and lower Möbius inverses. Explicitly,

$(\mathbf{Z}\varphi)_{X}=\sum_{Y\supseteq X}\varphi(Y),\qquad(\mathbf{Z}^{\sf
T}\varphi)_{X}=\sum_{Y\subseteq X}\varphi(Y)$

and

$(\mathbf{M}\varphi)_{X}=\sum_{Y\supseteq X}(-1)^{|Y\setminus
X|}\varphi(Y),\qquad(\mathbf{M}^{\sf T}\varphi)_{X}=\sum_{Y\subseteq
X}(-1)^{|X\setminus Y|}\varphi(Y)$

Introducing the permutation matrix $\mathbf{C}$ which interchanges a set with
its complement, explicitly $\mathbf{C}_{X,Y}={\mathbbm{1}}(X^{c}=Y)$, we
define $\mathbf{P}=\mathbf{J}-\mathbf{Z}\mathbf{C}$ and
$\mathbf{N}=-\mathbf{C}\mathbf{M}$. The matrices $\mathbf{P}$ and $\mathbf{N}$
are symmetric. The matrix $\mathbf{P}$ has a zero row and column corresponding
to $\emptyset$, so it is not invertible. But we can delete this row and
column, to get the matrix $\mathbf{P}^{\prime}$, which is invertible; it is
easy to check that its inverse is the matrix $\mathbf{N}^{\prime}$, obtained
from $\mathbf{N}$ by deleting the row and the column corresponding to
$\emptyset$. If, instead, we replace the only nonzero element of this row and
column of $\mathbf{N}$ by $0$ (this is a $1$ in the position $V$), then we get
a matrix which is a Penrose inverse of $\mathbf{P}$, and we may denote it by
$\mathbf{P}^{-1}$. The product $\mathbf{P}\mathbf{P}^{-1}$ is obtained from
the identity matrix by replacing its $(\emptyset,\emptyset)$-entry by $0$.

######  Lemma 9.3.

For every setfunction $\varphi:~{}2^{V}\to\mathbb{R}$ with
$\varphi(\emptyset)=0$ there is a unique setfunction
$\alpha:~{}2^{V}\to\mathbb{R}$ with $\alpha(\emptyset)=0$ such that
$\varphi=\mathbf{P}\alpha$.

###### Proof.

We want to solve the equation $\mathbf{P}\alpha=\varphi$. Here $\mathbf{P}$ is
singular, but the value $\alpha(\emptyset)$ plays no role, and we have the
equation $\alpha(\emptyset)=0$. Since $\varphi(\emptyset)=0$, the equation
$\mathbf{P}\alpha=\varphi$ is equivalent with
$\mathbf{P}^{\prime}\alpha^{\prime}=\varphi^{\prime}$, where $\alpha^{\prime}$
and $\varphi^{\prime}$ denote the restrictions of $\alpha$ and $\varphi$ to
nonempty subsets. Equivalently,
$\alpha^{\prime}=\mathbf{N}^{\prime}\varphi^{\prime}$, which we can write as
$\alpha=\mathbf{P}^{-1}\varphi$.

We define the (symmetric) union matrix
$\mathbf{U}_{\varphi}\in\mathbb{R}^{2^{V}\times 2^{V}}$ of a setfunction
$2^{V}\to\mathbb{R}$ by

$(\mathbf{U}_{\varphi})_{X,Y}=\varphi(X\cup Y)\qquad(X,Y\subseteq V).$ (68)

Defining the diagonal matrix $\mathbf{D}_{\varphi}={\rm
diag}(\varphi(X):~{}X\subseteq V)$, we have the simple but very useful
Lindström–Wilf Formula [35, 61]:

$\mathbf{U}_{\varphi}=\mathbf{Z}\mathbf{D}_{\mathbf{M}\varphi}\mathbf{Z}^{\sf
T}.$ (69)

As an immediate consequence, we see that the number of positive [negative]
eigenvalues of the union matrix $\mathbf{U}_{\varphi}$ is the number of
positive [negative] values of the upper Möbius inverse $\mathbf{M}\varphi$.

######  Theorem 9.4.

For a setfunction $\varphi:~{}2^{V}\to\mathbb{R}$ on a finite set $V$ with
$\varphi(\emptyset)=0$, the following are equivalent:

(i) $\varphi$ is strongly submodular;

(ii) $\varphi$ can be induced by the relation ${\bm{\in}}$ and a setfunction
$\alpha:~{}2^{V}\to\mathbb{R}_{+}$.

(iii) $\varphi$ can be induced by a relation $R\subseteq V\times W$ and a
charge $\alpha:~{}2^{W}\to\mathbb{R}_{+}$.

(iv) The upper Möbius inverse satisfies $\mathbf{M}\varphi(X)\leq 0$ for all
$X\subseteq V$, $X\not=V$.

(v) The union matrix $\mathbf{U}_{\varphi}$ has at most one positive
eigenvalue.

###### Proof.

Some implications are easy: (iii)$\Rightarrow$(ii) is trivial,
(ii)$\Rightarrow$(i) follows by Lemma 9.1, and (iv)$\Leftrightarrow$(v)
follows immediately from the Lindström–Wilf Formula (69).

(i)$\Rightarrow$(iv): The inequality $\mathbf{M}\varphi(X)\leq 0$ for
$X\not=V$ means that

$\sum_{Y\supseteq X}(-1)^{|Y\setminus X|}\varphi(Y)=\sum_{Z\subseteq
X^{c}}(-1)^{|Z|}\varphi(X\cup Z)\leq 0.$

This is a special case of Choquet’s condition (63) with $A_{0}=X$ and
$A_{1},\ldots,A_{n}$, the singleton subsets of $X^{c}$. (The condition
$X\not=V$ guarantees the bound $n\geq 1$ in (63).)

(iv)$\Rightarrow$(iii): By Lemma 9.3, there is a unique
$\alpha:~{}2^{V}\to\mathbb{R}$ such that $\alpha(\emptyset)=0$ and
$\mathbf{P}\alpha=\varphi$, which can be expressed as
$\mathbf{P}^{-1}\varphi$. This $\alpha$ and the relation ${\bm{\in}}$ induce
$\varphi$. We have $\alpha\geq 0$ if and only if $\mathbf{P}^{-1}\varphi\geq
0$. Here $\mathbf{P}^{-1}$ agrees with $\mathbf{N}$ except on the row and
column indexed by $\emptyset$, and hence (using that $\varphi(\emptyset)=0$)
we have $\mathbf{N}\varphi=\mathbf{P}^{-1}$ on nonempty sets. Using that
$\mathbf{N}=-\mathbf{C}\mathbf{M}$, we see that $\mathbf{P}^{-1}\varphi\geq 0$
is equivalent to $\mathbf{M}\varphi(X)\leq 0$ for $X\not=V$.

This theorem implies that the extreme rays of the convex cone of strongly
submodular setfunctions on the subsets of a finite set $V$ are given by
$\psi_{T}(X)={\mathbbm{1}}(X\cap T\not=\emptyset)$ ($T\subseteq V$). The
argument in the proof also gives that every setfunction $\varphi$ with
$\varphi(\emptyset)=0$ (submodular or not) can be induced by the relation
${\bm{\in}}$ and a function $\alpha:~{}2^{V}\to\mathbb{R}$. Furthermore,
$\alpha$ is uniquely determined, and the theorem implies that $\alpha\geq 0$
if and only if $\varphi$ is strongly submodular.

A property of a symmetric matrix $M$ stronger than having at most one positive
eigenvalue is that the matrix is of negative type: this means that the
quadratic form $x^{\sf T}Mx$ is nonnegative on the linear hyperplane
${\mathbbm{1}}^{\perp}$ (see e.g. [12], Section 6.1 and [25] for more on this
notion). In general, negative type is a strictly stronger property than having
at most one positive eigenvalue; however, for union matrices, they are
equivalent.

######  Corollary 9.5.

A setfunction $\varphi:~{}2^{V}\to\mathbb{R}$ with $\varphi(\emptyset)=0$ is
strongly submodular if and only if its union matrix $\mathbf{U}_{\varphi}$ is
of negative type.

###### Proof.

The “if” part follows from the obvious fact that negative type matrices have
at most one positive eigenvalue. To prove that $\mathbf{U}_{\varphi}$ is of
negative type for a strongly submodular setfunction
$\varphi:~{}2^{V}\to\mathbb{R}$ with $\varphi(\emptyset)=0$, we have to prove
that for every $x\in\mathbb{R}^{2^{V}}$ such that $\sum_{U\subseteq
V}x_{U}=0$,

$\sum_{U,W\subseteq V}x_{U}x_{W}\varphi(U\cup W)\leq 0.$

Using the representation given by Theorem 9.4(ii), we have

$\displaystyle\sum_{U,W\subseteq V}x_{U}x_{W}\varphi(U\cup
W)=\sum_{U,W\subseteq V}x_{U}x_{W}\sum_{Y\cap(U\cup
W)\not=\emptyset}\alpha(Y).$

Let us determine the coefficient of $\alpha(Y)$ for any given $Y\subseteq V$
in the sum above. Either $U$ or $W$ must meet $Y$, so we can split the sum
into three terms:

$\displaystyle\sum_{U,W\in{\bm{\in}}(Y)}x_{U}x_{W}$
$\displaystyle+\sum_{U\in{\bm{\in}}(Y),W\notin{\bm{\in}}(Y)}x_{U}x_{W}+\sum_{U\notin{\bm{\in}}(Y),W\in{\bm{\in}}(Y)}x_{U}y_{W}$
$\displaystyle=\Big{(}\sum_{U\in
2^{V}}x_{U}\Big{)}^{2}-\Big{(}\sum_{U\notin{\bm{\in}}(Y)}x_{U}\Big{)}^{2}.$

The first term is $0$, proving that the coefficient of $\alpha(Y)$ is
nonpositive. Since $\alpha\geq 0$ if $\varphi$ is strongly submodular, this
proves Corollary 9.5.

Most of the time, this property is studied for distance matrices of finite
(pseudo)metric spaces, where $(M_{ij})_{i,j=1}^{n}$ is the distance of $i$ and
$j$ in some metric space on $\\{1,\ldots,n\\}$. We say that a (possibly
infinite) pseudometric space has negative type, if all finite subspaces have
negative type. Many important metric spaces have this property.

We can turn Corollary 9.5 to a statement about a (pseudo)metric space
introduced in Section 8.

######  Corollary 9.6.

A setfunction on the subsets of a finite set is strongly submodular if and
only if it defines a Björner distance of negative type.

###### Proof.

First, assume that $J$ is finite and $\mathcal{B}=2^{V}$. The matrix of the
Björner distance is given by

$(\mathbf{B}_{\varphi})_{U,W}=2\varphi(U\cup W)-\varphi(U)-\varphi(W),$

and hence for any vector $x\in\mathbb{R}^{2^{V}}$ with $\sum_{U}x_{U}=0$, we
have

$x^{\sf T}\mathbf{B}_{\varphi}x=2\sum_{U,W\subseteq V}\varphi(U\cup
W)x_{U}x_{W}-\sum_{U,W\subseteq V}\varphi(U)x_{U}x_{W}-\sum_{U,W\subseteq
V}\varphi(W)x_{U}x_{W}.$

The last two terms are zero, so the quadratic form is nonpositive is and only
if the first term is.

For the case of a general set-algebra $(J,\mathcal{B})$, it is clear that
$\varphi$ is strongly submodular if and only if every finite quotient of it is
strongly submodular. It is also easy to see that the corresponding Björner
distance defined by $\varphi$ has negative type if an only if this holds for
every finite quotient.

We conclude with describing the behavior of $\varphi$ and $\alpha$ in Theorem
9.4(ii) on quotients. Let $U$ and $V$ be two finite sets, and let
$\Psi:~{}V\to U$ be a surjective map. Let $\varphi$ be a setfunction on
$(V,2^{V})$, then we can consider the quotient
$\varphi_{1}=\varphi\circ\Psi^{-1}$ of $\varphi$ by $\Psi$, as defined in
Section 3.2. Let $\mathbf{P}$ be the $2^{V}\times 2^{V}$ matrix defined above,
and let $\alpha=\mathbf{P}^{-1}\varphi$. Let $\mathbf{P}_{1}$ be the
$2^{U}\times 2^{U}$ matrix analogous to $\mathbf{P}$, and let
$\alpha_{1}=\mathbf{P}_{1}^{-1}\varphi_{1}$. We want to express $\alpha_{1}$
in terms of $\alpha$.

Let us define two $2^{U}\times 2^{V}$ matrices $\mathbf{Q}$, $\mathbf{R}$ by

$\mathbf{Q}_{X,Y}={\mathbbm{1}}(Y=\Psi^{-1}(X)),\qquad\text{and}\qquad\mathbf{R}_{x,y}={\mathbbm{1}}(X=\Psi(Y)).$

Then it is easy to check that $\varphi_{1}=\mathbf{Q}\varphi$, and also the
identity $\mathbf{P}_{1}\mathbf{R}=\mathbf{Q}\mathbf{P}$. Clearly
$(\mathbf{R}\alpha)(\emptyset)=0$, and

$\mathbf{P}_{1}\mathbf{R}\alpha=\mathbf{Q}\mathbf{P}\alpha=\mathbf{Q}\varphi=\varphi_{1},$

showing that $\mathbf{R}\alpha=\alpha_{1}$. Explicitly,

$\alpha_{1}(X)=\sum_{Y\subseteq V\atop\Psi(Y)=X}\alpha(Y).$ (70)

###  9.3 Finite subsets of an infinite set

We prove an extension of Theorem 9.4 for the case when the underlying ring
$(J,J_{\text{\sf fin}})$ consists of the finite subsets of an infinite set.
This is still a very special ring of sets, but it does occur in the important
example of homomorphism numbers and densities (Example 3.8).

We consider the sigma-algebra $(I,\mathcal{A})$, where $I=[0,1]^{\mathbb{N}}$
and $\mathcal{A}=\mathcal{B}^{\mathbb{N}}$. Let $R$ consist of those pairs
$(x,y)\in I\times J$, where $x=(x_{1},x_{2},\ldots)$ and $y=x_{n}$ for some
$n$. It is easy to see that $R$ is a Borel set. Furthermore, this relation is
countably separating, which means that for any two disjoint countable sets
$A,B\subseteq J$ there is an $x\in I$ such that $A\subseteq R(x)$ but
$B\subseteq J\setminus R(x)$. Indeed, any sequence $x\in I$ using all elements
of $A$ but no elements of $B$ has this property.

Recall the notation ${R^{cc}}(X)=R(X^{c})^{c}=\\{y\in J:~{}(x,y)\in
R~{}\forall x\in X\\}$. For a setfunction $\varphi:~{}J_{\text{\sf
fin}}\to\mathbb{R}$, define the function $\overline{\varphi}:~{}J_{\text{\sf
fin}}\times J_{\text{\sf fin}}\to\mathbb{R}$ by

$\overline{\varphi}(A,B)=\sum_{X\subseteq B}(-1)^{|X|}\varphi(A\cup X).$ (71)

We can also write this as

$\overline{\varphi}(A,B)=\sum_{A\subseteq Y\subseteq A\cup B}(-1)^{|Y\setminus
A|}f(Y).$ (72)

######  Theorem 9.7.

Let $\varphi$ be a setfunction on $J_{\text{\sf fin}}$ with
$\varphi(\emptyset)=0$. Then the following are equivalent:

(a) $\varphi$ is strongly submodular;

(b) $\overline{\varphi}(A,B)\leq 0$ for all $A,B\in J_{\text{\sf fin}}$,
$B\not=\emptyset$.

(c) there exists a measure $\alpha$ on $(I,\mathcal{C})$ such that
$\alpha(R(A))=\varphi(A)$ for every $A\in J_{\text{\sf fin}}$.

###### Proof.

All three conditions imply easily that $\varphi$ is increasing, and therefore
nonnegative. We may assume that $\varphi\leq 1$. The implication
(a)$\Rightarrow$(b) is easy, since the relation $\overline{f}(A,B)\leq 0$ for
$B\not=\emptyset$ is a special case of (63). (c)$\Rightarrow$(a) follows by
Lemma 9.1.

To complete the cycle, we prove that (b)$\Rightarrow$(c). We need some
preparation. For $A\in J_{\text{\sf fin}}$, the set $R(A)$ consists of those
sequences from $J^{\mathbb{N}}$ which contain at least one point of $A$, and
${R^{cc}}(A)$ consists of those sequences from $J^{\mathbb{N}}$ which contain
all points of $A$. For $A,B\subseteq J$, let

$H(A,B)={R^{cc}}(B)\setminus R(A).$ (73)

Clearly $H(\emptyset,\emptyset)=I$, more generally,
$H(\emptyset,B)={R^{cc}}(B)$, and $H(A,\emptyset)=I\setminus R(A)$. We also
have $H(A,B)=\emptyset$ if $A\cap B\not=\emptyset$. The fact that $R$ is
countably separating implies that $H(A,B)\not=\emptyset$ if $A$ and $B$ are
countable and $A\cap B=\emptyset$. Trivially $H(A,B)\in\mathcal{C}$ if
$A,B\subseteq I$ are countable. Hence the sigma-algebra generated by the sets
$H(A,B)$ $(A,B\in J_{\text{\sf fin}})$ is just $\mathcal{C}$.

######  Claim 1.

The family $\mathfrak{R}=\\{H(A,B):~{}A,B\in J_{\text{\sf fin}}\\}$ is a
semiring.

It is easy to check that if $A_{i},B_{i}\subseteq J$ ($i\in S$), $A=\cup_{i\in
S}A_{i}$ and $B=\cup_{i\in S}B_{i}$, then

$\bigcap_{i\in S}H(A_{i},B_{i})=H(A,B).$ (74)

Here $A$ and $B$ are finite if $S$ is finite. In particular,

$H(A_{1},B_{1})\cap H(A_{2},B_{2})=H(A_{1}\cup A_{2},B_{1}\cup
B_{2})\qquad(A_{i},B_{i}\in J_{\text{\sf fin}}),$ (75)

so $\mathfrak{R}$ is closed under intersections. We also need the identity
that if $A,B\subseteq U\subseteq J$, then

$H(A,B)=\bigcup_{A\subseteq X\subseteq U\setminus B}H(X,U\setminus X).$ (76)

Note that the sets $H(X,U\setminus X)$ on the right are mutually disjoint, and
so they partition $H(A,B)$.

Using this, it is easy to express the difference of two sets of the form
$H(A,B)$. Let $A,B,C,D\subseteq U\subseteq I$. Then $H(A,B)\setminus H(C,D)$
can be obtained by deleting those terms in (76) satisfying $C\subseteq
X\subseteq U\setminus D$, to get

$H(A,B)\setminus H(C,D)=\bigcup_{A\subseteq X\subseteq U\setminus
B\atop(C\setminus X)\cup(D\cap X)\not=\emptyset}H(X,U\setminus X).$ (77)

In (77) we can take $U=A\cup B\cup C\cup D$. With this choice, if $A,B,C,D$
are finite, then the union has a finite number of terms. This proves the
Claim.

######  Claim 2.

If $A,B,C,D\in J_{\text{\sf fin}}$ and $H(A,B)=H(C,D)\not=\emptyset$, then
$A=C$ and $B=D$.

Indeed, assume that $A\not=C$, and (say) $C\not\subseteq A$. Then $A$ and
$B^{\prime}=(C\setminus A)\cup B$ are disjoint finite sets, and hence
$H(A,B^{\prime})\not=\emptyset$. Let $y\in H(A,B^{\prime})$, then $y\in
H(A,B)$, but $y\in R(C)$ and so $y\notin H(C,D)$.

Define

$\alpha(H(A,B))=\begin{cases}-\overline{\varphi}(A,B),&\text{if
$B\not=\emptyset$},\\\ 1-\varphi(A),&\text{if $B=\emptyset$}.\end{cases}$

We have shown that if $H(A,B)$ is nonempty, then it determines $A$ and $B$, so
$\alpha$ is well-defined.

######  Claim 3.

$\alpha$ is a measure on $\mathfrak{R}$.

We argue first that additivity holds for the partition (76), i.e., for
$A,B,U\in J_{\text{\sf fin}}$ with $A,B\subseteq U$, we have

$\alpha(H(A,B))=\sum_{A\subseteq X\subseteq U\setminus B}\alpha(H(X,U\setminus
X)).$ (78)

For $B\not=\emptyset$, this means that

$\overline{\varphi}(A,B)=\sum_{A\subseteq X\subseteq U\setminus
B}\overline{\varphi}(X,U\setminus X).$ (79)

This can be verified by direct computation. Starting with the right hand side
and using (72), we have

$\displaystyle\sum_{A\subseteq X\subseteq U\setminus
B}\overline{\varphi}(X,U\setminus X)$ $\displaystyle=\sum_{A\subseteq
X\subseteq U\setminus B}\sum_{X\subseteq Z\subseteq U}(-1)^{|Z\setminus
X|}\varphi(Z)$ $\displaystyle=\sum_{A\subseteq Z\subseteq
U}\varphi(Z)\sum_{A\subseteq X\subseteq Z\cap(U\setminus B)}(-1)^{|Z\setminus
X|}.$

The inner sum is

$\begin{cases}(-1)^{|Z\setminus A|},&\text{if $A\subseteq Z\subseteq A\cup
B$},\\\ 0,&\text{otherwise}.\end{cases}$

Hence

$\sum_{A\subseteq X\subseteq U\setminus B}\overline{\varphi}(X,U\setminus
X)=\sum_{A\subseteq Z\subseteq A\cup B}\varphi(Z)(-1)^{Z\setminus
A}=\overline{\varphi}(A,B).$

This proves (78). For $B=\emptyset$, $1$ is added to both sides of equation
(79), and so it can be verified by the same computation.

Next we show finite additivity on the semiring $\mathfrak{R}$.

$H(C,D)=\bigcup_{i=1}^{m}H(A_{i},B_{i})$ (80)

where $A_{i},B_{i},X.Y\in J_{\text{\sf fin}}$ and the sets $H(A_{i},B_{i})$
are disjoint. Choose $U\in J_{\text{\sf fin}}$ large enough so that
$A_{i},B_{i},C,D\subseteq U$. Then each $H(A_{i},B_{i})$ as well as $H(C,D)$
can be expressed as the union of some of the sets $H(X,U\setminus X)$
($X\subseteq U$). Since the sets $H(A_{i},B_{i})$ are disjoint, the sets
$H(X,U\setminus X)$ in these representations are all different, and the union
of all these sets is $H(C,D)$. Applying (78) to each of these representations,
we get that

$\alpha(H(C,D))=\sum_{i=1}^{m}\alpha(H(A_{i},B_{i})),$ (81)

proving Claim 3.

It follows by basic measure theory that $\alpha$ can be extended to a
nonnegative charge on the ring $\mathfrak{R}^{\prime}$ generated by
$\mathfrak{R}$. Next we prove that $\alpha$ is countably additive on the ring
$\mathfrak{R}^{\prime}$. We need a combinatorial fact.

######  Claim 4.

If $X_{1}\supseteq X_{2}\supseteq\ldots$ is a countable sequence of sets in
$X_{i}\in\mathfrak{R}$ and $\cap_{i}X_{i}=\emptyset$, then $X_{i}=\emptyset$
for every sufficiently large $i$.

Let $X_{i}=H(A_{i},B_{i})$ with $A_{i},B_{i}\in J_{\text{\sf fin}}$, then by
(74),

$\bigcap_{i}X_{i}=H(A,B),$

where $A=\cup_{i}A_{i}$ and $B=\cup_{i}B_{i}$. By the separating property of
$R$, $H(A,B)\not=\emptyset$ if $A$ and $B$ are disjoint countable sets, so the
hypothesis that $\cap_{i}X_{i}=\emptyset$ implies that $A\cap B\not=\emptyset$
and hence $A_{i}\cap B_{j}\not=\emptyset$ for some $i,j\geq 1$. But then
$X_{\max(i,j)}=\emptyset$.

######  Claim 5.

The conclusion of Claim 4 also holds if the assumption $X_{i}\in\mathfrak{R}$
is weakened to $X_{i}\in\mathfrak{R}^{\prime}$.

Write $X_{i}=\cup_{j=1}^{k_{i}}X_{ij}$, where $X_{ij}\in\mathfrak{R}$ are
disjoint nonempty sets. We may assume (using (74)) that every $X_{ij}$ is
contained in exactly one of the sets $X_{i-1,j^{\prime}}$. This defines a
rooted tree $T$ with nodes $X_{ij}$, where the parent of $X_{ij}$ is the set
$X_{i-1,j^{\prime}}$ defined above. We consider the set $X_{0,1}=I$ as the
root.

Suppose that $X_{i}\not=\emptyset$ for every $i$. Then $T$ is infinite, and by
Kőnig’s Lemma, it contains an infinite path $X_{0,1}\supseteq
X_{1,j_{1}}\supseteq X_{2,j_{2}}\supseteq\ldots$ Here

$\bigcap_{i=1}^{\infty}X_{i,j_{i}}\subseteq\bigcap_{i=1}^{\infty}X_{i}=\emptyset,$

and so as remarked above, $X_{i,j_{i}}=\emptyset$ for sufficiently large $i$.
This contradicts the definition of $T$, and proves Claim 5.

Thus $\alpha$ is a pre-measure on $(I,\mathfrak{R}^{\prime})$, with

$\alpha(I)=\alpha(H(\emptyset,\emptyset))=\varphi(I)=1.$

The sigma-algebra generated by $\mathfrak{R}^{\prime}$ is $\mathcal{C}$. By
Caratheodory’s Extension Theorem, $\alpha$ extends to a probability measure on
$(I,\mathcal{C})$. Now for any $A\in J_{\text{\sf fin}}$,

$\varphi(A)=\overline{f}(A,\emptyset)=1-\alpha(H(A,\emptyset))=1-\alpha(I\setminus
R(A))=\alpha(R(A)).$

This proves (c).

###  9.4 Compact subsets of a compact set

Choquet proved the following general representation theorem for a large class
of strongly submodular setfunctions ([9], Section 49). Let $K$ be a compact
Hausdorff space and $\mathcal{F}$, the family of its compact subsets. Let us
call $(K,\mathcal{F})$ a compact pair. Clearly $\mathcal{F}$ is a lattice of
sets.

We consider the relation $R=\\{(x,Y):~{}x\in Y\in\mathcal{F}\\}\subseteq
K\times\mathcal{F}$. Let $\mathcal{A}\subseteq 2^{\mathcal{F}}$ be the sigma-
algebra generated by the sets $R(X)$ ($X\in\mathcal{F}$). One of the meany
results in [9] can be stated like this.

######  Theorem 9.8.

Let $\varphi$ be a strongly submodular setfunction on a compact pair
$(K,\mathcal{F})$. Then there is a measure $\mu$ on
$(\mathcal{F},\mathcal{A})$ such that $\varphi(X)=\mu(R(X))$ for all
$X\in\mathcal{F}$.

For the proof of this theorem, its extension to the locally compact case, and
other related results, we refer to [9].

##  10 Problems and projects

######  Problem 10.1 (Logarithms of determinants in the infinite case).

Can Example 3.12 be generalized to the infinite case? Fuglede–Kadison
determinants could play a role here.

######  Problem 10.2 (Decomposition of submodular setfunctions).

Can every bounded submodular setfunction be written as the sum of an
increasing and a decreasing submodular setfunction? This is true in the finite
case, and would strengthen Lemma 3.19.

######  Problem 10.3 (Integrality of separation).

Does Frank’s integral valued version of Theorem 5.1 in the finite case (see
Remark 5.2) has an analogue in the infinite case?

######  Problem 10.4 (Extremal minorizing measures).

We call a minorizing measure $\alpha\in{\sf mm}_{+}(\varphi)$ extremal, if it
cannot be written as $\alpha=(\alpha_{1}+\alpha_{2})/2$, where $\alpha_{1}$
and $\alpha_{2}$ are minorizing measures and $\alpha_{1}\not=\alpha_{2}$. In
the finite case, measures that agree with $\varphi$ on a full chain are the
same as extremal measures. What is the connection in the infinite case? Can
extremal minorizing measures be characterized? Let us raise an explicit
problem:

Let $\varphi$ be an increasing submodular setfunction and $\alpha\in{\sf
mm}_{+}(\varphi)$ with $\alpha(J)=\varphi(J)$. It is not hard to see that if
$(\varphi-\alpha)\land(\varphi^{c}-\alpha^{c})=0$, then $\alpha$ is extremal.
Is this condition also necessary?

######  Problem 10.5 (Extremal minorizing measures II).

In the finite case, every vertex of the intersection of two matroid polytopes
is a vertex of both (if they have the same rank, these are the common bases).
This does not remain valid for polymatroid polytopes, but the vertices of the
intersection of two such polytopes are still integral. Can this be generalized
to the situation of the Submodular Intersection Theorem 5.15? Perhaps
Lindenstrauss’ Theorem mentioned in Remark 7.5 can be extended.

######  Problem 10.6 (Infinite version of submodular minimization).

Finding the minimum of a (non-monotone) submodular setfunction in an efficient
way is a basic algorithmic task in the finite case; this was solved by
analytic methods in [21], and by combinatorial methods in [53, 29]. Submodular
setfunction minimization in the finite case features in many important
applications from computing minimum capacity cuts (cf. Example 3.7) to matroid
intersection (cf. Proposition 11.9).

Extensions of submodular function minimization from Boolean algebras to more
general structures has been considered (Murota [45], Hanada and Hirai [23].
The problem comes up in the measurable case as well (see e.g. Theorem 5.15).
However, it is not clear what an “algorithm” should mean in this case. Perhaps
the following is a valid approach.

Let us call a subset $X\subseteq[0,1]$ presentable, if it is the union of a
finite number of rational intervals. Let $\varphi$ be a submodular setfunction
on the algebra of presentable sets, and assume we have an oracle the gives us
the value of $\varphi(X)$ for any given presentable $X$. Can we compute in
finite time a presentable set on which the value of $\varphi$ is within
$\varepsilon$ to its infimum?

It would be interesting to generalize further results of matroid theory to
submodular setfunctions: matroid partition, sum, duality. Combining with the
results of [40], extending the theory of submodular flows [14] to the measure
theoretic setting may be possible.

In combinatorial optimization, many applications of submodularity use
setfunctions that satisfy the submodular inequality for restricted pairs of
subsets only: intersecting pairs, crossing pairs, subsets with odd
cardinality, paramodular pairs of functions, etc. (see Schrijver [54], Chapter
49). Does any of these have extensions or analogues in the measure-theoretic
setting?

######  Problem 10.7 (Submodularity in the countable case).

A standard Borel sigma-algebra is either finite, countable, or is isomorphic
to the sigma-algebra of Borel sets of $[0,1]$. We have built on the finite
examples as motivation, and studied the uncountable case in some detail. The
countably infinite case may be interesting on its own right.

######  Problem 10.8 (Strong and weak maps).

For matroids, strong and weak maps have been studied as a more algebraic
approach to matroid theory, as two categories associated with matroids. Can
results about these categories be extended to the infinite case?

######  Problem 10.9 (Compactness of the Björner distance).

Under what conditions on an increasing submodular setfunction $\varphi$ is the
set $\mathcal{B}$, endowed with the Björner distance, compact? Since we know
that it is complete, the question is equivalent to the total boundedness of
the space.

######  Problem 10.10 (Strong submodularity).

Lemma 9.1 gives a construction for strongly submodular setfunctions. In
various cases it is known that all strongly submodular setfunctions can be
obtained this way, in particular for finite subsets of an arbitrary set
(Theorem 9.7), or compact subsets of a compact space (Choquet [9], Theorem
49.1). Is there a converse to Lemma 9.1 in general? Is every strongly
submodular setfunction a pullback of a charge?

######  Problem 10.11 (Ingleton’s Inequality).

An inequality strengthening submodularity was introduced by Ingleton [30] (see
also [49]):

$\displaystyle r(X_{1})+r(X_{2})+r(X_{1}\cup X_{2}\cup X_{3})+r(X_{1}\cup
X_{2}\cup X_{4})+r(X_{3}\cup X_{4})~{}$ $\displaystyle\leq r(X_{1}\cup
X_{2})+r(X_{1}\cup X_{3})+r(X_{1}\cup X_{4})+r(X_{2}\cup X_{3})+r(X_{2}\cup
X_{4}).$

(Submodularity is the special case when $X_{4}=\emptyset$). This inequality
holds true for the rank functions of linear and algebraic matroids, but not
all matroids. It is also related to the notion of pseudomodularity mentioned
above. It is not clear what the relationship between strong submodularity and
these other properties is.

######  Problem 10.12 (Limit theories of matroids).

As mentioned in the introduction, there are previous constructions for limits
of matroids sequences: partition lattices of finite sets (which can be viewed
as cycle matroids of complete graphs; Björner [4], Haiman [22]); pseudomodular
matroids (including full algebraic and full transversal matroids; Björner and
Lovász [7]). The limit objects have submodular dimension functions on
lattices, which translate to submodular setfunctions on measurable spaces by
Example 3.10, but no further details have been worked out. A limit theory for
certain (in a sense more general) sequences of matroids was initiated by
Kardoš et al. [33], based on a different concept of the limit object. Limits
of matroids of finite graphs with bounded degrees have been studied in [41].

Can these limit theories be connected? Can they provide motivation for a
general limit theory of matroids?

######  Problem 10.13 (Matroids of graphons).

As remarked in the Introduction, a limit theory seems to be possible for
bounded degree graphs and their limit objects, namely graphings [41]. Can the
matroid of a graphon (dense graph limit) be defined, and described as the
limit of a convergent sequence of matroids of dense graphs? (See e.g. [38] for
definitions.)

## References

  * [1]
  * [2] F. Bach: Submodular functions: from discrete to continuous domains, Mathematical Programming 175 (2019), 419–459.
  * [3] I. Benjamini and O. Schramm: Recurrence of Distributional Limits of Finite Planar Graphs, Electronic J. Probab. 6 (2001), paper no. 23, 1–13.
  * [4] A. Björner: Continuous partition lattice, Proc. Natl. Acad. Sci. 84 (1987) 6327–6329.
  * [5] A. Björner: Continuous matroids revisited, in: I. Bárány, G. Katona, A. Sali (eds), Building Bridges II, Bolyai Society Mathematical Studies 28 (2019), Springer, Berlin–Heidelberg.
  * [6] K.P.S. Bhaskara Rao, M. Bhaskara Rao: Theory of Charges, A Study of Finitely Additive Measures, Academic Press, London–New York–Paris–San Diego–San Francisco (1982).
  * [7] A. Björner, L. Lovász: Pseudomodular lattices and continuous matroids, Acta Sci. Math. Szeged 51 (1987), 295–308.
  * [8] H. Bruhn, R. Diestel, M. Kriesell, R. Pendavingh, P. Wollan, Axioms for infinite matroids, Adv. Math. 239 (2013) 18–46.
  * [9] G. Choquet: Theory of capacities, Annales de l’Institut Fourier, 5 (1954), 131–295.
  * [10] L. Csirmaz: An optimization problem for continuous submodular functions, https://arxiv.org/pdf/2009.12574.pdf
  * [11] D. Denneberg: Non-Additive Measure and Integral, Kluwer Academic Publisher, Dordrecht, 1994.
  * [12] M. Deza and M. Laurent: Geometry of Cuts and Metrics, Springer Verlag, 1997\.
  * [13] J. Edmonds: Submodular functions, matroids, and certain polyhedra, in: Combinatorial Structures and their Applications (eds. R.K. Guy, H. Hanani, N. Sauer and J. Schönheim), Gordon and Breach, New York (1970), pp. 69–87.
  * [14] J. Edmonds, R. Giles: A min-max relation for submodular functions on graphs, Studies in integer programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics 1 (1977), North-Holland, Amsterdam, 185–204.
  * [15] G. Fichtenholz and L.V. Kantorovich: Sur les opérations linéaires dans l’espace des fonctions bornées, Studia Mathematica 5 (1934), 69–98.
  * [16] A. Frank: An algorithm for submodular functions on graphs, Annals of Discrete Mathematics 16 (1982), 97–120.
  * [17] A. Frank: Connections in Combinatorial Optimization, Oxford University Press (2011).
  * [18] S.G. Gal: Volterra–Choquet nonlinear operators, Topol. Methods Nonlin. Anal. 57 (2021), 89–106.
  * [19] P. Ghirardato: On Independence for non-additive measures, with a Fubini theorem, Journal of Economic Theory 73 (1997), 261–291.
  * [20] R. Glebov, A. Grzesik, T. Klimošová, D. Král’: Finitely forcible graphons and permutons, J. Comb. Theory B 110 (2015), 112–135.
  * [21] M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer (1988).
  * [22] M. Haiman: On Realization of Björner’s ’Continuous Partition Lattice’ by Measurable Partitions, Trans. Amer. MathṠoc. 343 (1994), 695–711.
  * [23] M. Hamada, H. Hirai: Computing the nc-rank via discrete convex optimization on CAT(0) spaces, SIAM Journal on Applied Algebra and Geometry 5 (2021) 10.1137/20M138836X
  * [24] T.H. Hildebrandt: On bounded functional operations, Transactions of the American Mathematical Society 36 (1934), 868–875.
  * [25] P. Hjorth, P. Lison, S. Markvorsen, C. Thomassen: Finite Metric Spaces of Strictly Negative Type, Linear Algebra Appl. 270 (1998), 255–273.
  * [26] C. Hoppen, Y. Kohayakawa, C.G. Moreira, B. Ráth, R.M. Sampaio: Limits of permutation sequences, J. Comb. Theory B 103 (2013), 93–113.
  * [27] C.A.J. Hurkens, L. Lovász, A. Schrijver, É. Tardos: How to tidy up your set-system? in: Combinatorics, Proc. Coll. Eger 1987, Coll. Math. Soc. J. Bolyai 52, North-Holland (1988), 309–314.
  * [28] G. Ivanyos, Y. Qiao, and K.V. Subrahmanyam: Non-commutative Edmonds’ problem and matrix semi-invariants, Computational Complexity 26 (2017), 717–763.
  * [29] S. Iwata, L. Fleischer, S. Fujishige: A combinatorial strongly polynomial algorithm for minimizing submodular functions, J. ACM, 48 (2001), 761–777.
  * [30] A.W. Ingleton: Representation of matroids, in: Combinatorial Mathematics and its Applications (ed. D.J.A. Welsh), Academic Press (1971), 149–167.
  * [31] A.S. Kechris: Classical Descriptive Set Theory, Springer Grad. Texts in Math. 156 (1995).
  * [32] H.G. Kellerer: Duality theorems for marginal problems, Z. Wahrscheinlichkeitstheorie verw. Gebiete 67 (1984), 399–432.
  * [33] F. Kardoš, D. Král’, A. Liebenau, L. Machd: First order convergence of matroids, Europ. J. Combinatorics 59 (2017), 150–168.
  * [34] J Lindenstrauss: A remark on extreme doubly stochastic measures, Amer. Math. Monthly 72 (1965), 379–382.
  * [35] B. Lindström: Determinants on semilattices, Proc. Amer. Math. Soc. 20 (1969), 207–208.
  * [36] V. Losert: Counter-examples to some conjectures about doubly stochastic measures, Pacific J. Math. 99 (1982), 387–397.
  * [37] L. Lovász: Submodular functions and convexity, in: Mathematical Programming: the State of the Art (ed. A. Bachem, M. Grötschel, B. Korte), Springer (1983), 235-257.
  * [38] L. Lovász: Large networks and graph limits, Amer. Math. Soc., Providence, RI (2012).
  * [39] L. Lovász: Graphs and Geometry, Amer. Math. Soc. Colloquium Publ. 65, Providence, R.I. (2019).
  * [40] L. Lovász: Flows on measurable spaces, Geom. Func. Anal. 31 (2021), 402–437.
  * [41] L. Lovász: The matroid of a graphing,
https://arxiv.org/abs/2311.03868

  * [42] L. Lovász, M.D. Plummer: Matching Theory, Akadémiai Kiadó - North Holland, Budapest, 1986 (reprinted by AMS Chelsea Publishing, 2009).
  * [43] K. Murota: Discrete Convex Analysis, Soc. Ind. Appl. Math. (1987).
  * [44] K. Murota: Discrete convex analysis, Mathematical Programming 83 (1998), 313–371.
  * [45] K. Murota: Submodular function minimization and maximization in discrete convex analysis, RIMS Kôkyűroku Bessatsu B23 (2010), 193–211.
  * [46] J. Nešetřil and P. Ossona de Mendez: A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth, Memoirs of the American Mathematical Society 263 (2020), No. 1272.
  * [47] J. von Neumann: Continuous Geometries, Proc. Nat. Acad. Sci. USA 22 (1936), 92-100.
  * [48] J. von Neumann, Examples of Continuous Geometries, Proc. Nat. Acad. Sci. USA 22 (1936), 101-108.
  * [49] J.G. Oxley: Matroid Theory, Oxford University Press, Oxford 1992
  * [50] R. Rado: A theorem on independence relations, The Quarterly J. of Math. (Oxford), 13 (1942), 83–89.
  * [51] A. Recski: Maps of matroids with applications, Discrete Mathematics 303 (2005), 175–185.
  * [52] P. Rigo: Finitely additive mass transportation,
https://arxiv.org/abs/2206.01654

  * [53] A. Schrijver: A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combinatorial Theory B, 80 (2000), 346–355.
  * [54] A. Schrijver: Combinatorial Optimization—Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.
  * [55] Ján Šipoš: Nonlinear integrals, Mathematica Slovaca 29 (1979), 257–270.
  * [56] V. Strassen: The Existence of Probability Measures with Given Marginals, Ann. Math. Stat. 36 (1965), 423–439.
  * [57] J. Toland: The Dual of $L_{\infty}(X,L,\lambda)$, Finitely Additive Measures and Weak Convergence: A Primer, SpringerBriefs in Mathematics, Springer-Verlag, 2020.
  * [58] D.J.A. Welsh: Matroid Theory, L.M.S. Monographs 8, Academic Press (1976).
  * [59] N. White, ed.: Theory of Matroids, Encyclopedia of Mathematics and its Applications 26, Cambridge University Press (1986).
  * [60] H. Whitney: On the abstract properties of linear dependence, Amer. J. Math. 57 (1935), 509–533.
  * [61] H.S. Wilf: Hadamard determinants, Möbius functions, and the chromatic number of a graph, Bull. Amer. Math. Soc. 74 (1968), 960–964.
  * [62] K. Yosida, E. Hewitt: Finitely additive measures, Trans. Amer. Math. Soc. 72 (1952), 46–66.

##  11 Appendices

###  11.1 Charges, a.k.a. finitely additive measures

We collect some facts about charges that we need (see Yosida and Hewitt [62],
Rao and Rao [6], and Toland [57] for more).

Let $(J,\mathcal{B})$ be a set-algebra, let ${\sf Bd}={\sf Bd}(J,\mathcal{B})$
denote the Banach space of bounded $\mathcal{B}$-measurable functions
$J\to\mathbb{R}$ with the supremum norm, and let ${\sf ba}={\sf
ba}(J,\mathcal{B})$ be the Banach space of charges on $\mathcal{B}$ with the
norm $\|\alpha\|=\sup_{X\in\mathcal{B}}|\alpha(X)|$. We define

${\sf Bd}_{+}=\\{f\in{\sf Bd}:~{}f\geq 0\\}\qquad\text{and}\qquad{\sf
ba}_{+}=\\{\mu\in{\sf ba}:~{}\mu\geq 0\\}.$

The following important fact was proved by Hildebrandt [24] and Fichtenholtz
and Kantorovich [15]:

######  Proposition 11.1.

The Banach space ${\sf ba}$ is the continuous dual of the space ${\sf Bd}$.

In other words, every continuous linear functional $\Lambda$ on ${\sf Bd}$ can
be represented as $\Lambda=\widehat{\alpha}$ by a charge $\alpha$. Explicitly,

$\Lambda(h)=\int\limits_{J}h\,d\alpha=\widehat{\alpha}(h)$

for all $h\in{\sf Bd}$.

This duality extends to set-algebras instead of sigma-algebras with some care.
Instead of ${\sf Bd}$, we have to consider the space of
$\mathcal{B}$-continuous functions (functions $f$ such that for every
$\varepsilon>0$ there is a partition of $J$ into a finite number of sets
$B_{i}\in\mathcal{B}$ such that $f$ varies by less than $\varepsilon$ on each
$B_{i}$). See [6], Section 4.7.

Charges on a set-algebra $(J,\mathcal{A})$ are the same as modular
setfunctions $\alpha$ with $\alpha(\emptyset)=0$. It is well known that if
$\alpha$ and $\beta$ are bounded charges, then so are $\alpha\land\beta$ and
$\alpha\lor\beta$. If $\alpha\in{\sf ba}$ and we define
$\alpha_{A}(X)=\alpha(A\cap X)$ for $A\in\mathcal{B}$, then
$\alpha_{A}\land\alpha_{B}=\alpha_{A\cap B}$ and
$\alpha_{A}\lor\alpha_{B}=\alpha_{A\cup B}$.

######  Example 11.2.

Let $J$ be any infinite set, and let $\mathcal{F}$ be a nontrivial ultrafilter
on $J$. Then the indicator function

${\mathbbm{1}}_{\mathcal{F}}(X)={\mathbbm{1}}(X\in\mathcal{F})$

is a charge on all subsets of $J$.

The Jordan Decomposition Theorem for countably additive measures remains valid
in the following form. For $\alpha\in{\sf ba}(\mathcal{A})$, we define its
positive and negative parts by

$\alpha_{+}=\alpha^{\rm
ls}\qquad\text{and}\qquad\alpha_{-}=(-\alpha)_{+}=-\alpha^{\rm li}.$

Then $\alpha_{+},\alpha_{-}\in{\sf ba}_{+}(\mathcal{A})$, and
$\alpha=\alpha_{+}-\alpha_{-}$. However, the Hahn Decomposition Theorem does
not remain valid, only approximately; see [6], Section 2.6.

There is another canonical decomposition of a charge (see [57, 6]). A charge
$\alpha\in{\sf ba}_{+}(\mathcal{B})$ is called purely finitely additive, if
the only countably additive measure $\mu$ such that $0\leq\mu\leq\alpha$ is
the zero measure. A signed measure $\alpha\in{\sf ba}(\mathcal{B})$ is purely
finitely additive if its positive and negative parts are. Every $\alpha\in{\sf
ba}(\mathcal{B})$ has a unique decomposition as $\alpha=\beta+\gamma$ such
that $\beta\in{\sf ba}(\mathcal{B})$ is purely finitely additive and
$\gamma\in{\sf ca}(\mathcal{B})$ is countably additive.

A third decomposition of a charge can be defined as follows. Assume that
$(J,\mathcal{B})$ is the sigma-algebra of Borel sets in a compact Hausdorff
space $K$. Integration by a charge $\alpha$ defines a continuous linear
functional $\mathcal{L}_{\alpha}:~{}{\sf Bd}\to\mathbb{R}$. Continuous
functions on $K$ are bounded, so $\mathcal{L}_{\alpha}$ can be restricted to
the Borel space of continuous functions on $K$. By the Riesz Representation
Theorem, this restriction can be represented as integration according to a
countably additive measure $\overline{\alpha}$. So
$\alpha(f)=\overline{\alpha}(f)$ for every continuous function $f$. To sum up,

######  Proposition 11.3.

Let $\alpha$ be a charge on the Borel sets of a compact Hausdorff space $K$.
Then there is a countably additive measure $\overline{\alpha}$ such that
$\int_{K}f\,d\overline{\alpha}=\int_{K}f\,d\alpha$ for every continuous
function $f:~{}K\to\mathbb{R}$.

This proposition remains valid for locally compact Hausdorff spaces $K$, if
instead of all continuous functions, we restrict the condition to continuous
functions vanishing at infinity (i.e., for which every level set $\\{|f|\geq
c\\}$, $c>0$ is compact).

The difference $\alpha-\overline{\alpha}$ is a charge such that the integral
of any continuous function $f$ with respect to $\alpha-\overline{\alpha}$ is
zero. Note, however, that the map $\alpha\mapsto\overline{\alpha}$ depends on
the compact topology chosen to represent $(J,\mathcal{B})$.

Fubini’s Theorem does not remain valid for charges (Example 11.4), even if one
of the measures is countably additive (Example 11.5).

######  Example 11.4.

Let $J=\mathbb{N}$, let $\mathcal{F}$ be a nontrivial ultrafilter on $J$, and
consider the charge $\alpha(X)={\mathbbm{1}}(X\in\mathcal{F})$ as in Example
11.2. Let $F(x,y)={\mathbbm{1}}(x\leq y)$ for $x,y\in\mathbb{N}$. Then

$\int\limits_{\mathbb{N}}\Big{(}\int\limits_{\mathbb{N}}F(x,y)\,d\alpha(x)\Big{)}\,d\alpha(y)=0$

(since for every $y$, $F(x,y)=0$ except for a finite set of elements $x$), but

$\int\limits_{\mathbb{N}}\Big{(}\int\limits_{\mathbb{N}}F(x,y)\,d\alpha(y)\Big{)}\,d\alpha(x)=1$

(since for every $x$, $F(x,y)=1$ except for a finite set of elements $y$).

######  Example 11.5.

For $x\in\\{0,1\\}^{\mathbb{N}}$, let $x_{i}$ denote the $i$-th bit of $x$.
Let

$J=\big{\\{}(i,j,\varepsilon,\delta):~{}i,j\in\mathbb{N},i<j,\varepsilon,\delta\in\\{0,1\\}\big{\\}}.$

For every $x\in\\{0,1\\}^{\mathbb{N}}$, let
$J_{x}=\\{(i,j,\varepsilon,\delta)\in J:~{}x_{i}=\varepsilon,x_{j}=\delta\\}$.
Let $\mathfrak{C}$ be the family of all finite unions of sets $J_{x}$ and
their subsets.

Clearly $\mathfrak{C}\subseteq 2^{J}$ is a set ideal. We claim that
$J\notin\mathfrak{C}$. Indeed, assume that there is a finite set
$Y\subseteq\\{0,1\\}^{\mathbb{N}}$ such that $J=\cup_{y\in Y}J_{y}$. Then for
every $i<j\in\mathcal{N}$, there is a $y\in Y$ such that $y_{i}=0$ and
$y_{j}=1$. So the edges of the complete graph on $\mathcal{N}$ are colored
with $|Y|$ colors. By Ramsey’s Theorem, there is a monochromatic triangle
$\\{i,j,k\\}$, $i<j<k$. This implies that there is a $y\in Y$ such that
$y_{i}=0$, $y_{j}=1$, but also $y_{j}=0$ and $y_{k}=1$, which is impossible.

The ideal $\mathfrak{C}$ can be extended to a maximal ideal $\mathfrak{D}$.
Since $\mathfrak{C}$ contains all singletons, $\mathfrak{D}$ is not principal.
The ultrafilter $\mathcal{F}=2^{J}\setminus\mathfrak{D}$ defines a charge
$\alpha={\mathbbm{1}}_{\mathcal{F}}$. Let $\lambda$ denote the product measure
of $\\{0,1\\}^{\mathbb{N}}$, and let
$F:~{}J\times\\{0,1\\}^{\mathbb{N}}\to\\{0,1\\}$ be defined by

$F(q,x)={\mathbbm{1}}(q\in J_{x}).$

Then

$\int\limits_{0}^{1}\Big{(}\int\limits_{\mathcal{B}}F(q,x)\,d\alpha(q)\Big{)}\,d\lambda(x)=\int\limits_{0}^{1}\alpha(J_{x})\,d\lambda(x)=0,$

but

$\int\limits_{\mathcal{B}}\Big{(}\int\limits_{0}^{1}F(q,x)\,d\lambda(x)\Big{)}\,d\alpha(q)=\int\limits_{0}^{1}\lambda\\{x:~{}q\in
J_{x}\\}\,d\alpha(q)=\frac{1}{4}.$

So Fubini’s Theorem fails for this example.

Fubini’s Theorem does work under appropriate assumptions on the integrand, of
which we need only one in this paper (Ghirardato [19]).

######  Proposition 11.6.

Let $(I,\mathcal{A})$ and $(J,\mathcal{B})$ be sigma-algebras, $\alpha\in{\sf
ba}(I,\mathcal{A})$, $\beta\in{\sf ba}(J,\mathcal{B})$, and let $F:~{}I\times
J\to\mathbb{R}$ be a bounded measurable function with the comonotonicity
property. Then

$\int\limits_{I}\int\limits_{J}F(x,y)\,d\beta(y)\,d\alpha(x)=\int\limits_{J}\int\limits_{I}F(x,y)\,d\alpha(x)\,d\beta(y).$

We will need the following corollary. For a charge $\alpha\in{\sf ba}$ and
function $f\in{\sf Bd}$, we define the measure $f\cdot\alpha$ by

$(f\cdot\alpha)(X)=\int_{X}f\,d\alpha=\int_{J}{\mathbbm{1}}_{X}f\,d\alpha.$

######  Corollary 11.7.

For every charge $\alpha\in{\sf ba}_{+}$ and comonotonic functions $f,g\in{\sf
Bd}_{+}$, we have

$f\cdot(g\cdot\alpha)=g\cdot(f\cdot\alpha)=(fg)\cdot\alpha.$

###### Proof.

It suffices to prove that the first and third quantities are equal. The
measure on the left can be expressed as

$\displaystyle(f\cdot(g\cdot\alpha))(X)$
$\displaystyle=\int\limits_{X}f(x)\,d(g\cdot\alpha)(x)=\int\limits_{0}^{\infty}{\mathbbm{1}}_{X}\,(g\cdot\alpha)\\{f\geq
t\\}\,dt$
$\displaystyle=\int\limits_{0}^{\infty}\int\limits_{J}{\mathbbm{1}}(x\in
X,f(x)\geq t)g(x)\,d\alpha(x)\,dt.$

By Proposition 11.6, the order of integration can be interchanged provided the
integrand $F(x,t)={\mathbbm{1}}(x\in X,f(x)\geq t)g(x)$ has the comonotonicity
property, which is easy to check. So

$\displaystyle(f\cdot(g\cdot\alpha))(X)$
$\displaystyle=\int\limits_{J}\int\limits_{0}^{\infty}{\mathbbm{1}}(x\in
X,f(x)\geq t)g(x)\,dt\,d\alpha(x)$
$\displaystyle=\int\limits_{J}{\mathbbm{1}}(x\in
X)f(x)g(x)\,d\alpha(x)=((fg)\cdot\alpha)(X).$

We conclude this section with a simple fact about extending modular
setfunctions ([6], Theorem 3.1.6; for the case that will be most important for
us, namely when $\mathcal{L}$ is totally ordered, see also Proposition 2.10 in
[11]).

######  Proposition 11.8.

Let $\mathcal{L}\subseteq 2^{J}$ be a lattice family of subsets of a set $J$
such that $\emptyset\in\mathcal{L}$, and let $\mathcal{N}$ be the set-algebra
generated by the sets in $\mathcal{L}$. Let $\psi$ be a modular setfunction on
$\mathcal{L}$ with $\psi(\emptyset)=0$. Then $\psi$ has a unique extension to
a charge on $\mathcal{N}$.

###  11.2 Matroids

This is an absurdly brief survey of matroid theory, which will be needed to
understand the motivation behind some of the results in this paper. For
monographs about matroid theory, see [49, 51, 58, 59], and also [54], Part IV.

A matroid can be defined as a pair $(E,\mathcal{I})$, where $E$ is a finite
set, $\mathcal{I}\subseteq 2^{E}$, $\mathcal{I}$ is descending,
$\emptyset\in\mathcal{I}$, and the Augmentation Axiom is satisfied: for
$A,B\in\mathcal{I}$ with $|A|<|B|$ there is an element $x\in B\setminus A$
such that $A\cup\\{x\\}\in\mathcal{I}$. Sets in $\mathcal{I}$ are called
independent. Maximal independent sets are called bases; they all have the same
cardinality $r(E)$. A fractional independent set is a vector
$w\in\mathbb{R}^{E}$ that is a convex combination of indicator vectors of
independent sets; a fractional basis is defined analogously.

The setfunction $r(X)=\max\\{|I|:~{}I\in\mathcal{I},I\subseteq X\\}$
($X\subseteq E$) is the rank function of the matroid. The rank function $r$ is
an integer valued increasing submodular setfunction such that $r(\emptyset)=0$
and $r(X)\leq|X|$, and these properties characterize matroid rank functions.
The rank function determines the matroid: Independent sets are characterized
by the equation $r(X)=|X|$.

Maximal sets with a given rank are called flats (also called closed sets). The
flats of a matroid form a lattice with respect to the ordering defined by
inclusion. There are simple and natural axioms defining matroids based on any
of these concepts, for which we refer to the literature.

Matroids were introduced formally by Whitney [60]; see [54], Section 39.10 for
a detailed history of matroid theory.

A more general structure is a polymatroid: a finite set $E$ endowed with an
integer valued increasing submodular setfunction $\rho$ such that
$\rho(\emptyset)=0$. If $\mathcal{H}$ is any family of subsets of a finite set
$V$, then defining $\rho(\mathcal{X})=|\cup\mathcal{X}|$ for
$\mathcal{X}\subseteq\mathcal{H}$, we get a polymatroid $(\mathcal{H},\rho)$.
More generally, if we have a matroid rank function $r$ on the subsets of $V$,
then $\rho(\mathcal{X})=r(\cup(\mathcal{X}))$ defines a polymatroid. It is a
nontrivial fact that every polymatroid arises from an appropriate matroid by
this construction (cf. Section 4.1).

For every finite graph $G=(V,E)$, subsets of $E$ containing no cycles form the
cycle matroid of $G$. Subsets of $E$ whose removal does not disconnect any of
the connected components form the cut matroid or cocycle matroid of $G$.
Another important construction of matroids are linear matroids: Let $d\geq 1$,
and let $r(X)=\dim(\text{lin}(X))$ for $X\subseteq\mathbb{R}^{d}$. Then $r$ is
an increasing integer valued submodular setfunction. The real space
$\mathbb{R}^{d}$ can be replaced by any other finite dimensional linear space,
and by any subset of it. A further important example is an algebraic matroid,
defined by a field $\mathbb{F}$ of finite transcendence rank over a subfield
$\mathbb{G}$; the transcendence rank of a subset is a matroid rank function.

The Greedy Algorithm can be used to obtain another characterization of
matroids. Let $r$ be the rank function of a matroid $(E,\mathcal{I})$, and let
$(v_{1},\ldots,v_{n})$ be any ordering of $E$. Then there is a basis $B$ of
the matroid such that
$|B\cap\\{v_{1},\ldots,v_{k}\\}|=r(\\{v_{1},\ldots,v_{k}\\})$ for
$k=1,\ldots,n$. This basis can be obtained “greedily”, processing the elements
$v_{1},\ldots,v_{n}$ one-by-one, putting each element into $B$ if this
preserves its independence. Conversely, every basis $B$ can be obtained like
this, by considering any ordering starting with the elements of $B$.
Furthermore, the setfunction $\beta(X)=|B\cap X|$ is a measure on the subsets
of $E$ such that $\beta\leq r$.

The set of all vectors $x\in\mathbb{R}_{+}^{V}$ such that

$\sum_{i\in S}x_{i}\leq r(S)$

for all $S\subseteq E$ is a convex polytope ${\sf mm}_{+}(E,r)$ called the
matroid polytope. The vertices of the matroid polytope are the indicator
vectors of independent sets. Furthermore, the face of the matroid polytope
defined by adding the constraint

$\sum_{i\in E}x_{i}=r(E)$

has the indicator vectors of bases as vertices, and it is called the basis
polytope of the matroid.

We illustrate the power of matroid theory by recalling the Matroid
Intersection Theorem (Edmonds [13]), which has many applications, from
matchings to rigidity of frameworks.

######  Proposition 11.9.

Let $(E,\mathcal{I}_{1})$ and $(E,\mathcal{I}_{2})$ be two matroids on a
common underlying set, with rank functions $r_{1}$ and $r_{2}$. Then

$\max_{A\in\mathcal{I}_{1}\cap\mathcal{I}_{2}}|A|=\min_{X\subseteq
E}r_{1}(X)+r_{2}(E\setminus X).$

We will see that several of these fundamental properties of matroids extend to
submodular setfunctions defined on sigma-algebras. It turns out that a natural
extension of a matroid independent set to the measurable case is a special
charge.

###  11.3 Summary of notation

Choquet integral:
$\displaystyle\widehat{\varphi}(f)=\int_{0}^{\infty}\varphi\\{f\geq t\\}\,dt$.

Complementary setfunction: $\varphi^{c}(X)=\varphi(X^{c})$.

Join and meet: $(\varphi\lor\psi)(X)=\sup_{Y\subseteq
X}\big{(}\varphi(Y)+\psi(X\setminus Y)\big{)},$

Join and meet: $(\varphi\land\psi)(X)=\inf_{Y\subseteq
X}\big{(}\varphi(Y)+\psi(X\setminus Y)\big{)}$.

Monotonizations: $\varphi^{\rm li}(X)=\inf_{Y\in\mathcal{F},Y\subseteq
X}\varphi(Y),\qquad\varphi^{\rm ui}(X)=\inf_{Y\in\mathcal{F},Y\supseteq
X}\varphi(Y),$

Monotonizations: $\varphi^{\rm ls}(X)=\sup_{Y\in\mathcal{F},Y\subseteq
X}\varphi(Y),\qquad\varphi^{\rm us}(X)=\sup_{Y\in\mathcal{F},Y\supseteq
X}\varphi(Y)$.

Positive and negative part (measure): $\alpha_{+}=\alpha^{\rm ls}$,

Positive and negative part (measure): $\alpha_{-}=(-\alpha)_{+}=-\alpha^{\rm
li}\qquad(\alpha\in{\sf ba}(\mathcal{A}))$.

Relation applied to a set: $R(X)=\\{y:~{}\exists x\in X,(x,y)\in R\\}$,

Relation applied to a set: $R^{cc}(X)=\\{y:~{}\forall x\in X,(x,y)\in R\\}$,

Restriction and projection: $\varphi_{A}(X)=\varphi(X)$,

Restriction and projection: $\varphi^{A}(X)=\varphi(A^{c}\cup
X)-\varphi(A^{c})\qquad(X\subseteq A)$.

Quotient: $(\varphi\circ\Pi^{-1})(X)=\varphi(\Pi^{-1}(X))$.

Pullback: $(\varphi\circ\Gamma)(X)=\varphi(\Gamma(X))$.

Positive part (submodular):

$\varphi_{\circ}(U)=\inf_{\mathcal{X}}\Big{\\{}\sum_{X\in\mathcal{X}}|\varphi(X)|_{+}:~{}\mathcal{X}\text{~{}partition
of $U$}~{}\Big{\\}}$.

Part continuous from below:

$\varphi_{\bullet}(U)=\inf_{\mathcal{X}}\Big{\\{}\lim_{n\to\infty}\varphi(X_{n}):~{}\mathcal{X}=(X_{1}\subseteq
X_{2}\subseteq\ldots),~{}\cup_{n}X_{n}=U\Big{\\}}$.

Majorizing measure:

${\varphi}^{\sqcap}(U)=\sup_{\mathcal{X}}\Big{\\{}\sum_{X\in\mathcal{X}}\varphi(X):~{}\mathcal{X}\text{~{}partition
of $U$}~{}\Big{\\}}$.