Proof of A Countable Uniformly Dense Family of Lipschitz Functions on a Compact Metric Space

Throughout, $\mathbb{N}$ is the set of natural numbers, $[r]$ is the initial segment determined by $r\in\mathbb{N}$, $\iota:\mathbb{N}\to\mathbb{R}$ is the canonical map of $\mathbb{R}$, $\mathbb{Q}$ is the set of rational numbers, $B_d(z,\rho)$ denotes the open ball in $(K,d)$ with center $z$ and radius $\rho$, and $K^{r}$ denotes the set of $r$-tuples in $K$.

Step 0 (finite minima). The order of the ordered field $\mathbb{R}$ is a total order, so the minimum of two elements is defined on $\mathbb{R}$. For $r\in\mathbb{N}$ and a map $s:[r]\to\mathbb{R}$ with values $s_k$, define $\min_{k\in[r]}s_k$ by recursion on $r$: put $\min_{k\in[1]}s_k=s_1$ and, whenever $m+1\le r$,

$$\min_{k\in[m+1]}s_k=\min\Bigl\{\min_{k\in[m]}s_k,\ s_{m+1}\Bigr\},$$

the inner minimum being formed from the restriction of $s$ to $[m]$. An induction on $r$, using that $\min\{a,b\}$ is $a$ or $b$ and is a lower bound for both, gives:

(a) $\min_{k'\in[r]}s_{k'}\le s_k$ for every $k\in[r]$;

(b) there is $j\in[r]$ with $\min_{k\in[r]}s_k=s_j$.

From (a) and (b) we obtain a comparison principle:

(c) if $s,t:[r]\to\mathbb{R}$ and $\eta\in\mathbb{R}$ satisfy $s_k\le t_k+\eta$ for every $k\in[r]$, then $\min_{k\in[r]}s_k\le\min_{k\in[r]}t_k+\eta$. Indeed, by (b) there is $j\in[r]$ with $\min_{k\in[r]}t_k=t_j$, and by (a) we get $\min_{k\in[r]}s_k\le s_j\le t_j+\eta$.

Step 1 (continuous functions on $K$ are bounded). Let $f:K\to\mathbb{R}$ be continuous on $K$. Continuity on $K$ is exactly the hypothesis of Extreme Value Theorem on a Compact Subset of a Metric Space for the nonempty compact set $K$, so there are $x_{\min},x_{\max}\in K$ with $f(x_{\min})\le f(x)\le f(x_{\max})$ for every $x\in K$. Put $M_0=\max\{|f(x_{\min})|,|f(x_{\max})|\}$, so $0\le M_0$ by claim 1 of Properties of the Absolute Value in an Ordered Field. By claim 3 of that lemma, $-M_0\le-|f(x_{\min})|\le f(x_{\min})$ and $f(x_{\max})\le|f(x_{\max})|\le M_0$, whence $-M_0\le f(x)\le M_0$ for every $x\in K$, and claim 6 of that lemma gives $|f(x)|\le M_0$. Thus $f$ is bounded, with bound $M_0$.

Step 2 (proof of claim 1). Let $f:K\to\mathbb{R}$ be continuous on $K$ and let $\varepsilon>0$. Let $M_0$ be the bound produced in Step 1 and put $M=M_0+M_0$. Define $F:K\to\mathbb{R}$ by $F(x)=f(x)+M_0$. By claims 1 and 5 of Continuity of Sums and Products of Real-Valued Functions on a Metric Space, $F$ is continuous on $K$, and $-M_0\le f(x)\le M_0$ (claim 6 of Properties of the Absolute Value in an Ordered Field) gives $0\le F(x)\le M$ for every $x\in K$.

By claim 2 of Semicontinuity Under Negation and Characterization of Continuity, $F$ is lower semicontinuous on $K$. So Bounded Lower Semicontinuous Functions are Increasing Limits of Lipschitz Functions applies to $F$ on the nonempty metric space $(K,d)$ with this $M$. Writing

$$F_k(x)=\inf\bigl\{F(y)+\iota(k)\,d(x,y)\ :\ y\in K\bigr\}\qquad(k\in\mathbb{N},\ x\in K),$$

its claim 1 gives $0\le F_k(x)\le F(x)$, its claim 2 that $F_k$ is Lipschitz with constant $\iota(k)$ and continuous on $K$, its claim 3 that $F_k(x)\le F_{k+1}(x)$, and its claim 4 that the sequence $(F_k(x))_{k\in\mathbb{N}}$ converges to $F(x)$.

For $k\in\mathbb{N}$ put $V_k=\{x\in K: F(x)-F_k(x)<\varepsilon\}$. The map $F-F_k$ is continuous on $K$ by claims 4 and 5 of Continuity of Sums and Products of Real-Valued Functions on a Metric Space, hence upper semicontinuous on $K$ by claim 2 of Semicontinuity Under Negation and Characterization of Continuity, so $V_k\in\mathcal{T}_d$ by claim 1 of Semicontinuity via Sublevel and Superlevel Sets, applied with the subset $K$ of $K$ itself.

Since $F_k(x)\le F_{k+1}(x)$ we get $F(x)-F_{k+1}(x)\le F(x)-F_k(x)$, so $V_k\subseteq V_{k+1}$, and by induction $V_k\subseteq V_m$ whenever $k\le m$. Moreover every $x\in K$ lies in some $V_k$: since $(F_k(x))_{k\in\mathbb{N}}$ converges to $F(x)$ there is $k\in\mathbb{N}$ with $|F_k(x)-F(x)|<\varepsilon$, and claim 9 of Properties of the Absolute Value in an Ordered Field gives $-\varepsilon<F_k(x)-F(x)$, that is $F(x)-F_k(x)<\varepsilon$.

Thus $(V_k)_{k\in\mathbb{N}}$ is a family of subsets of $K$ lying in $\mathcal{T}_d$ and covering $K$. As $K$ is compact in $(K,\mathcal{T}_d)$ there is a finite subset $J\subseteq\mathbb{N}$ with $K\subseteq\bigcup_{k\in J}V_k$; since $K$ is nonempty and a union indexed by the empty set is empty, $J$ is nonempty. Hence $J$ has $r$ elements for some $r\in\mathbb{N}$, and a bijection $[r]\to J$ is an $r$-tuple $c$ in $\mathbb{N}$ whose set of components is $J$. The order on $\mathbb{N}$ is a total order, by claims 1, 2 and 3 of Properties of the Order on the Natural Numbers, so Greatest Element of a Finite Family in a Totally Ordered Set provides $j\in[r]$ with $c_k\le c_j$ for every $k\in[r]$. Put $k_0=c_j\in J$. Every $k\in J$ satisfies $k\le k_0$ and hence $V_k\subseteq V_{k_0}$, so $K\subseteq V_{k_0}$, that is

$$0\le F(x)-F_{k_0}(x)<\varepsilon\qquad\text{for every }x\in K .$$

Define $g:K\to\mathbb{R}$ by $g(x)=F_{k_0}(x)-M_0$. Then $f(x)-g(x)=F(x)-F_{k_0}(x)$, so $-\varepsilon\le f(x)-g(x)\le\varepsilon$ and claim 6 of Properties of the Absolute Value in an Ordered Field gives $|f(x)-g(x)|\le\varepsilon$ for every $x\in K$. Finally $g(x)-g(y)=F_{k_0}(x)-F_{k_0}(y)$ for all $x,y\in K$, so $d_{\mathbb{R}}(g(x),g(y))=d_{\mathbb{R}}(F_{k_0}(x),F_{k_0}(y))\le\iota(k_0)\,d(x,y)$ and $g$ is Lipschitz with constant $\iota(k_0)$. This proves claim 1.

Step 3 (a sequence of finite nets). Let $S$ be the set of all $a$ such that $a\in K^{r}$ for some $r\in\mathbb{N}$. If $a\in K^{r}$ and $a\in K^{r'}$ then $[r]=[r']$, since both are the domain of $a$, and hence $r=r'$; so the length of a tuple is well defined.

By claim 3 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field, $0<\iota(n)$ and $0<\iota(n)^{-1}$ for every $n\in\mathbb{N}$. For $n\in\mathbb{N}$ let $A_n$ be the set of those $a\in S$, of length $r$ say, such that

$$K\subseteq\bigcup_{k\in[r]}B_d\bigl(a_k,\iota(n)^{-1}\bigr).$$

Each $A_n$ is nonempty. Indeed, $K$ is compact in $(K,\mathcal{T}_d)$, so by A Compact Subset of a Metric Space is Totally Bounded, applied with the ambient metric space $(K,d)$, the set $K$ is totally bounded in $(K,d)$; hence there is a finite $F\subseteq K$ with $K\subseteq\bigcup_{b\in F}B_d(b,\iota(n)^{-1})$. Since $K$ is nonempty and a union indexed by the empty set is empty, $F$ is nonempty, so $F$ has $r$ elements for some $r\in\mathbb{N}$ and a bijection $[r]\to F$ is an $r$-tuple $a\in K^{r}$ whose set of components is $F$; this $a$ lies in $A_n$.

By Axiom of Countable Choice, applied to the family $(A_n)_{n\in\mathbb{N}}$ of subsets of $S$, there is a sequence $(a^{n})_{n\in\mathbb{N}}$ in $S$ with $a^{n}\in A_n$ for every $n\in\mathbb{N}$. Let $r_n\in\mathbb{N}$ be the length of $a^{n}$ and write $a^{n}_1,\dots,a^{n}_{r_n}$ for its components.

Step 4 (the family $\mathcal{G}$ and its countability). For $m,n\in\mathbb{N}$ and $q\in\mathbb{Q}^{r_n}$ define $g_{m,n,q}:K\to\mathbb{R}$ by

$$g_{m,n,q}(x)=\min_{k\in[r_n]}\bigl(q_k+\iota(m)\,d(x,a^{n}_k)\bigr),$$

the minimum being that of Step 0, and put $\mathcal{G}_{m,n}=\{g_{m,n,q}:q\in\mathbb{Q}^{r_n}\}$.

By The Set of Pairs of Natural Numbers is Countable the set $\mathbb{N}\times\mathbb{N}$ is countable, and it is nonempty, so there is a sequence $(p_j)_{j\in\mathbb{N}}$ in $\mathbb{N}\times\mathbb{N}$ whose set of terms is all of $\mathbb{N}\times\mathbb{N}$; write $p_j=(m_j,n_j)$ and put

$$\mathcal{G}=\bigcup_{j\in\mathbb{N}}\mathcal{G}_{m_j,n_j},$$

so that $\mathcal{G}$ is exactly the set of all $g_{m,n,q}$ with $m,n\in\mathbb{N}$ and $q\in\mathbb{Q}^{r_n}$.

For fixed $m,n$ the set $\mathbb{Q}^{r_n}$ is countable by claim 3 of The Integers and the Rational Numbers are Countable, and $\mathcal{G}_{m,n}$ is the set of values of the map $q\mapsto g_{m,n,q}$ on $\mathbb{Q}^{r_n}$, hence countable by claim 4 of Basic Properties of Countable Sets. Every $\mathcal{G}_{m,n}$ is a subset of the set of all maps from $K$ to $\mathbb{R}$, so $(\mathcal{G}_{m_j,n_j})_{j\in\mathbb{N}}$ is a family of subsets of that set, and A Countable Union of Countable Sets is Countable shows that $\mathcal{G}$ is countable.

Step 5 (members of $\mathcal{G}$ are Lipschitz and bounded). Fix $m,n\in\mathbb{N}$ and $q\in\mathbb{Q}^{r_n}$, and put $u_k(x)=q_k+\iota(m)\,d(x,a^{n}_k)$ for $k\in[r_n]$. For $x,y\in K$ condition 4 of the definition of a metric gives $d(x,a^{n}_k)\le d(x,y)+d(y,a^{n}_k)$, and $0<\iota(m)$, so $u_k(x)\le u_k(y)+\iota(m)d(x,y)$ for every $k\in[r_n]$. By Step 0(c),

$$g_{m,n,q}(x)\le g_{m,n,q}(y)+\iota(m)\,d(x,y),$$

and exchanging $x$ and $y$ gives the same inequality with $x$ and $y$ interchanged. Hence, by claim 6 of Properties of the Absolute Value in an Ordered Field,

$$d_{\mathbb{R}}\bigl(g_{m,n,q}(x),g_{m,n,q}(y)\bigr)=\bigl|g_{m,n,q}(x)-g_{m,n,q}(y)\bigr|\le\iota(m)\,d(x,y),$$

so $g_{m,n,q}$ is Lipschitz with the nonnegative constant $\iota(m)$. By A Lipschitz Map is Uniformly Continuous it is continuous on $K$, hence bounded by Step 1.

Step 6 (the approximation property). Let $f:K\to\mathbb{R}$ be continuous on $K$ and let $\varepsilon>0$. Write $2=1+1$. Applying claim 8 of Elementary Order Arithmetic in an Ordered Field first to $\varepsilon$ and then to $\eta=\varepsilon\cdot 2^{-1}$ yields $0<\eta$, $\eta+\eta=\varepsilon$, and, for $\varepsilon_1=\eta\cdot 2^{-1}$, both $0<\varepsilon_1$ and $\varepsilon_1+\varepsilon_1=\eta$. Consequently $\varepsilon_1+\varepsilon_1+\varepsilon_1<\varepsilon_1+\varepsilon_1+\varepsilon_1+\varepsilon_1=\eta+\eta=\varepsilon$.

By claim 1, already proved, there is a Lipschitz map $g_0:K\to\mathbb{R}$ with $|f(x)-g_0(x)|\le\varepsilon_1$ for every $x\in K$; by the definition of a Lipschitz map there is a nonnegative real $L$ with $|g_0(x)-g_0(y)|\le L\,d(x,y)$ for all $x,y\in K$.

By claim 1 of The Archimedean Property of the Real Numbers choose $m\in\mathbb{N}$ with $L<\iota(m)$. By claim 2 of that theorem choose $n\in\mathbb{N}$ with $\iota(m)+\iota(m)<\iota(n)\,\varepsilon_1$; multiplying by $\iota(n)^{-1}>0$, which is legitimate by claim 10 of Elementary Order Arithmetic in an Ordered Field, gives

$$\bigl(\iota(m)+\iota(m)\bigr)\iota(n)^{-1}<\varepsilon_1 .$$

By claim 2 of The Rational Numbers are Dense in the Real Numbers, for each $k\in[r_n]$ the set of $q_k\in\mathbb{Q}$ with $|g_0(a^{n}_k)-q_k|<\varepsilon_1$ is nonempty; since $[r_n]$ is finite, an induction on $r_n$ produces a tuple $q\in\mathbb{Q}^{r_n}$ with $|g_0(a^{n}_k)-q_k|<\varepsilon_1$ for every $k\in[r_n]$, and no choice principle is needed for this. Claim 9 of Properties of the Absolute Value in an Ordered Field turns these inequalities into $g_0(a^{n}_k)-\varepsilon_1<q_k<g_0(a^{n}_k)+\varepsilon_1$.

Fix $x\in K$ and write $g=g_{m,n,q}\in\mathcal{G}$.

Lower estimate. For every $k\in[r_n]$ we have $g_0(x)\le g_0(a^{n}_k)+L\,d(x,a^{n}_k)$, and $L<\iota(m)$ together with $0\le d(x,a^{n}_k)$ gives $L\,d(x,a^{n}_k)\le\iota(m)\,d(x,a^{n}_k)$, while $g_0(a^{n}_k)\le q_k+\varepsilon_1$. Hence $g_0(x)-\varepsilon_1\le q_k+\iota(m)d(x,a^{n}_k)$ for every $k\in[r_n]$, and Step 0(b) yields $g_0(x)-\varepsilon_1\le g(x)$.

Upper estimate. Since $a^{n}\in A_n$ there is $k_1\in[r_n]$ with $x\in B_d(a^{n}_{k_1},\iota(n)^{-1})$, that is $d(x,a^{n}_{k_1})<\iota(n)^{-1}$. Using Step 0(a), then $q_{k_1}<g_0(a^{n}_{k_1})+\varepsilon_1$, then $g_0(a^{n}_{k_1})\le g_0(x)+L\,d(x,a^{n}_{k_1})\le g_0(x)+\iota(m)d(x,a^{n}_{k_1})$, we obtain

$$g(x)\le q_{k_1}+\iota(m)\,d(x,a^{n}_{k_1})<g_0(x)+\varepsilon_1+\bigl(\iota(m)+\iota(m)\bigr)d(x,a^{n}_{k_1})<g_0(x)+\varepsilon_1+\varepsilon_1 .$$

Combining the two estimates gives $-(\varepsilon_1+\varepsilon_1)\le-\varepsilon_1\le g(x)-g_0(x)\le\varepsilon_1+\varepsilon_1$, so $|g_0(x)-g(x)|\le\varepsilon_1+\varepsilon_1$ by claims 2 and 6 of Properties of the Absolute Value in an Ordered Field. Finally, by claim 5 of that lemma,

$$|f(x)-g(x)|\le|f(x)-g_0(x)|+|g_0(x)-g(x)|\le\varepsilon_1+\varepsilon_1+\varepsilon_1\le\varepsilon .$$

Since $x\in K$ was arbitrary and $g\in\mathcal{G}$ does not depend on $x$, claim 2 is proved.