1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
7
  • $\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$
    – iom10
    Commented 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$
    – iom10
    Commented 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$
    – iom10
    Commented Dec 2, 2022 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.