$\epsilon $-net
Definition Suppose $X$ is a metric space with a metric $d$, and suppose $S$ is a subset of $X$. Let $\epsilon $ be a positive real number. A subset $N\subset S$ is an $\epsilon $-net for $S$ if, for all $x\in S$, there is an $y\in N$, such that $$.
For any $\epsilon >0$ and $S\subset X$, the set $S$ is trivially an $\epsilon $-net for itself.
Theorem^{} Suppose $X$ is a metric space with a metric $d$, and suppose $S$ is a subset of $X$. Let $\epsilon $ be a positive real number. Then $N$ is an $\epsilon $-net for $S$, if and only if
$$\{{B}_{\epsilon}(y)\mid y\in N\}$$ |
is a cover for $S$. (Here ${B}_{\epsilon}(x)$ is the open ball with center $x$ and radius $\epsilon $.)
Proof. Suppose $N$ is an $\epsilon $-net for $S$. If $x\in S$, there is an $y\in N$ such that $x\in {B}_{\epsilon}(y)$. Thus, $x$ is covered by some set in $\{{B}_{\epsilon}(x)\mid x\in N\}$. Conversely, suppose $\{{B}_{\epsilon}(y)\mid y\in N\}$ is a cover for $S$, and suppose $x\in S$. By assumption^{}, there is an $y\in N$, such that $x\in {B}_{\epsilon}(y)$. Hence $$ with $y\in N$. $\mathrm{\square}$
Example In $X={\mathbb{R}}^{2}$ with the usual Cartesian metric, the set
$$N=\{(a,b)\mid a,b\in \mathbb{Z}\xc3\mathrm{\x82}\xc2\mathrm{}\}$$ |
is an $\epsilon $-net for $X$ assuming that $\epsilon >\sqrt{2}/2$. $\mathrm{\square}$
The above definition and example can be found in [1], page 64-65.
References
- 1 G. Bachman, L. Narici, Functional analysis^{}, Academic Press, 1966.
Title | $\epsilon $-net |
---|---|
Canonical name | varepsilonnet |
Date of creation | 2013-03-22 13:37:54 |
Last modified on | 2013-03-22 13:37:54 |
Owner | Koro (127) |
Last modified by | Koro (127) |
Numerical id | 4 |
Author | Koro (127) |
Entry type | Definition |
Classification | msc 54E35 |
Related topic | Cover |