1.1. General duality 19 but here this can be checked more directly). Deduce that C0(C([0, 1] R)) = {0}, and in particular the conclusion of Riesz’ theorem does not apply to C([0, 1] R). Hints: Besides being uniformly bounded, K should satisfy the uniform equicontinuity criterion of Ascoli’s theorem: ∀η 0 ∃δ 0 |x − y| ≤ δ =⇒ sup f∈K |f(x) − f(y)| ≤ η. Using this, for any u ∈ K it is possible to construct v ∈ C([0, 1] R) \ K with u − v L∞ as small as desired. Exercise 1.2. Show that L∞((0, 1)), Cb(Rn) are not separable. Hint: For both cases one can construct a non-countable family of elements, any two of which are separated by a distance exactly 1. 1.1.2. Duality. It is well-known, and widely used, that a linear minimiza- tion problem with convex constraints, like (4), admits a dual formulation. In the context of optimal mass transportation, it was introduced by Kan- torovich in 1942. He was concerned with the particular case when the cost function is a distance: c(x, y) = d(x, y), but in fact his duality theorem holds in considerable generality, as can be seen from Theorem 1.3 below. As mentioned above, there are also versions of this theorem holding in more exotic topological spaces, or even non-topological settings (see [211]), but we shall not enter into these tricky variants. Theorem 1.3 (Kantorovich duality). Let X and Y be Polish spaces, let μ ∈ P (X) and ν ∈ P (Y ), and let c : X × Y → R+ ∪ {+∞} be a lower semi-continuous cost function. Whenever π ∈ P (X × Y ) and (ϕ, ψ) ∈ L1(dμ) × L1(dν), define I[π] = X×Y c(x, y) dπ(x, y), J(ϕ, ψ) = X ϕ dμ + Y ψ dν. Define Π(μ, ν) to be the set of all Borel probability measures π on X × Y such that for all measurable subsets A ⊂ X and B ⊂ Y , π[A × Y ] = μ[A], π[X × B] = ν[B], and define Φc to be the set of all measurable functions (ϕ, ψ) ∈ L1(dμ) × L1(dν) satisfying (1.3) ϕ(x) + ψ(y) ≤ c(x, y) for dμ-almost all x ∈ X, dν-almost all y ∈ Y . Then (1.4) inf Π(μ,ν) I[π] = sup Φc J(ϕ, ψ).

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright no copyright American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.