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 verbatim 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 (also called $c$-conjugate function) $\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, we say that 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)$ and we denote by $c-\operatorname{conc}(X)$ and $\bar{c}-\operatorname{conc}(Y)$ the sets of $c$ - and $\bar{c}$-concave functions, respectively (when $X=Y$ and $c$ is symmetric this distinction between $c$ and $\bar{c}$ will play no more any role and will be dropped as soon as possible).
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 $c(x, \bar{y})-\psi(\bar{y})<\varphi(x)+\varepsilon$. In particular, $\color{blue}{\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) =-\infty$ if and only if $y \notin \pi_{y} (\Gamma)$ where $\pi_{y}:X \times Y \to Y$ is the projection map.
My concern lies within the paragraph
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 $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)$.
We have $$ \varphi (x) =\psi^{\bar{c}} (x) = \inf_{y \in Y} [c(x, y)- \psi (y) ] \quad \forall x \in X. $$
Because $y \in \pi_{y} (\Gamma)$, we clearly have $\psi(y) \neq -\infty$. Now assume $x$ is such that $\varphi (x) = -\infty$. Then for $c(x, \bar{y})-\psi(\bar{y})<\varphi(x)+\varepsilon$ to be true, we at least must have $\psi (\overline y) = +\infty$. This is because $c$ is real-valued. Even in this most optimistic scenario, we still have $-\infty < -\infty$ which is not meaningful.
Could you elaborate on my confusion, i.e., how the author obtains $\color{blue}{\psi(\bar{y}) \neq \pm \infty}$?
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 \} \\ -\psi (y) &:= \inf \left \{ - 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 \text{ s.t. } y_n=y \right \} \\ &= \inf \left \{ -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 \text{ s.t. } y_n=y \right \} \\ &= -c(x_0, y) + \inf \left \{ \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 \text{ s.t. } y_n=y \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. $$
Hence $-\psi (y) \ge -c(x_0, y)$, or equivalently $\psi (y) \le c(x_0, y)$. It follows that $\psi$ never takes the value $+\infty$.
For $(x, y) \in \Gamma$ and $\overline y \in \pi_{y} (\Gamma)$, we have $$ \begin{aligned} &-\psi (y) \\ =& \inf \left \{ - 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 \text{ s.t. } y_n=y \right \} \\ =& \inf \left \{ - c (x_n, y_n) + [ c(x_n, y_{n-1}) - c(x_{n-1}, y_{n-1}) ] + \sum_{i=0}^{n-2} [ 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 \text{ s.t. } y_n=y \right \} \\ \le& \inf \left \{ [- c (x_n, y_n) + c(x_n, y_{n-1})] - c(x_{n-1}, y_{n-1}) + \sum_{i=0}^{n-2} [ c(x_{i+1}, y_i) - c(x_{i}, y_i) ] \,\middle\vert\, n \in \mathbb N^*,n \ge 2, (x_i, y_i)_{i=1}^n \subset \Gamma \text{ s.t. } \begin{align} y_n=y \\ x_n=x \\ y_{n-1} = \overline y \end{align} \right \} \\ =& - c (x, y) + c(x, \overline y) + \inf \left \{- c(x_{n-1}, y_{n-1}) + \sum_{i=0}^{n-2} [ c(x_{i+1}, y_i) - c(x_{i}, y_i) ] \,\middle\vert\, n \in \mathbb N^*,n \ge 2, (x_i, y_i)_{i=1}^n \subset \Gamma \text{ s.t. } y_{n-1} = \overline y \right \} \\ =& - c (x, y) + c(x, \overline y) - \psi (\overline y). \end{aligned} $$