2
$\begingroup$

Definition $(\epsilon -Net)$ :let $(T,d)$ be a metric space .Consider a subset $ K \subset T$ and let $\epsilon >0$, A subset $N \subset K $ is called $\epsilon -Net$ of $K$ if every point in $K$ is within a distance $\epsilon$ if every point in K is within a distance $\epsilon$ of some point of $N$,i.e.

$$\forall x \in K \ \ \ \exists x_0 \in N \ : d (x,x_0) \leq \ \epsilon$$

Definition(Covering Number): For metric space $(T,d)$ The covering number of $K \subset T$ respect to a given $\epsilon \geq 0$ ,denotes as $N(K,d,\epsilon )$, is the smallest possible cardinarity an $\epsilon -Net$ of K , or equivalently ,is the smallest number of closed balls with centers in $K$ and radii $\epsilon$ whose union covers $K$

Definition(Exterior Covering Number): For metric space $(T,d)$ The exterior covering number of $K \subset T$ respect to a given $\epsilon \geq 0$ ,denotes as $N^{ext}(K,d,\epsilon )$, is the smallest number of closed balls with centers not necessary in $K$ and radii $\epsilon$ whose union covers $K$

then I was asked to prove that:

$$N(K,d,\epsilon) \leq N^{ext} (K,d,\epsilon /2) $$

how to see that ?

here is my attempt: since each $\epsilon -ball$ in $N(K,d, \epsilon) $ should intersect at least one $\epsilon /2 -ball$ in $N^{ext}(N,d,\epsilon/2)$ ,thus I am trying to show that by contradiction: for each two distinct $\epsilon -ball$ in $N(K,d, \epsilon)$ ,the $\epsilon /2 -balls$ they intersect must contain a distinct one.

$\endgroup$
1
$\begingroup$

Suppose that $$\bar B(x_1, \epsilon / 2), \ \dots, \ \bar B(x_{N^{\rm ext}}, \epsilon / 2)$$ is an external covering of $K$ of minimal size.

For each $i \in \{ 1, \dots, N^{\rm ext}\}$, there exists a $k_i \in K$ that is contained in $\bar B(x_i, \epsilon / 2)$. (Otherwise $\bar B(x_i, \epsilon / 2)$ would be redundant, contradicting the minimality of size of the covering).

By the triangle inequality, $$ \bar B(x_i , \epsilon / 2) \subseteq \bar B(k_i, \epsilon), $$ for each $i$, which means that $$\bar B(k_1, \epsilon ), \ \dots, \ \bar B(k_{N^{\rm ext}}, \epsilon)$$ is an internal covering of size $N^{\rm ext}$. Hence the smallest internal covering has size at most $N^{\rm ext}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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