Proof of A Closed Totally Bounded Subset of a Complete Metric Space is Compact

The order of $\mathbb{R}$ is total and the rules of Rules of Arithmetic and Order in an Ordered Field apply to it; the order of $\mathbb{N}_{0}$ is total, being a well-order by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §order. Open balls $B_{d}(a,r)$ are as in Open Ball in a Metric Space §ball, with membership as in Open Ball in a Metric Space §membership; finite and infinite sets are as in Finite Sets §finite. Both claims use the axiom of dependent choice, assumed in the statement.

Preliminaries. (A) For $k\in\mathbb{N}$ we have $0<k$ in $\mathbb{R}$ by Inequalities in an Ordered Field: Mixed Transitivity, Strict Sums, Signs, Products, Natural Numbers, Halving, Reciprocals, Absolute Values and Squares §naturals, and $0<1/k$ by Rules of Arithmetic and Order in an Ordered Field §positive-reciprocal. For every real $\eta>0$ there is $k\in\mathbb{N}$ with $1/k<\eta$: by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §archimedean there is $k\in\mathbb{N}$ with $1/\eta<k$, and as $0<1/\eta$, Rules of Arithmetic and Order in an Ordered Field §positive-reciprocal and Rules of Arithmetic and Order in an Ordered Field §reciprocals give $1/k<(1/\eta)^{-1}=\eta$. (B) For a real $\varepsilon>0$, the real $\varepsilon/(1+1)$ satisfies $0<\varepsilon/(1+1)$ by Rules of Arithmetic and Order in an Ordered Field §midpoint, and $\varepsilon/(1+1)+\varepsilon/(1+1)=\varepsilon$. (C) If $I\subseteq\mathbb{N}$ is infinite, then $I\neq\emptyset$ by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §small, and for every $b\in\mathbb{N}_{0}$ there is $m\in I$ with $b<m$, since otherwise $m\le b$ for every $m\in I$ and $I$ would be finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §naturals. (D) For $j,k\in\mathbb{N}$ with $k\le j+1$ we have $k=j+1$ or $k\le j$: if $k\neq j+1$ then $k<j+1$, and $j<k$ is excluded by Arithmetic and Order of the Natural Numbers §successor, so $k\le j$ by Arithmetic and Order of the Natural Numbers §trichotomy.

Step 0 (limits of sequences in $K$ lie in $K$). Let $(z_{m})_{m\in\mathbb{N}}$ be a sequence in $X$ with $z_{m}\in K$ for every $m\in\mathbb{N}$ that converges to $x\in X$ in $(X,d)$. Suppose $x\notin K$. As $K$ is closed in $(X,\mathcal{T}_{d})$, $X\setminus K\in\mathcal{T}_{d}$, so $X\setminus K$ is open in $(X,d)$ and there is a real $r>0$ with $B_{d}(x,r)\subseteq X\setminus K$. By Convergent Sequence in a Metric Space §converges there is $N\in\mathbb{N}$ with $d(z_{m},x)<r$ for every $m\ge N$; then $d(x,z_{N})=d(z_{N},x)<r$ by Metric Space §symmetric, so $z_{N}\in B_{d}(x,r)\subseteq X\setminus K$, contradicting $z_{N}\in K$. Hence $x\in K$.

Claim 1. Let $(x_{m})_{m\in\mathbb{N}}$ be a sequence in $X$ with $x_{m}\in K$ for every $m\in\mathbb{N}$.

Step 1.1 (one refinement). We show: for every $k\in\mathbb{N}$ and every infinite $I\subseteq\mathbb{N}$ there are $a\in X$ and an infinite $I'\subseteq I$ with $d(a,x_{n})<1/k$ for every $n\in I'$. As $0<1/k$ by (A) and $K$ is totally bounded, there is a finite subset $F$ of $X$ such that every point of $K$ lies in $B_{d}(a,1/k)$ for some $a\in F$. For $a\in F$ let $J_{a}=\{n\in I:d(a,x_{n})<1/k\}$. Each $n\in I$ satisfies $x_{n}\in K$, so $x_{n}\in B_{d}(a,1/k)$, that is $d(a,x_{n})<1/k$, for some $a\in F$; hence $I=\bigcup_{a\in F}J_{a}$. If every $J_{a}$ were finite, $I$ would be finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §family-union. So some $J_{a}$ is infinite, and $a$ and $I'=J_{a}$ are as required.

Step 1.2 (nested index sets). Let $\mathfrak{B}$ be the set of all $(k,I)\in\mathbb{N}\times\mathcal{P}(\mathbb{N})$ such that $I$ is infinite and there is $a\in X$ with $d(a,x_{n})<1/k$ for every $n\in I$, and let $R$ be the set of all pairs $((k,I),(k',I'))$ of elements of $\mathfrak{B}$ with $k'=k+1$ and $I'\subseteq I$, a relation on $\mathfrak{B}$. For $(k,I)\in\mathfrak{B}$, Step 1.1 applied to $k+1$ and $I$ gives $I'$ with $(k+1,I')\in\mathfrak{B}$ and $((k,I),(k+1,I'))\in R$. The set $\mathbb{N}$ is infinite by Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples §infinite, so Step 1.1 applied to $1$ and $\mathbb{N}$ gives an element $s=(1,I^{\circ})$ of $\mathfrak{B}$. By Axiom of Dependent Choice §dependent-choice there is a map $f:\mathbb{N}\to\mathfrak{B}$ with $f_{1}=s$ and $(f_{m},f_{m+1})\in R$ for every $m\in\mathbb{N}$. By induction from $1$, The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §induction, the first component of $f_{m}$ is $m$; write $f_{m}=(m,I_{m})$. Thus every $I_{m}$ is an infinite subset of $\mathbb{N}$, for every $m$ there is $a\in X$ with $d(a,x_{n})<1/m$ for every $n\in I_{m}$, and $I_{m+1}\subseteq I_{m}$. For fixed $k\in\mathbb{N}$, induction on $j$ from $1$, using $k\le1\Rightarrow k=1$ by Arithmetic and Order of the Natural Numbers §least and (D) in the inductive step, gives $I_{j}\subseteq I_{k}$ for every $j\in\mathbb{N}$ with $k\le j$.

Step 1.3 (the indices). For $k,n\in\mathbb{N}$ the set $\{m\in I_{k+1}:n<m\}$ is nonempty by (C); let $g(k,n)$ be its least element, which exists by Arithmetic and Order of the Natural Numbers §well-order and is unique by Bounds, Least and Greatest Elements, Suprema and Infima for a Partial Order §least. This defines a map $g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ by Sets and Maps: Ordinary Notation §maps. Let $c$ be the least element of $I_{1}$, nonempty by (C). By Recursion on the Natural Numbers Starting at One §recursion there is a map $\sigma:\mathbb{N}\to\mathbb{N}$ with $\sigma(1)=c$ and $\sigma(k+1)=g(k,\sigma(k))$ for every $k\in\mathbb{N}$. Then $\sigma(k)\in I_{k}$ for every $k\in\mathbb{N}$, by induction on $k$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §induction): $\sigma(1)=c\in I_{1}$, and $\sigma(k+1)=g(k,\sigma(k))\in I_{k+1}$. Moreover $\sigma(k)<g(k,\sigma(k))=\sigma(k+1)$ for every $k\in\mathbb{N}$ by the definition of $g$. So $\sigma$ is strictly increasing and $(y_{k})_{k\in\mathbb{N}}$ with $y_{k}=x_{\sigma(k)}$ is a subsequence of $(x_{m})$; and $y_{k}\in K$ for every $k$.

Step 1.4 (a Cauchy subsequence and its limit). Let $\varepsilon>0$ be real, put $\eta=\varepsilon/(1+1)$, positive by (B), and choose by (A) $k_{0}\in\mathbb{N}$ with $1/k_{0}<\eta$. Let $j,l\in\mathbb{N}$ with $j\ge k_{0}$ and $l\ge k_{0}$. By Steps 1.2 and 1.3, $\sigma(j)\in I_{j}\subseteq I_{k_{0}}$ and $\sigma(l)\in I_{l}\subseteq I_{k_{0}}$, and there is $a\in X$ with $d(a,x_{n})<1/k_{0}$ for every $n\in I_{k_{0}}$. By Metric Space §triangle, Metric Space §symmetric and Rules of Arithmetic and Order in an Ordered Field §order-sum,

$$d(y_{j},y_{l})\le d(a,y_{j})+d(a,y_{l})<\tfrac{1}{k_{0}}+\tfrac{1}{k_{0}}<\eta+\eta=\varepsilon .$$

Hence $(y_{k})$ is a Cauchy sequence in $(X,d)$. As $(X,d)$ is complete, $(y_{k})$ is convergent: it converges to some $x\in X$, and $x\in K$ by Step 0. The subsequence $(x_{\sigma(k)})_{k\in\mathbb{N}}$ and the point $x$ witness Sequentially Compact Subset of a Metric Space §sequentially-compact for $(x_{m})$. As this sequence was arbitrary, $K$ is sequentially compact in $(X,d)$.

Claim 2. Let $\mathcal{T}_{K}$ be the subspace topology on $K$ induced by $\mathcal{T}_{d}$. By Compact Topological Space and Compact Subset §compact-subset and Compact Topological Space and Compact Subset §compact we must show that for every subset $\mathcal{U}$ of $\mathcal{T}_{K}$ with $K\subseteq\bigcup\mathcal{U}$ some finite subset of $\mathcal{U}$ has a union containing $K$. Fix such a $\mathcal{U}$, and call a subset $S$ of $K$ bad if there is no finite subset $\mathcal{V}$ of $\mathcal{U}$ with $S\subseteq\bigcup\mathcal{V}$. A bad set is nonempty, as $\emptyset$ is a finite subset of $\mathcal{U}$ by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §small with $\emptyset\subseteq\bigcup\emptyset$. Suppose, for a contradiction, that $K$ is bad.

Step 2.1 (one refinement). We show: for every $k\in\mathbb{N}$ and every bad $S\subseteq K$ there are $a\in X$ and $y$ such that $S\cap B_{d}(a,1/k)$ is bad and contains $y$. As in Step 1.1 there is a finite subset $F$ of $X$ such that every point of $K$ lies in $B_{d}(a,1/k)$ for some $a\in F$, so $S=\bigcup_{a\in F}(S\cap B_{d}(a,1/k))$. Suppose no $S\cap B_{d}(a,1/k)$ with $a\in F$ is bad. Then for $a\in F$ the set $C_{a}$ of all finite subsets $\mathcal{V}$ of $\mathcal{U}$ with $S\cap B_{d}(a,1/k)\subseteq\bigcup\mathcal{V}$ is nonempty, and Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §choice, applied to $F$ and the family $(C_{a})_{a\in F}$, gives a map $\varphi$ on $F$ with $\varphi(a)\in C_{a}$ for every $a\in F$. The set $\bigcup_{a\in F}\varphi(a)$ is a finite subset of $\mathcal{U}$ by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §family-union, and its union contains $S$, contradicting the badness of $S$. So some $S\cap B_{d}(a,1/k)$ is bad, hence nonempty, and contains some $y$.

Step 2.2 (nested bad sets). Let $\mathfrak{C}$ be the set of all $((k,y),S)\in(\mathbb{N}\times X)\times\mathcal{P}(K)$ such that $S$ is bad, $y\in S$, and $S\subseteq B_{d}(a,1/k)$ for some $a\in X$, and let $Q$ be the set of all pairs $(((k,y),S),((k',y'),S'))$ of elements of $\mathfrak{C}$ with $k'=k+1$ and $S'\subseteq S$, a relation on $\mathfrak{C}$. For $((k,y),S)\in\mathfrak{C}$, Step 2.1 applied to $k+1$ and $S$ gives $a$ and $y'$ with $((k+1,y'),S\cap B_{d}(a,1/(k+1)))\in\mathfrak{C}$, a $Q$-successor. Step 2.1 applied to $1$ and the bad set $K$ gives an element $s'$ of $\mathfrak{C}$ with first component $(1,y)$ for some $y$. By Axiom of Dependent Choice §dependent-choice there is a map $h:\mathbb{N}\to\mathfrak{C}$ with $h_{1}=s'$ and $(h_{m},h_{m+1})\in Q$ for every $m\in\mathbb{N}$; by induction from $1$, The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §induction, $h_{m}=((m,y_{m}),S_{m})$ for some $y_{m}$ and $S_{m}$. Thus every $S_{m}$ is bad, $y_{m}\in S_{m}\subseteq K$, for every $m$ there is $a\in X$ with $S_{m}\subseteq B_{d}(a,1/m)$, and $S_{m+1}\subseteq S_{m}$; as in Step 1.2, $S_{j}\subseteq S_{k}$ whenever $k\le j$.

Step 2.3 (the limit point). Let $\varepsilon>0$ be real, put $\eta=\varepsilon/(1+1)$ and choose $k\in\mathbb{N}$ with $1/k<\eta$, by (B) and (A). For $j,l\ge k$ we have $y_{j},y_{l}\in S_{k}\subseteq B_{d}(a,1/k)$ for some $a\in X$, so $d(y_{j},y_{l})\le d(a,y_{j})+d(a,y_{l})<\varepsilon$ as in Step 1.4. Hence $(y_{m})$ is a Cauchy sequence in $(X,d)$, and by Complete Metric Space §complete and Convergent Sequence in a Metric Space §convergent it converges to some $x\in X$; $x\in K$ by Step 0.

Step 2.4 (contradiction). As $x\in K\subseteq\bigcup\mathcal{U}$, there is $U\in\mathcal{U}$ with $x\in U$, and $U=K\cap W$ for some $W\in\mathcal{T}_{d}$ by Subspace Topology §subspace-topology. As $W$ is open in $(X,d)$, there is a real $r>0$ with $B_{d}(x,r)\subseteq W$. In this order choose: $\rho=r/(1+1)$ and $\eta=\rho/(1+1)$, positive with $\rho+\rho=r$ and $\eta+\eta=\rho$ by (B); then $k\in\mathbb{N}$ with $1/k<\eta$ by (A); then $N\in\mathbb{N}$ with $d(y_{m},x)<\rho$ for every $m\ge N$, by Convergent Sequence in a Metric Space §converges; and put $m=\max\{k,N\}$, which exists by The Maximum and Minimum of Two Elements of a Total Order §exists and satisfies $k\le m$ and $N\le m$ by The Maximum and Minimum of Two Elements of a Total Order §bounds. Let $a\in X$ with $S_{k}\subseteq B_{d}(a,1/k)$; then $y_{m}\in S_{m}\subseteq S_{k}$. For every $z\in S_{k}$, Metric Space §triangle and Metric Space §symmetric give

$$d(x,z)\le d(y_{m},x)+d(a,y_{m})+d(a,z)<\rho+\tfrac{1}{k}+\tfrac{1}{k}<\rho+\eta+\eta=r,$$

so $z\in B_{d}(x,r)\subseteq W$, and $z\in K$; hence $z\in U$. Thus $S_{k}\subseteq\bigcup\{U\}$, where $\{U\}$ is a finite subset of $\mathcal{U}$ by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §small, contradicting the badness of $S_{k}$.

Hence $K$ is not bad: some finite subset of $\mathcal{U}$ has a union containing $K$. As $\mathcal{U}$ was arbitrary, $(K,\mathcal{T}_{K})$ is compact, that is, $K$ is compact in $(X,\mathcal{T}_{d})$.