Proof of Limits of Penalized Maxima on a Compact Set

Conventions. We use the order arithmetic of Elementary Arithmetic in an Ordered Field and Elementary Order Arithmetic in an Ordered Field, the fact that $\le$ is a total order, hence reflexive, antisymmetric, transitive and comparing any two elements, and the elementary arithmetic of the underlying field. We use repeatedly that $a\le b$ and $c\le e$ imply $a+c\le b+e$, which follows from claims 2 and 3 of Elementary Arithmetic in an Ordered Field with the addition axioms of the field, and in particular that $a\le b$ implies $c+a\le c+b$. Set $2=1+1$.

Let $d_{K\times K}$ be the restriction of $d_{X\times X}$ to $K\times K$, a metric by claim 1 of The Restriction of a Metric to a Subset Induces the Subspace Topology. Since $d_{K\times K}$ and $d_{X\times X}$ take the same values at points of $K\times K$, a function on $K\times K$ is upper (or lower) semicontinuous on $K\times K$ with respect to one of them if and only if it is so with respect to the other; the same applies to continuity. By A Product of Compact Subsets is Compact in the Product Metric the topological space consisting of $K\times K$ with the subsets open in $(K\times K,d_{K\times K})$ is compact, and $K\times K$ is compact in $X\times X$. Since $K$ is nonempty, so is $K\times K$: if $x\in K$ then $(x,x)\in K\times K$.

Step 1: proof of claim 1. By claim 1 of Semicontinuity Under Negation and Characterization of Continuity, applied at each point of $K$, the function $-v$ is upper semicontinuous on $K$, and then claim 1 of Sums and Nonnegative Multiples of Semicontinuous Functions shows that $u+(-v)$, which is the function $u-v$, is upper semicontinuous on $K$. Claim 1 of Semicontinuous Functions Attain Their Extrema on a Compact Set, applied to the nonempty compact set $K$, provides $x_{M}\in K$ with $(u-v)(x)\le(u-v)(x_{M})$ for every $x\in K$; put $M=(u-v)(x_{M})$. If $M'$ has the two stated properties as well, then $M\le M'$ and $M'\le M$, so $M=M'$ by antisymmetry.

Fix $\alpha$ with $0<\alpha$. Let $\pi_{1},\pi_{2}:K\times K\to X$ be the maps $\pi_{1}(x,y)=x$ and $\pi_{2}(x,y)=y$; by claim 1 of Continuity of the Projections and of the Distance Function on a Product Metric Space, applied with $S=K\times K$, both are continuous on $K\times K$ relative to $K\times K$, and both take values in $K$. By claim 1 of Semicontinuity and Continuity Under Composition with a Continuous Map, applied with $A=K$, $B=K\times K$ and $g=\pi_{1}$, the function $u\circ\pi_{1}$ is upper semicontinuous on $K\times K$. By claim 2 of the same lemma with $g=\pi_{2}$, the function $v\circ\pi_{2}$ is lower semicontinuous on $K\times K$, so $-(v\circ\pi_{2})$ is upper semicontinuous by claim 1 of Semicontinuity Under Negation and Characterization of Continuity. Since $0\le\alpha$, claim 3 of Sums and Nonnegative Multiples of Semicontinuous Functions shows that $\alpha\psi$ is lower semicontinuous on $K\times K$, and claim 1 of Semicontinuity Under Negation and Characterization of Continuity shows that $-(\alpha\psi)$ is upper semicontinuous. Since

two applications of claim 1 of Sums and Nonnegative Multiples of Semicontinuous Functions show that $\Phi_{\alpha}$ is upper semicontinuous on $K\times K$. Claim 1 of Semicontinuous Functions Attain Their Extrema on a Compact Set, applied in the metric space $(X\times X,d_{X\times X})$ to the nonempty compact set $K\times K$, provides a point at which $\Phi_{\alpha}$ attains a greatest value $M_{\alpha}$, unique by antisymmetry as above.

Step 2: proof of claim 2. Let $x\in K$. Then $\psi(x,x)=0$, so $\alpha\psi(x,x)=0$ and $\Phi_{\alpha}(x,x)=u(x)-v(x)=(u-v)(x)$. Hence $(u-v)(x)\le M_{\alpha}$ for every $x\in K$, and taking $x=x_{M}$ gives $M\le M_{\alpha}$.

Now let $0<\alpha$ and $\alpha\le\beta$, and let $(x,y)\in K\times K$. Since $0\le\psi(x,y)$, claim 5 of Elementary Arithmetic in an Ordered Field gives $\alpha\,\psi(x,y)\le\beta\,\psi(x,y)$, and claim 4 of Elementary Order Arithmetic in an Ordered Field gives $-\beta\,\psi(x,y)\le-\alpha\,\psi(x,y)$. Adding $u(x)-v(y)$ yields $\Phi_{\beta}(x,y)\le\Phi_{\alpha}(x,y)$. In particular, choosing a point where $\Phi_{\beta}$ attains $M_{\beta}$,

Step 3: proof of claim 3. Let $w:K\times K\to\mathbb{R}$ be the function $w(x,y)=u(x)-v(y)$, that is $w=(u\circ\pi_{1})+(-(v\circ\pi_{2}))$, which is upper semicontinuous on $K\times K$ by Step 1. By claim 1 of Semicontinuous Functions Attain Their Extrema on a Compact Set there is $C\in\mathbb{R}$ with $w(p)\le C$ for every $p\in K\times K$.

We first record two facts used below. First, for every $p\in K\times K$ we have $0\le\alpha\,\psi(p)$ by claim 5 of Elementary Arithmetic in an Ordered Field, hence $-\alpha\,\psi(p)\le 0$ by claim 4 of Elementary Order Arithmetic in an Ordered Field, and therefore $\Phi_{\alpha}(p)\le w(p)$. Second, if $c\in\mathbb{R}$ and $c\le w(p)$ fails, then $w(p)\le c$ by comparability.

Let $\varepsilon$ satisfy $0<\varepsilon$ and put

By claim 3 of Semicontinuity via Sublevel and Superlevel Sets, applied in the metric space $(X\times X,d_{X\times X})$ with the subset $K\times K$ and the value $M+\varepsilon$, the set $A_{\varepsilon}$ is closed in the topological space $K\times K$ whose open sets are the subsets open in $(K\times K,d_{K\times K})$. That topological space is compact, so Closed Subset of a Compact Space is Compact shows that $A_{\varepsilon}$ is compact in the metric space $(K\times K,d_{K\times K})$.

Case 1: $A_{\varepsilon}$ is empty. Then $w(p)\le M+\varepsilon$ for every $p\in K\times K$, so $\Phi_{\alpha}(p)\le w(p)\le M+\varepsilon$ and hence $M_{\alpha}\le M+\varepsilon$ for every $\alpha$ with $0<\alpha$. Since $0<1$ by claim 6 of Elementary Order Arithmetic in an Ordered Field, the choice $\alpha_{0}=1$ works.

Case 2: $A_{\varepsilon}$ is nonempty. By claim 4 of Semicontinuity and Continuity Under Composition with a Continuous Map the restriction of $\psi$ to $A_{\varepsilon}$ is lower semicontinuous on $A_{\varepsilon}$, so claim 2 of Semicontinuous Functions Attain Their Extrema on a Compact Set, applied in the metric space $(K\times K,d_{K\times K})$ to the nonempty compact set $A_{\varepsilon}$, provides $p^{*}=(x^{*},y^{*})\in A_{\varepsilon}$ with $\psi(p^{*})\le\psi(p)$ for every $p\in A_{\varepsilon}$. Put $c=\psi(p^{*})$.

If $x^{*}=y^{*}$, then $w(p^{*})=u(x^{*})-v(x^{*})=(u-v)(x^{*})\le M$ by claim 1, while $M+\varepsilon\le w(p^{*})$ because $p^{*}\in A_{\varepsilon}$; adding $-M$ to $M+\varepsilon\le M$ gives $\varepsilon\le 0$, contradicting $0<\varepsilon$. Hence $x^{*}\ne y^{*}$, so $\psi(p^{*})\ne 0$ by the hypothesis on $\psi$, and with $0\le c$ this gives $0<c$. By claim 7 of Elementary Order Arithmetic in an Ordered Field the inverse $c^{-1}$ exists.

Put $\alpha_{0}=\max\{1,\,(C-M-\varepsilon)c^{-1}\}$, the maximum of the two displayed numbers. By claim 1 of Elementary Properties of the Maximum of Two Elements we have $1\le\alpha_{0}$ and $(C-M-\varepsilon)c^{-1}\le\alpha_{0}$, so $0<\alpha_{0}$.

Let $\alpha$ satisfy $\alpha_{0}\le\alpha$ and let $p=(x,y)\in K\times K$. If $p\notin A_{\varepsilon}$, then $w(p)\le M+\varepsilon$ and hence $\Phi_{\alpha}(p)\le M+\varepsilon$. If $p\in A_{\varepsilon}$, then $c\le\psi(p)$, so claim 5 of Elementary Arithmetic in an Ordered Field gives $\alpha c\le\alpha\,\psi(p)$ and claim 4 of Elementary Order Arithmetic in an Ordered Field gives $-\alpha\,\psi(p)\le-\alpha c$; adding $w(p)\le C$ yields $\Phi_{\alpha}(p)\le C-\alpha c$. Moreover $(C-M-\varepsilon)c^{-1}\le\alpha$ by transitivity, so multiplying by $c$, which satisfies $0\le c$, gives $C-M-\varepsilon\le\alpha c$ by claim 5 of Elementary Arithmetic in an Ordered Field; claim 4 of Elementary Order Arithmetic in an Ordered Field and adding $C$ then give

Hence $\Phi_{\alpha}(p)\le M+\varepsilon$ in this case as well. Taking $p=(x_{\alpha},y_{\alpha})$ gives $M_{\alpha}\le M+\varepsilon$.

Step 4: proof of claim 4. From $\Phi_{\alpha}(x_{\alpha},y_{\alpha})=M_{\alpha}$ we get

Since $0\le\alpha\,\psi(x_{\alpha},y_{\alpha})$, adding $M_{\alpha}$ gives $M_{\alpha}\le u(x_{\alpha})-v(y_{\alpha})$, and $M\le M_{\alpha}$ by claim 2; transitivity gives the first assertion.

Now let $0<\varepsilon$ and put $\varepsilon_{1}=\varepsilon\cdot 2^{-1}$ and $\varepsilon_{2}=\varepsilon_{1}\cdot 2^{-1}$. By claim 8 of Elementary Order Arithmetic in an Ordered Field we have $0<\varepsilon_{1}$, $\varepsilon_{1}+\varepsilon_{1}=\varepsilon$, $\varepsilon_{1}<\varepsilon$, $0<\varepsilon_{2}$, $\varepsilon_{2}+\varepsilon_{2}=\varepsilon_{1}$ and $\varepsilon_{2}<\varepsilon_{1}$. Let $\alpha_{0}$ be as in claim 3 for $\varepsilon_{2}$ and put $\alpha_{1}=2\alpha_{0}$, which satisfies $0<\alpha_{1}$ by claim 5 of Elementary Order Arithmetic in an Ordered Field.

Let $\alpha_{1}\le\alpha$ and put $\beta=\alpha\cdot 2^{-1}$, so that $0<\beta$, $\beta+\beta=\alpha$ and $\beta<\alpha$ by claim 8. Multiplying $2\alpha_{0}\le\alpha$ by $2^{-1}$, which is nonnegative, gives $\alpha_{0}\le\beta$ by claim 5 of Elementary Arithmetic in an Ordered Field, so claim 3 gives $M_{\beta}\le M+\varepsilon_{2}$.

Since $(x_{\alpha},y_{\alpha})\in K\times K$ and $\alpha\,\psi-\beta\,\psi=\beta\,\psi$ at that point, because $\alpha=\beta+\beta$,

By claim 2 we have $M\le M_{\alpha}$, hence $-M_{\alpha}\le -M$ by claim 4 of Elementary Order Arithmetic in an Ordered Field; adding $-M_{\alpha}$ to the displayed inequality therefore gives

Multiplying by $2$, which is nonnegative, and using $2\beta=\beta+\beta=\alpha$ and $2\varepsilon_{2}=\varepsilon_{2}+\varepsilon_{2}=\varepsilon_{1}$, we obtain

Finally, $\beta\le\alpha$ and claim 2 give $M_{\alpha}\le M_{\beta}\le M+\varepsilon_{2}$, so adding the last two inequalities,

Step 5: proof of claim 5. Let $\rho:K\times K\to\mathbb{R}$ be the function $\rho(x,y)=d(x,y)$. By claim 2 of Continuity of the Projections and of the Distance Function on a Product Metric Space, applied with $T=K\times K$, the function $\rho$ is continuous on $K\times K$ relative to $K\times K$, hence both upper and lower semicontinuous on $K\times K$ by claim 2 of Semicontinuity Under Negation and Characterization of Continuity.

Let $0<\eta$ and put $C_{\eta}=\{p\in K\times K:\;\eta\le\rho(p)\}$. By claim 3 of Semicontinuity via Sublevel and Superlevel Sets the set $C_{\eta}$ is closed in the topological space $K\times K$ described in Step 3, hence compact in the metric space $(K\times K,d_{K\times K})$ by Closed Subset of a Compact Space is Compact. Note that if $p\in K\times K$ and $p\notin C_{\eta}$, then $\eta\le\rho(p)$ fails, so comparability gives $\rho(p)\le\eta$ and $\rho(p)\ne\eta$, that is $\rho(p)<\eta$.

If $C_{\eta}$ is empty, then $d(x_{\alpha},y_{\alpha})<\eta$ for every $\alpha$ with $0<\alpha$, and $\alpha_{2}=1$ works. Otherwise, by claim 4 of Semicontinuity and Continuity Under Composition with a Continuous Map the restriction of $\psi$ to $C_{\eta}$ is lower semicontinuous on $C_{\eta}$, so claim 2 of Semicontinuous Functions Attain Their Extrema on a Compact Set provides $p^{\#}=(x^{\#},y^{\#})\in C_{\eta}$ with $\psi(p^{\#})\le\psi(p)$ for every $p\in C_{\eta}$; put $c_{\eta}=\psi(p^{\#})$. From $\eta\le d(x^{\#},y^{\#})$ and $0<\eta$ we get $d(x^{\#},y^{\#})\ne 0$, so $x^{\#}\ne y^{\#}$ by condition 2 in the definition of a metric; hence $c_{\eta}\ne 0$ by the hypothesis on $\psi$, and $0<c_{\eta}$.

Let $\alpha_{1}$ be as in claim 4 for the value $c_{\eta}$ in place of $\varepsilon$, and put $\alpha_{2}=\max\{\alpha_{1},2\}$, so that $0<\alpha_{2}$ by claim 1 of Elementary Properties of the Maximum of Two Elements. Let $\alpha_{2}\le\alpha$ and suppose that $(x_{\alpha},y_{\alpha})\in C_{\eta}$. Then $c_{\eta}\le\psi(x_{\alpha},y_{\alpha})$, so claim 5 of Elementary Arithmetic in an Ordered Field and claim 4 of the present theorem give

while $2\le\alpha_{2}\le\alpha$ and $0\le c_{\eta}$ give $c_{\eta}+c_{\eta}=2c_{\eta}\le\alpha c_{\eta}$. Hence $c_{\eta}+c_{\eta}\le c_{\eta}$, and adding $-c_{\eta}$ gives $c_{\eta}\le 0$, contradicting $0<c_{\eta}$. Therefore $(x_{\alpha},y_{\alpha})\notin C_{\eta}$, that is $d(x_{\alpha},y_{\alpha})<\eta$.

Step 6: proof of claim 6. Write $r=u(\hat{x})-v(\hat{x})$. Since $\hat{x}\in K$, claim 1 gives $r\le M$.

Let $0<\varepsilon$. Since $u$ is upper semicontinuous at $\hat{x}$ relative to $K$, there is $\delta_{1}$ with $0<\delta_{1}$ such that every $x\in K$ with $d(\hat{x},x)<\delta_{1}$ satisfies $u(x)<u(\hat{x})+\varepsilon$. Since $v$ is lower semicontinuous at $\hat{x}$ relative to $K$, there is $\delta_{2}$ with $0<\delta_{2}$ such that every $y\in K$ with $d(\hat{x},y)<\delta_{2}$ satisfies $v(\hat{x})-\varepsilon<v(y)$. By claim 9 of Elementary Order Arithmetic in an Ordered Field there is $\delta$ with $\delta\le\delta_{1}$, $\delta\le\delta_{2}$ and $\delta$ equal to $\delta_{1}$ or to $\delta_{2}$; in either case $0<\delta$. Put $\delta'=\delta\cdot 2^{-1}$, so $0<\delta'$, $\delta'+\delta'=\delta$ and $\delta'<\delta$ by claim 8.

By claim 5 there is $\alpha_{2}$ with $0<\alpha_{2}$ such that $d(x_{\alpha},y_{\alpha})<\delta'$ whenever $\alpha_{2}\le\alpha$. By the hypothesis on $\hat{x}$, applied with $\delta'$ and with $\beta=\alpha_{2}$, there is $\alpha$ with $\alpha_{2}\le\alpha$ and $d(\hat{x},x_{\alpha})<\delta'$. Fix such an $\alpha$. Then $d(\hat{x},x_{\alpha})<\delta'<\delta\le\delta_{1}$, so $u(x_{\alpha})<u(\hat{x})+\varepsilon$; and condition 4 in the definition of a metric gives

so $v(\hat{x})-\varepsilon<v(y_{\alpha})$ and hence $-v(y_{\alpha})<\varepsilon-v(\hat{x})$ by claim 4 of Elementary Order Arithmetic in an Ordered Field. Adding the two strict inequalities by claim 3 of that lemma,

By claim 4 we have $M\le u(x_{\alpha})-v(y_{\alpha})$, so claim 2 of Elementary Order Arithmetic in an Ordered Field gives $M<r+\varepsilon+\varepsilon$, and in particular $M\le r+\varepsilon+\varepsilon$.

Suppose $r\ne M$. Since $r\le M$, this gives $r<M$ and hence $0<M-r$. Applying the previous paragraph with $\varepsilon=(M-r)\cdot 2^{-1}\cdot 2^{-1}$, which is positive by claim 8 of Elementary Order Arithmetic in an Ordered Field, and using $\varepsilon+\varepsilon=(M-r)\cdot 2^{-1}<M-r$ from the same claim, we obtain

so $M<M$, which is impossible. Hence $r=M$, that is $u(\hat{x})-v(\hat{x})=M$.