Consider an ambient metric space $(\mathcal{X},\Vert\cdot\Vert_\infty)$. Let $\mathcal{B}_1 = \mathcal{B}_{\Vert\cdot\Vert_K}(0,1)\subseteq\mathcal{X}$ be the closed unit ball with respect to some norm $\Vert\cdot\Vert_K$. Denote the $\varepsilon$-covering number of $\mathcal{B}_1$ with respect to $\Vert\cdot\Vert_\infty$ by $\mathcal{N}(\varepsilon, \mathcal{B}_1,\Vert\cdot\Vert_\infty)$. That is, we can find a set of points $\{x_1,\dots,x_n\}\subseteq\mathcal{X}$ with $n = \mathcal{N}\left(\varepsilon, \mathcal{B}_1,\Vert\cdot\Vert_\infty\right)$ such that for all $x\in\mathcal{B}_1$, there exists $i\in[n]$ with \begin{equation} \Vert x - x_i\Vert_\infty\leq\varepsilon \end{equation} From the observation that the ball is closed and the covering number is defined with $\leq$ instead of $<$ (see equation above), I am tempted to assume that the covering number is a right-continuous function of $\varepsilon$. Is this assumption correct?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
Without additional assumptions on the metric space, it may appear that for every $\varepsilon>1$ the covering number equals 1, but for $\varepsilon=1$ it is infinite. For example, let positive integers be the points and the distance between $n$ and $m>n$ be equal $1+1/m$.
For compact metric space, it is right-continuous as you may take a convergent subsequence of cover sets.
answered Dec 1, 2022 at 9:49
-
$\begingroup$ Thank you very much for your helpful answer (unfortunately I cannot upvote yet). Regarding your second statement, I have tried to formalize the right-continuity via convergent sequences (see initial post). Could you please have a look at the proof attempt to check if it is correct? Thanks again for the help! $\endgroup$– iom10Commented Dec 1, 2022 at 19:10
-
$\begingroup$ I do not understand your notations and choosing quantifiers seems suspicial, but the idea is very simple: if for all $n$ you may cover $X$ by $N$ balls with radius $\varepsilon+1/n$ centered in points $x_1(n),\dots,x_N(n)$, then choose a subsequence $n_1<n_2<\dots$ such that $x_i(n_k)$ converges to some $x_i$ for all $i=1,\dots,N$. The balls cenrered in $x_i$'s of radius $\varepsilon$ cover $X$. $\endgroup$ Commented Dec 1, 2022 at 19:24
-
$\begingroup$ Thanks for the clarifications. I was wondering if we can always find a converging subsequence $(x_i(n_k))_k$. Then I found the Bolzano–Weierstrass theorem. Do we deduce the existence of the converging subsequence from this theorem? $\endgroup$– iom10Commented Dec 2, 2022 at 6:00
-
$\begingroup$ Bolzano-Weierstrass is for bounded subsets of $\mathbb{R}^n$, for compact metric spaces it is one of equivalent definitions (see "sequential compactness") $\endgroup$ Commented Dec 2, 2022 at 9:13
-
$\begingroup$ Great, I appreciate your help. Maybe one more question: how is $N$ defined in your proof? Do we take $N$ to be the $\varepsilon$-covering number? $\endgroup$– iom10Commented Dec 2, 2022 at 13:39