I'm reading a proof of **Theorem 1.37** from Santambrogio's *Optimal transport for applied mathematicians: calculus of variations, PDEs, and modeling*. First, I quote related definitions. Let $X,Y$ be Polish spaces and $\overline{\mathbb{R}} := \mathbb R \cup \{\pm \infty\}$.




---


* **Definition 1.10.** Given a function $\chi: X \rightarrow \overline{\mathbb{R}}$ we define its $c$-transform $\chi^{c}: Y \rightarrow \overline{\mathbb{R}}$ by $\chi^{c}(y)=\inf \_{x \in X} c(x, y)-\chi(x)$. We also define the $\bar{c}$-transform of $\zeta: Y \rightarrow \overline{\mathbb{R}}$ by $\zeta^{\bar{c}}(x)=\inf \_{y \in Y} c(x, y)-\zeta(y)$. Moreover, a function $\psi$ defined on $Y$ is $\bar{c}$-concave if there exists $\chi$ such that $\psi=\chi^{c}$ (and, analogously, a function $\varphi$ on $X$ is said to be $c$-concave if there is $\zeta: Y \rightarrow \overline{\mathbb{R}}$ such that $\left.\varphi=\zeta^{\bar{c}}\right)$.
* **Definition 1.36.** Once a function $c: \Omega \times \Omega \rightarrow \mathbb{R} \cup\{+\infty\}$ is given, we say that a set $\Gamma \subset$ $\Omega \times \Omega$ is $c$-cyclically monotone (briefly $c$-CM) if, for every $k \in \mathbb{N}$, every permutation $\sigma$ and every finite family of points $\left(x\_{1}, y\_{1}\right), \ldots,\left(x\_{k}, y\_{k}\right) \in \Gamma$ we have
$$
\sum\_{i=1}^{k} c\left(x\_{i}, y\_{i}\right) \leq \sum\_{i=1}^{k} c\left(x\_{i}, y\_{\sigma(i)}\right).
$$


Below is the theorem of my interest.



> 
> **Theorem 1.37.** If $\Gamma \neq \emptyset$ is a $c$-CM set in $X \times Y$ and $c: X \times Y \rightarrow \mathbb{R}$ (note that $c$ is required not to take the value $+\infty)$, then there exists a c-concave function $\varphi: X \rightarrow$ $\mathbb{R} \cup\{-\infty\}$ (different from the constant $-\infty$ function) such that
> $$
> \Gamma \subset\left\{(x, y) \in X \times Y: \varphi(x)+\varphi^{c}(y)=c(x, y)\right\}.
> $$
> 
> 
> 


**Proof.** We will give an explicit formula for the function $\varphi$, prove that it is well-defined and that it satisfies the properties that we want to impose. Let us fix a point $\left(x\_{0}, y\_{0}\right) \in \Gamma:$ for $x \in X$ set
$$
\begin{aligned}
\varphi(x)=\inf \left\{c\left(x, y\_{n}\right)\right.&-c\left(x\_{n}, y\_{n}\right)+c\left(x\_{n}, y\_{n-1}\right)-c\left(x\_{n-1}, y\_{n-1}\right)+\cdots+\\
&\left.+c\left(x\_{1}, y\_{0}\right)-c\left(x\_{0}, y\_{0}\right): n \in \mathbb{N},\left(x\_{i}, y\_{i}\right) \in \Gamma \text { for all } i=1, \ldots, n\right\}
\end{aligned}
$$
Since $c$ is real-valued and $\Gamma$ is non-empty, $\varphi$ never takes the value $+\infty$. If we set, for $y \in Y$,
$$
\begin{aligned}
-\psi(y)=\inf \left\{-c\left(x\_{n}, y\right)\right.&+c\left(x\_{n}, y\_{n-1}\right)-c\left(x\_{n-1}, y\_{n-1}\right)+\cdots+c\left(x\_{1}, y\_{0}\right)+ \\
&\left.-c\left(x\_{0}, y\_{0}\right): n \in \mathbb{N},\left(x\_{i}, y\_{i}\right) \in \Gamma \text { for all } i=1, \ldots, n, y\_{n}=y\right\} .
\end{aligned}
$$


Note that from the definition we have $\psi(y)>-\infty$ if and only if $y \in\left(\pi\_{y}\right)(\Gamma)$. Moreover, by construction we have $\varphi=\psi^{\bar{c}}$. This proves that $\varphi$ is $c$-concave ${ }^{8}$. The fact that $\varphi$ is not constantly $-\infty$ can be seen from $\varphi\left(x\_{0}\right) \geq 0$ : indeed, if we take $x=x\_{0}$, then for any chain of points $\left(x\_{i}, y\_{i}\right) \in \Gamma$ we have
$$
\sum\_{i=0}^{n} c\left(x\_{i+1}, y\_{i}\right) \geq \sum\_{i=0}^{n} c\left(x\_{i}, y\_{i}\right)
$$
where we consider $x\_{n+1}=x\_{0}$. This shows that the infimum in the definition of $\varphi\left(x\_{0}\right)$ is non-negative.


To prove $\varphi(x)+\varphi^{c}(y)=c(x, y)$ on $\Gamma$ it is enough to prove the inequality $\varphi(x)+$ $\varphi^{c}(y) \geq c(x, y)$ on the same set, since by definition of $c$-transform the opposite inequality is always true. Moreover, since $\varphi^{c}=\psi^{\bar{c} c}$ and $\psi^{\bar{c} c} \geq \psi$, it is enough to check $\varphi(x)+\psi(y) \geq c(x, y)$


Suppose $(x, y) \in \Gamma$ and fix $\varepsilon>0$. From $\varphi=\psi^{\bar{c}}$ one can find a point $\bar{y} \in \pi\_{y}(\Gamma)$ such that $\color{blue}{c(x, \bar{y})-\psi(\bar{y})<\varphi(x)+\varepsilon}$. In particular, $\psi(\bar{y}) \neq \pm \infty$. From the definition of $\psi$ one has the inequality $-\psi(y) \leq-c(x, y)+c(x, \bar{y})-\psi(\bar{y})$ (since every chain starting from $\bar{y}$ may be completed adding the point $(x, y) \in \Gamma)$.


Putting together these two informations one gets
$$
-\psi(y) \leq-c(x, y)+c(x, \bar{y})-\psi(\bar{y})<-c(x, y)+\varphi(x)+\varepsilon,
$$
which implies the inequality $c(x, y) \leq \varphi(x)+\psi(y)$ since $\varepsilon$ is arbitrary.




---


**My question:** In previous paragraphs, the author said that


* $\varphi: X \to \mathbb R \cup \{-\infty\}$ is proper, i.e., $\varphi$ is not identical to $-\infty$. In particular, $\varphi (x\_0) \ge 0$.
* $\psi(y) \neq -\infty$ if and only if $y \in \pi\_{y} (\Gamma)$ where $\pi\_{y}:X \times Y \to Y$ is the projection map.


My concern lies within the sentence



> 
> Suppose $(x, y) \in \Gamma$ and fix $\varepsilon>0$. From $\varphi=\psi^{\bar{c}}$ one can find a point $\bar{y} \in \pi\_{y}(\Gamma)$ such that $\color{blue}{c(x, \bar{y})-\psi(\bar{y})<\varphi(x)+\varepsilon}$.
> 
> 
> 


With $x\_{n+1} := x\_0$, we have
\begin{align}
\varphi (x) &:= \inf \left \{ c(x, y\_n) - c (x\_n, y\_n) + \sum\_{i=0}^{n-1} [ c(x\_{i+1}, y\_i) - c(x\_{i}, y\_i) ] \,\middle\vert\, n \in \mathbb N^\*,(x\_i, y\_i)\_{i=1}^n \subset \Gamma \right \} \\
&= \inf \left \{ c(x, y\_n) -c(x\_0, y\_n) + \sum\_{i=0}^{n} [ c(x\_{i+1}, y\_i) - c(x\_{i}, y\_i) ] \,\middle\vert\, n \in \mathbb N^\*,(x\_i, y\_i)\_{i=1}^n \subset \Gamma \right \}.
\end{align}


Notice that $(x\_i, y\_i)\_{i=0}^n \subset \Gamma$, so $\sum\_{i=0}^{n} [ c(x\_{i+1}, y\_i) - c(x\_{i}, y\_i) ] \ge 0$. Then we have an estimate
$$
\varphi (x) \ge \inf \{ c(x, y\_n) -c(x\_0, y\_n) \mid y\_n \in \pi\_{y} (\Gamma)\}.
$$


As the author said
$$
\varphi (x) = \psi^{\bar{c}} (x) = \inf\_{y \in Y} [c(x, y) - \psi (y)].
$$



> 
> Then I think the inequality $\color{blue}{c(x, \bar{y})-\psi(\bar{y})<\varphi(x)+\varepsilon}$ is only valid if $\varphi (x) \neq -\infty$. But I could not get how $\varphi (x) \neq -\infty$ in case $(x, y) \in \Gamma$. Could you elaborate on my confusion?
> 
> 
> 



Optimal transport for applied mathematicians: how does $\varphi (x) = \inf_{y \in Y} [c(x, y) - \psi (y)] \neq -\infty$ follow in Theorem 1.37?
I hope I did not misunderstand the question, but it seems $\varphi(x) > - \infty$ holds as follows if $(x, y) \in \Gamma$:


For any $(x\_i, y\_i) \in \Gamma$, $i=1, \dots, n$, we see that
\begin{align}
&c(x, y\_{n}) - c(x\_n, y\_n) + \sum\_{i=0}^{n-1} c(x\_{i+1}, y\_i) - c(x\_i, y\_i) \\
&= c(x, y\_{n}) - c(x\_n, y\_n) + \sum\_{i=0}^{n-1} c(x\_{i+1}, y\_i) - c(x\_i, y\_i) \\&+ c(x\_0, y) - c(x, y) -c(x\_0, y) + c(x, y) \\
&= - c(x, y) + c(x, y\_n) - c(x\_n, y\_n) + c(x\_n, y\_{n-1}) - ... + c(x\_1, y\_0) - c(x\_0, y\_0) + c(x\_0, y) \\
&+c(x, y) - c(x\_0, y) \\
&\geq c(x, y) - c(x\_0, y) > -\infty,
\end{align}
where the last inequality holds since $(x, y) \in \Gamma$ and by $c$-cyclical monotonicity of $\Gamma$.
Thus, $\varphi(x)$ is bounded from below by $c(x, y) - c(x\_0, y)$.


