Kantorovich–Rubinstein duality on compact metric spaces

For any $x\in X$, the ball $B(x,\epsilon )$ is open: if $y\in B(x,\epsilon )$, set $\delta =\epsilon -d(x,y)>0$; whenever $d(y,z)<\delta$, [F2] gives $d(x,z)\le d(x,y)+d(y,z)<\epsilon$, so $B(y,\delta )\subseteq B(x,\epsilon )$. Also $x\in B(x,\epsilon )$, so $\{B(x,\epsilon ):x\in X\}$ is an open cover.

By [F1], finitely many members of that cover still cover $X$. Each selected member is a ball with at least one center; since the list is finite, finite induction selects a center for every selected member without any choice axiom. Removing repeated centers and preserving their first-occurrence order leaves a finite nonempty distinct list $x_1,\dots ,x_m$ whose $\epsilon$-balls cover $X$.

For $i<j$, the function $h_{ij}(x)=d(x,x_i)-d(x,x_j)$ satisfies $\mathrm{\mid }{h}_{ij}(x)-h_{ij}(y)\mathrm{\mid }\le 2d(x,y)$ by applying the triangle inequality in both directions to each distance. If $h_{ij}(x)<0$, then the ball of radius $-h_{ij}(x)\mathrm{/}4$ around $x$ lies in $\{h_{ij}<0\}$; if $h_{ij}(x)>0$, then the ball of radius $h_{ij}(x)\mathrm{/}4$ around $x$ lies in $\{h_{ij}>0\}$. Hence $\{h_{ij}<0\}$ is open and $\{h_{ij}\le 0\}$ is closed.

Define $C_i:={\bigcap }_{j<i}\{x:d(x,x_i)<d(x,x_j)\}\cap {\bigcap }_{j>i}\{x:d(x,x_i)\le d(x,x_j)\}$. These are Borel sets by [F4] and step 3.1. For each $x$, [F3] gives a least index minimizing the finite list $d(x,x_1),\dots ,d(x,x_m)$, so $x$ belongs to the corresponding $C_i$. If $i<j$, membership in $C_i$ gives $d(x,x_i)\le d(x,x_j)$ while membership in $C_j$ gives $d(x,x_j)<d(x,x_i)$; therefore the cells are disjoint and form a partition.

Define $Q(x)=x_i$ on $C_i$. For every subset $A\subseteq F$, $Q^{-1}(A)={\bigcup }_{i:x_i\in A}{C}_i$ is a finite union of Borel sets, so $Q$ is Borel. The net points from step 2.1 have $\epsilon$-balls covering $X$; hence a nearest center is at distance less than $\epsilon$ from every point. Thus $d(x,Q(x))<\epsilon$ for all $x$.

For each $k$, every term in the defining minimum at $x_k$ satisfies $f_i+d(x_k,x_i)\ge f_k$, because $f_k-f_i\le d(x_k,x_i)$ by [F1] and the hypothesis. The term $i=k$ equals $f_k$, so $\tilde{f}(x_k)=f_k$.

For any $x,y\in X$ and every $i$, [F1] gives $d(x,x_i)\le d(x,y)+d(y,x_i)$. Thus $f_i+d(x,x_i)\le d(x,y)+f_i+d(y,x_i)$ for every $i$; taking finite minima yields $\tilde{f}(x)\le d(x,y)+\tilde{f}(y)$. Interchanging $x,y$ and using symmetry gives $\tilde{f}(y)\le d(x,y)+\tilde{f}(x)$, hence $\mathrm{\mid }\tilde{f}(x)-\tilde{f}(y)\mathrm{\mid }\le d(x,y)$.

By [F1], choose an at-most-countable dense set $D\subseteq X$. If $X=\mathrm{\varnothing }$, the empty family is a countable basis. Otherwise set $\mathcal{U}:=\{B(a,1\mathrm{/}n):a\in D,n\in \mathbb{N},n\ge 1\}$. By [F2], the index set $D\times \{n\in \mathbb{N}:n\ge 1\}$ and therefore $\mathcal{U}$ are at most countable.

To check that $\mathcal{U}$ is a basis, let $O$ be open and $x\in O$. By [F4], choose $r>0$ with $B(x,r)\subseteq O$. Apply [F3] to $r\mathrm{/}2$ to choose $n\ge 1$ with $2\mathrm{/}n<r$. Density of $D$ gives $a\in D$ with $d(x,a)<1\mathrm{/}n$. Then $x\in B(a,1\mathrm{/}n)$, and every $y\in B(a,1\mathrm{/}n)$ satisfies $d(x,y)\le d(x,a)+d(a,y)<2\mathrm{/}n<r$. Hence $x\in B(a,1\mathrm{/}n)\subseteq O$.

By [F5], the at-most-countable basis $\mathcal{U}$ makes $X$ second-countable.

If $p_i=0$, [F3] and nonnegativity imply ${\pi }_{ij}=0$ for every $j$; similarly, if $q_j=0$, then ${\pi }_{ij}=0$ for every $i$. For $p_i>0$ define ${\mu }_i(A)=\mu (A\cap C_i)\mathrm{/}{p}_i$ for Borel $A\subseteq X$, and for $q_j>0$ define ${\nu }_j(A)=\nu (A\cap C_j)\mathrm{/}{q}_j$. Countable additivity of $\mu ,\nu$ is preserved by restriction to $C_i,C_j$ and multiplication by $1\mathrm{/}{p}_i,1\mathrm{/}{q}_j$; each restricted measure has total mass one after normalization. Hence these are Borel probability measures concentrated on $C_i,C_j$.

Each conditional probability measure in step 1.1 is sigma-finite because $X$ has mass one. If $X$ is compact, the Borel section-product construction in [F2] applied to the probabilities ${\mu }_i,{\nu }_j$ on the full compact space $X$ gives a Borel product probability for each active pair; the cells themselves need not be compact. If $X$ is second-countable, [F1] and the ordinary product construction in [F2] give the same conclusion. Denote the chosen construction in either case by ${\mu }_i\times {\nu }_j$. Define $\gamma :={\sum }_{i,j:p_i,q_j>0}{\pi }_{ij}({\mu }_i\times {\nu }_j)$. Since zero rows and columns contribute zero by step 1.1, its total mass is ${\sum }_{i,j}{\pi }_{ij}={\sum }_i{p}_i=1$. Thus $\gamma$ is a Borel probability measure.

For Borel $A\subseteq X$, the rectangle formula [F2] and row sums give $\gamma (A\times X)={\sum }_{i:p_i>0}{\sum }_{j:q_j>0}{\pi }_{ij}{\mu }_i(A)={\sum }_{i:p_i>0}{p}_i{\mu }_i(A)={\sum }_i\mu (A\cap C_i)=\mu (A)$. The same calculation using column sums gives $\gamma (X\times A)=\nu (A)$, so $\gamma$ has the required marginals.

The cost $d(x,y)$ is nonnegative Borel by [F7]. For each active pair with $p_i,q_j>0$, [F2] gives $({\mu }_i\times {\nu }_j)(C_i\times C_j)=1$. For every other active pair $(k,\mathrm{\ell })\mathrm{\ne }(i,j)$, disjointness of the partition forces ${\mu }_k(C_i)=0$ or ${\nu }_{\mathrm{\ell }}(C_j)=0$, so [F2] gives its product measure zero on $C_i\times C_j$. Consequently the finite measure sum of step 2.1 gives $\gamma (C_i\times C_j)={\pi }_{ij}$. On zero rows or columns both sides are zero by step 1.1. On each active block, [F6] gives $d(x,y)\le d(x,x_i)+d(x_i,x_j)+d(x_j,y)<d(x_i,x_j)+2\epsilon$. The finite Borel step function $s(x,y):={\sum }_{i,j}(d(x_i,x_j)+2\epsilon ){\mathbf{1}}_{C_i\times C_j}(x,y)$ majorizes $d(x,y)$ on all blocks, including zero-mass ones. Monotonicity [F5], the block masses just computed and the simple-integral formula [F8] give $\int dd\gamma \le \int sd\gamma ={\sum }_{i,j}(d(x_i,x_j)+2\epsilon ){\pi }_{ij}={\sum }_{i,j}{\pi }_{ij}d(x_i,x_j)+2\epsilon$.

Use [F1] at scale $1$ to obtain a finite net $z_1,\dots ,z_s$. Let $M:=2+{\max }_{k,\mathrm{\ell }}d(z_k,z_{\mathrm{\ell }})$, whose maximum exists by [F7]. For any $x,y\in X$, choose net points within $1$ of $x$ and $y$; [F8] gives $d(x,y)<M$. Hence an anchored feasible $f$ satisfies $\mathrm{\mid }f(x)\mathrm{\mid }\le d(x,x_0)<M$. For every $x$ and $r>0$, $d(x,y)<r$ implies $\mathrm{\mid }f(x)-f(y)\mathrm{\mid }<r$, so the metric-topology definition makes $f$ continuous; [F13] then makes it Borel. Also $0\le f^{+},f^{-}\le M$. By [F9] and [F10], each nonnegative integral is at most $M\mu (X)=M$, so [F12] makes $f$ integrable and both dual integrals are finite. The zero function is feasible, so the dual objective set is nonempty and its supremum $D_X$ is a finite real number.

Fix $\epsilon >0$ and use [F1] to obtain distinct net points $x_1,\dots ,x_m$, Borel nearest-center cells $C_1,\dots ,C_m$, and a Borel map $Q$ with $Q(x)=x_i$ on $C_i$ and $d(x,Q(x))<\epsilon$. Set $p_i=\mu (C_i)$ and $q_i=\nu (C_i)$. Countable additivity and the finite Borel partition imply $p_i,q_i\ge 0$ and ${\sum }_i{p}_i={\sum }_i{q}_i=1$. Let $c_{\epsilon }$ be the minimum finite transport cost between these vectors on $F=\{x_1,\dots ,x_m\}$; [F4] ensures that this finite minimum exists and is attained.

By [F4], choose a minimizing finite coupling ${\pi }^{\epsilon }$ and a maximizing normalized finite 1-Lipschitz potential; their common finite primal and dual value is $c_{\epsilon }$.

For any $\gamma \in {\mathrm{\Pi }}_X(\mu ,\nu )$, set ${\pi }_{ij}:=\gamma (C_i\times C_j)$. Its row and column sums are $p_i,q_j$ by the marginal identities and finite additivity, so it is a finite coupling. On $C_i\times C_j$, [F8] gives $d(x_i,x_j)\le d(x_i,x)+d(x,y)+d(y,x_j)<d(x,y)+2\epsilon$. The cells $C_i\times C_j$ form a finite Borel partition of $X\times X$. Integrating the pointwise bounds on these cells and using finite additivity of the nonnegative integral [F11] gives ${\sum }_{i,j}{\pi }_{ij}d(x_i,x_j)\le \int d(x,y)d\gamma +2\epsilon$, since $\gamma (X\times X)=1$. Taking the infimum over $\gamma$ gives $c_{\epsilon }\le W_1^X(\mu ,\nu )+2\epsilon$.

Let $D_F$ be the maximum finite dual value. By [F4], $D_F=c_{\epsilon }$. For any feasible finite potential $(f_i)$, [F3] gives an extension $\tilde{f}$; put $h:=\tilde{f}-\tilde{f}(x_0)$. This anchors $h$ without changing either probability-difference objective. The function $h\circ Q$ is finite-valued Borel simple, so its integrals are ${\sum }_i{p}_{i}h(x_i)$ and ${\sum }_i{q}_{i}h(x_i)$ by [F10]. Pointwise, $\mathrm{\mid }h(x)-h(Q(x))\mathrm{\mid }<\epsilon$. For either probability measure $\rho \in \{\mu ,\nu \}$, let $r=h-h\circ Q$. It is integrable because both terms are bounded Borel functions. Monotonicity [F9] gives $0\le \int (r+\epsilon )d\rho$ and $0\le \int (\epsilon -r)d\rho$; [F10] gives $\int \epsilon d\rho =\epsilon$, and linearity [F12] yields $\mathrm{\mid }\int rd\rho \mathrm{\mid }\le \epsilon$. Hence each finite objective differs from the corresponding compact objective by at most $2\epsilon$, so $D_F\le D_X+2\epsilon$.

Conversely, let $g$ be any feasible compact potential and restrict it to $F$, subtracting $g(x_1)$ to normalize the first coordinate. The finite objective is unchanged by this shift because both probability vectors sum to one. The functions $g\circ Q$ are Borel simple and have the finite sums as their integrals, by [F10]. For each $\rho \in \{\mu ,\nu \}$, the integrable difference $r=g-g\circ Q$ satisfies $-\epsilon \le r\le \epsilon$; applying the two monotonicity and linearity inequalities detailed in step 2.3 gives $\mathrm{\mid }\int rd\rho \mathrm{\mid }\le \epsilon$. Thus each compact integral differs from its finite sum by at most $\epsilon$. By the definition of $D_F$ in step 2.3, every restricted finite objective is at most $D_F$, and $D_X\le D_F+2\epsilon$.

For any $\gamma \in {\mathrm{\Pi }}_X(\mu ,\nu )$ and feasible compact $f$, the Lipschitz constraint gives $f(x)-f(y)\le d(x,y)$. By step 1.1 and [F13], the functions $f\circ {\mathrm{p}\mathrm{r}}_1$ and $f\circ {\mathrm{p}\mathrm{r}}_2$ are bounded Borel, and the metric cost is bounded and Borel; hence they are integrable. The first-coordinate pushforward of $\gamma$ agrees with $\mu$ on every Borel set by the marginal condition, and the second-coordinate pushforward agrees with $\nu$. Equal measures integrate indicators, then simple functions, then all nonnegative Borel functions equally by [F10]; positive-negative decomposition and signed-integral linearity [F12] give equality for bounded signed Borel functions. Thus $\int (f(x)-f(y))d\gamma =\int fd\mu -\int fd\nu$. Since $d(x,y)-(f(x)-f(y))\ge 0$, [F9]–[F10] give a nonnegative integral for this difference, so [F12] implies the dual value is at most the cost of $\gamma$. Taking the infimum gives $D_X\le W_1^X(\mu ,\nu )$.

Apply [F2] to the minimizing plan ${\pi }^{\epsilon }$ of step 2.1. It gives a Borel coupling ${\gamma }^{\epsilon }\in {\mathrm{\Pi }}_X(\mu ,\nu )$ with cost at most $c_{\epsilon }+2\epsilon$. Hence the coupling set is nonempty and $W_1^X(\mu ,\nu )\le c_{\epsilon }+2\epsilon$.

Steps 2.2 and 3.3 give $\mathrm{\mid }{W}_1^X-c_{\epsilon }\mathrm{\mid }\le 2\epsilon$. Steps 2.3 and 3.1 give $\mathrm{\mid }{D}_X-D_F\mathrm{\mid }\le 2\epsilon$, and step 2.3 gives $D_F=c_{\epsilon }$. Combining with step 3.2 yields $D_X\le W_1^X\le c_{\epsilon }+2\epsilon =D_F+2\epsilon \le D_X+4\epsilon$. Since this holds for every $\epsilon >0$, $W_1^X(\mu ,\nu )=D_X$.

By [A1] and [F1], the metric topology of $X$ has an at-most-countable basis, so the hypotheses of [F2] hold. The countable-choice use is exactly the one recorded in [F1]; no other selection is needed.

Apply [F2] to $X,\mu ,\nu$ and the fixed point $x_0$. It gives ${\mathrm{\Pi }}_X(\mu ,\nu )\mathrm{\ne }\mathrm{\varnothing }$ and the displayed Kantorovich–Rubinstein equality.

For an open set $G\subseteq Y$ with $G\mathrm{\ne }Y$, put $K_n:=\{y:d(y,Y\setminus G)\ge 1\mathrm{/}n\}$ for integers $n\ge 1$. By [F1] these sets are closed and compact. They increase, lie in $G$, and exhaust $G$: if $y\in G$, some ball $B(y,r)$ lies in $G$, so $d(y,Y\setminus G)\ge r>0$ and $y\in K_n$ for some $n$. If $G=Y$, use $K_n=Y$. Thus [F3] gives $\nu (G)={\sup }_n\nu (K_n)$ for a specified compact exhaustion of each open $G$, including $G=\mathrm{\varnothing }$.

Let $U\subseteq X\times Y$ be open. The map $y\mapsto (x,y)$ is continuous for fixed $x$, so each $U_x$ is open. Put $h_U(x)=\nu (U_x)$. If $h_U(x)>a$ for $a\ge 0$, step 1.1 provides one compact $K\subseteq U_x$ with $\nu (K)>a$. The coordinate interchange $S:Y\times X\to X\times Y$, $S(y,z)=(z,y)$, is a homeomorphism: it and its inverse take basic open rectangles to basic open rectangles by [F6]. Thus $S^{-1}(U)$ is open and contains $K\times \{x\}$. Apply [F2] in $Y\times X$ to obtain an open neighborhood $V$ of $x$ with $K\times V\subseteq S^{-1}(U)$, or equivalently $V\times K\subseteq U$. For every $z\in V$, $K\subseteq U_z$ and $h_U(z)=\nu (U_z)$. The set $K$ is one of the closed sets in the exhaustion from step 1.1, and $U_z$ is open, so $K$ and $U_z\setminus K$ are Borel by [F6]. Their disjoint union is $U_z$; apply countable additivity to the disjoint sequence $K,U_z\setminus K,\mathrm{\varnothing },\dots$ [F8]. Nonnegativity of $\nu$ [F8] then gives $h_U(z)=\nu (K)+\nu (U_z\setminus K)\ge \nu (K)>a$. Consequently $\{h_U>a\}$ is open for every real $a$ (for $a<0$ it is all of $X$). Hence $h_U$ is lower semicontinuous and Borel: the inverse images of real rays $(a,+\mathrm{\infty })$ are open, and these rays generate the real Borel sigma-algebra, as their rational subfamily generates all open intervals by countable unions and complements.

Every Borel $E\subseteq X\times Y$ has Borel sections because the continuous map $y\mapsto (x,y)$ has inverse image $E_x$. Let $\mathcal{D}$ be the family of Borel $E$ for which $h_E(x):=\nu (E_x)$ is Borel. It contains $X\times Y$, with $h=1$. If $E\in \mathcal{D}$, then $h_{E^c}=1-h_E$ is Borel by [F7]. For disjoint $E_n\in \mathcal{D}$, countable additivity of $\nu$ gives $h_{{\bigcup }_n{E}_n}={\sum }_n{h}_{E_n}$, an increasing limit of Borel partial sums and therefore Borel by [F7]. Thus $\mathcal{D}$ is a lambda-system. All open sets belong to it by step 2.1; the open sets form a pi-system generating $\mathcal{B}(X\times Y)$. By [F4], $\mathcal{D}=\mathcal{B}(X\times Y)$.

Define $\lambda (E)=\int h_{E}d\mu$, which is meaningful and lies in $[0,1]$ by step 3.1 and [F5]. It has $\lambda (\mathrm{\varnothing })=0$ and $\lambda (X\times Y)=1$. For disjoint Borel $E_n$, step 3.1 gives $h_{{\bigcup }_n{E}_n}={\lim }_N{\sum }_{n=1}^N{h}_{E_n}$ increasingly. Finite additivity and monotone convergence [F5] yield $\lambda ({\bigcup }_n{E}_n)={\lim }_N{\sum }_{n=1}^N\lambda (E_n)={\sum }_n\lambda (E_n)$. Hence $\lambda$ is a countably additive Borel probability.

For Borel $A\subseteq X,B\subseteq Y$, the rectangle $A\times B$ is Borel as the intersection of the two coordinate inverse images. Its section measure is $h_{A\times B}(x)={\mathbf{1}}_A(x)\nu (B)$. The simple-integral formula [F5] gives $\lambda (A\times B)=\mu (A)\nu (B)$. Taking $B=Y$ or $A=X$ proves the marginal identities.

Use [F1] at scale $1$ to obtain a finite net $z_1,\dots ,z_s$. Let $M:=2+{\max }_{k,\mathrm{\ell }}d(z_k,z_{\mathrm{\ell }})$, whose maximum exists by [F7]. For any $x,y\in X$, choose net points within $1$ of $x$ and $y$; [F8] gives $d(x,y)<M$. Hence an anchored feasible $f$ satisfies $\mathrm{\mid }f(x)\mathrm{\mid }\le d(x,x_0)<M$. For every $x$ and $r>0$, $d(x,y)<r$ implies $\mathrm{\mid }f(x)-f(y)\mathrm{\mid }<r$, so the metric-topology definition makes $f$ continuous; [F13] then makes it Borel. Also $0\le f^{+},f^{-}\le M$. By [F9] and [F10], each nonnegative integral is at most $M\mu (X)=M$, so [F12] makes $f$ integrable and both dual integrals are finite. The zero function is feasible, so the dual objective set is nonempty and its supremum $D_X$ is a finite real number.

Fix $\epsilon >0$ and use [F1] to obtain distinct net points $x_1,\dots ,x_m$, Borel nearest-center cells $C_1,\dots ,C_m$, and a Borel map $Q$ with $Q(x)=x_i$ on $C_i$ and $d(x,Q(x))<\epsilon$. Set $p_i=\mu (C_i)$ and $q_i=\nu (C_i)$. Countable additivity and the finite Borel partition imply $p_i,q_i\ge 0$ and ${\sum }_i{p}_i={\sum }_i{q}_i=1$. Let $c_{\epsilon }$ be the minimum finite transport cost between these vectors on $F=\{x_1,\dots ,x_m\}$; [F4] ensures that this finite minimum exists and is attained.